Chef and Inflation
All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
A recent glut in Chefland's markets has caused the local currency Peppercorn to devaluate sharply. (Peppercorns are getting cheaper on an average, though there could be ups and downs).
And Chef needs to rescue his wealth! Initially, he had D Peppercorns. There are N exchange kiosks in the city he lives in, where he can go and exchange his Peppercorns for a well-known stable currency, the Antarctican Dollar. For each kiosk, the exchange rate for the first M seconds of the day is known (both for buying and selling). All kiosks are arranged in a row, and to travel from the ith to the jth kiosk, you need to spend |i-j| seconds, and to exchange currency at any kiosk, you also need 1 second. So, starting at point of time 0 at any of the kiosks (he can get there before trading starts for the day), Chef runs from one kiosk to another to buy and sell currency. You need to find the maximum amount of Peppercorns Chef could have after the Mth second.
- If X is a buying rate, the kiosk will pay you X Peppercorns for 1 Antarctican Dollar.
- If X is a selling rate, you will pay the kiosk X Peppercorns for 1 Antarctican Dollar.
First line of input contains three numbers — N, M and D. N lines follow. ith line (i = 0 … N-1) contains 2*M integers — currency rate for ith kiosk. Numbers Ai, 2j and Ai, 2j+1 (j = 0 … M-1) are the selling and buying rates, respectively, at the jth second for the ith kiosk.
Output a single number: the maximum amount of money (in Peppercorns - in the end Chef ought to have all the money converted to local currency since it's the only valid currency in the country for financial operations) he could have after M seconds, with absolute or relative error not more than 1e-6.
If the amount of money of any currency that Chef will own at any point of time exceeds 1018, output file should contain only a single line containing the string “Quintillionnaire” (without quotes, followed by a newline character).
- 1 ≤ D ≤ 1018
- 1 ≤ N, M ≤ 103
- 1 ≤ Ai, j ≤ 109
- Ai, 2j > Ai, 2j+1 (because there are no miracles in Chefland — you’ll always pay more than what the kiosk will pay you. Otherwise, one could’ve indefinitely sold and bought and increased their money this way).
SubtasksSubtask 1 (20 points):
- 1 ≤ N ≤ 100
- 1 ≤ M ≤ 100
- 1 ≤ D ≤ 103
- 1 ≤ Ai,j ≤ 103
- 1 ≤ N ≤ 100
- 1 ≤ M ≤ 100
Input: 3 3 5 2 1 5 3 7 6 2 1 4 3 6 5 10 9 8 7 6 5 Output: 15.0000000000
|Tags||dynamic-programming, jan16, medium, witalij_hq|
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.