لینک‌های مفید برای شرکت در مسابقه:

در طول مسابقه، می‌توانید سؤالات خود را از قسمت «سؤال بپرسید» مطرح کنید.

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- Nowadays everything depends on exchange rate of dollar (Now it is called *rate* due to its importance). Total atmosphere of our country has been affected by *rate*. But this is not the only reason of economical disorders. Some of sellers called "*traitors*" cause the other reason. These sellers act different in different rate swings: + In rate increment, they increase the price of goods bought before and pretext: "I must increase because I need to buy this good again". + In rate decrement, they don't decrease the price of goods bought before and pretext: "I paid more and decrement has lots of damages for me”. Actually if *rate* changes from $r_1$ to $r_2$ (and $r_2 > r_1$ ), *traitors* multiply their price to $\frac{r_2}{r_1}$ and round the product to the nearest(if distances were equal, to upper nearest) multiple of *round base*. For example if a *traitor* bought a pen $1000_{Rials}\space$ in first day and *rate* changed from $8000_{Rials}\space$ to $23000_{Rials}$ and then to $12000_{Rials}\space$, and round base was $100_{Rials}\space$, finally he sells this pen $2900_{Rials}\space$. because: $100 \times 28 < 1000 \times \frac{23000}{8000} = 2875 \le 100 \times 29$ and $2875$ is closer to $2900$. Ali wants to buy a battery for his laptop. But there is only one shop selling this kind of battery. Ali knows that this shop's seller is a *traitor* and has this battery since **n** days ago. Ali went to this shop and realised that the seller sells the battery **p** Rials and round base for this shop is **b** Rials. Ali wants to know how much was this battery's price **d** days ago. He is busy preparing problems for SBU Newbies Contest so he needs your help. # ورودی The input file contains several input sets. The description of each set is given below: Each set starts with four integers $n (0 ≤ n ≤ 10^5)$, the number of days passed from seller's buy, $p (0 ≤ p ≤ 10^9)$, the price of battery, $b (1 ≤ b ≤ 10^5)$, round base, and $d (0 ≤ d ≤ n)$, the number of days passed from Ali's slightly day, following a line with $n + 1$ non-negative space separated integers $r_0, r_1, \dots, r_n\space$. $r_i$ equals the rate when $i$ days passed from seller's buy. Actually $r_0$ equals the rate when seller bought the battery. It is guaranteed that Input will follow the descriptions given.Input is terminated by a set where $n=p=b=d=0$ which should not be processed. There is a blank line between two input sets. sum of $n$ over all input sets are at most $2\times 10^5$ and count of input sets are less than $20$. # خروجی For each input set, produce one line of output including space separated $m$ and $M$ which respectively mean the least and the most possible prices the battery could have in d days ago. # مثال‌ها ## ورودی نمونه ۱ ``` 1 15000 1000 1 8000 12000 2 45000 1000 2 8000 36000 12000 3 20 4 1 1 5 4 3 0 0 0 0 ``` ## خروجی نمونه ۱ ``` 9667 10333 9889 10111 20 20 ```

H – Exchange Rate

محدودیت زمان: ۱ ثانیه
محدودیت حافظه: ۲۵۶ مگابایت

Nowadays everything depends on exchange rate of dollar (Now it is called rate due to its importance). Total atmosphere of our country has been affected by rate. But this is not the only reason of economical disorders. Some of sellers called "traitors" cause the other reason. These sellers act different in different rate swings:

In rate increment, they increase the price of goods bought before and pretext: "I must increase because I need to buy this good again".
In rate decrement, they don't decrease the price of goods bought before and pretext: "I paid more and decrement has lots of damages for me”.

Actually if rate changes from $r_1$ to $r_2$ (and $r_2 > r_1$ ), traitors multiply their price to $\frac{r_2}{r_1}$ and round the product to the nearest(if distances were equal, to upper nearest) multiple of round base. For example if a traitor bought a pen $1000_{Rials}\space$ in first day and rate changed from $8000_{Rials}\space$ to $23000_{Rials}$ and then to $12000_{Rials}\space$ , and round base was $100_{Rials}\space$ , finally he sells this pen $2900_{Rials}\space$ . because: $100 \times 28 < 1000 \times \frac{23000}{8000} = 2875 \le 100 \times 29$ and $2875$ is closer to $2900$ .

Ali wants to buy a battery for his laptop. But there is only one shop selling this kind of battery. Ali knows that this shop's seller is a traitor and has this battery since n days ago. Ali went to this shop and realised that the seller sells the battery p Rials and round base for this shop is b Rials. Ali wants to know how much was this battery's price d days ago. He is busy preparing problems for SBU Newbies Contest so he needs your help.

ورودی🔗

The input file contains several input sets. The description of each set is given below:

Each set starts with four integers $n (0 ≤ n ≤ 10^5)$ , the number of days passed from seller's buy, $p (0 ≤ p ≤ 10^9)$ , the price of battery, $b (1 ≤ b ≤ 10^5)$ , round base, and $d (0 ≤ d ≤ n)$ , the number of days passed from Ali's slightly day, following a line with $n + 1$ non-negative space separated integers $r_0, r_1, \dots, r_n\space$ . $r_i$ equals the rate when $i$ days passed from seller's buy. Actually $r_0$ equals the rate when seller bought the battery. It is guaranteed that Input will follow the descriptions given.Input is terminated by a set where $n=p=b=d=0$ which should not be processed. There is a blank line between two input sets. sum of $n$ over all input sets are at most $2\times 10^5$ and count of input sets are less than $20$ .

خروجی🔗

For each input set, produce one line of output including space separated $m$ and $M$ which respectively mean the least and the most possible prices the battery could have in d days ago.

مثال‌ها🔗

ورودی نمونه ۱🔗

1 15000 1000 1
8000 12000

2 45000 1000 2
8000 36000 12000

3 20 4 1
1 5 4 3

0 0 0 0

خروجی نمونه ۱🔗

9667 10333
9889 10111
20 20

ارسال پاسخ برای این سؤال

در حال حاضر شما دسترسی ندارید.

حل سؤال در بانک سؤالات