All submissions for this problem are available.
Two cheeky thieves (Chef being one of them, the more talented one of course) have came across each other in the underground vault of the State Bank of Churuland. They are shocked! Indeed, neither expect to meet a colleague in such a place with the same intentions to carry away all the money collected during Churufest 2015.
They have carefully counted a total of exactly 1 billion (109) dollars in the bank vault. Now they must decide how to divide the booty. But there is one problem: the thieves have only M minutes to leave the bank before the police arrives. Also, the more time they spend in the vault, the less amount could carry away from the bank. Formally speaking, they can get away with all of the billion dollars right now, but after t minutes they can carry away only 1 billion * pt dollars, where p is some non-negative constant less than or equal to unity, and at t = M, they get arrested and lose all the money. They will not leave the vault until a decision on how to divide the money has been made.
The money division process proceeds in the following way: at the beginning of each minute starting from the 1st (that is, t = 0), one of them proposes his own way to divide the booty. If his colleague agrees, they leave the bank with pockets filled with the proposed amounts of dollars. If not, the other one proposes his way at the next minute etc. To escape arrest, they can only propose plans till the beginning of the Mth minute (i.e., till t = M-1). Each thief wants to maximize his earnings, but if there are two plans with the same amounts for him, he would choose the one which leads to a larger total amount of stolen dollars.
Chef is about to start this procedure, and he is the first to propose a plan. You are wondering what will be the final division of money, if each thief chooses the optimal way for himself and money is considering real.
InputThe first line of input contains an integer T denoting the number of test cases. The description of T test cases follows. The only line of input for each test case contains an integer M denoting the number of minutes until arrest and a double denoting the constant p.
OutputFor each test case, output a single line containing two space-separated doubles denoting the amount of dollars each thief will get in the optimal division. First number: dollars amassed by Chef, and second: by his colleague. The answer will be considered correct if its absolute error doesn't exceed 10-2.
Constraints and subtasks
- 1 ≤ T ≤ 105
- 0 ≤ p ≤ 1
Input: 2 1 0.5 2 0.5 Output: 1000000000.0 0.0 500000000.0 500000000.0
Example case 1. In the second case, if decision isn't made at t = 0, total amount of money decreases to 5*108 at t = 1 which leads to a situation worse than the given solution.
|Tags||binary, easy, kaizer, math, sept15|
|Time Limit:||1 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, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.