PROBLEM LINK:Author: Kirill DIFFICULTY:Easy PREREQUISITES:Math, Binary Exponentiation, Sum of Geometric Progression PROBLEM:Given that two thieves have $1$ billion to divide amongst them according to a particular method, report the amounts both the thieves will receive upon division. The particular method here is that after a certain amount of time $t$, only (1 Billion * $p^t$) amount of money can be taken, where $0 \leq p \leq 1$. Also, there are only $M$ minutes to divide the stolen money and escape. EXPLANATION:Subtask 1
After the fourth minute, both the thieves will lose all the money. So, let's go back in time minute by minute and see what the optimal division would be.
The acceptances will be because the theif accepting the plan can in no way gain more money in the future than being offered at that point in time. Please note this point in the question: We can make a very important observation here. The amount that Thief 1 will gain is given by: Subtask 2 We common ratio $r$ = $p$ and the first term of GP $a$ = $1$. The formula to calculate the sum of first $n$ terms of a GP is well known: Thus, in this case, $S = \frac{((p)^M  1)}{(p)1}$. Subtask 3 COMPLEXITY:$\mathcal{O}(\log M)$ per test case. SAMPLE SOLUTIONS:
This question is marked "community wiki".
asked 05 Sep '15, 17:34

sum of GP :P https://www.codechef.com/viewsolution/8129204 answered 14 Sep '15, 17:21

For those who couldn't understand the question, I'll explain it with a test case. Suppose p=0.6, M = 5. t=0 > money > 1 billion. Here Chef will decide(make a decision). t=1> money > 0.6 billion. Here other will decide. t=2 > money > 0.36 billion. Here Chef will decide. t=3 > money > 0.216 billion. Here other will decide. t=4 > money > 0.1296 billion. Here Chef will decide. If the situation comes to t=4, it is obvious that chef will take all the 0.1296 billion, and other thief will agree. So, before this time (at t=3), the other thief will decide to give Chef 0.1296 billion, so that he will accept because in any case that is the maximum amount chef can get. So other thief will get (0.2160.1296) = 0.0864 billion. So, before this time (at t=2), the Chef will decide to give other thief 0.0864 billion, so that he will accept because in any case that is the maximum amount other thief can get. So chef will get (0.360.0864) = 0.2736 billion. So, before this time (at t=1), the other thief will decide to give Chef 0.0.2736 billion, so that he will accept because in any case that is the maximum amount chef can get. So other thief will get (0.60.2736) = 0.3264 billion. So, before this time (at t=0), the Chef will decide to give other thief 0.3264 billion, so that he will accept because in any case that is the maximum amount other thief can get. So chef will get (10.3264) = 0.6736 billion. Finally, you will get a G.P. and then it can be solved easily. answered 14 Sep '15, 18:56

Well, for the fourth test case: t = 0 > p = $1000\cdot10^6$ t = 1 > p = $500\cdot10^6$ t = 2 > p = $250\cdot10^6$ t = 3 > p = $125\cdot10^6$ I started backwards. At the third minute it is the second thief turn, right. Then the gold that is left is 125000000. Which means that if the second thief offers 0 125000000, the Chef should accept it. Otherwise. at the fourth minute, the Chef will take 0 as well. And we know that  "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.". So at the third minute the Chef would accept the plan 0 125000000. Then, at the second minute, if the Chef offered the plan 125000000 125000000, the second thief would accept it, because the total amount of stolen dollars is more. If the Chef tried to offer more to himself and less for the second thief, the second thief would reject the offer, and receive more at the next turn. Then again, at the first minute, if the second thief offered the plan 125000000 375000000, the Chef would accept it, because of the totalamountrule. At last, at the beginning the Chef will propose the plan 625000000 375000000, and the second thief will accept it, because of the totalamountrule. answered 14 Sep '15, 18:29

Check this video and subscribe to the channel for more video editorials.. https://www.youtube.com/watch?v=KaucPRyejis Hope this helps.. answered 14 Sep '15, 22:23

Let $a(M)$,$b(M)$ be the proportions of the money the first and second thief obtain given $M$ minutes to decide. Clearly $a(1)=1$,$b(1)=0$ as with no time left the second thief will agree to anything to avoid arrest. For general M, the first thief thinks: If the other guy rejects my offer, I will get $pb(M−1)$ and he $pa(M−1)$ since we play the same game with less money, less time, and roles switched. He will reject especially if I offer him less than $pa(M−1)$. He will greedily accept if I offer more than $pa(M−1)$ but that would not be optimal for me; he will also accept by the tiebreaking rule if I offer exactly $pa(M−1)$, which will leave $1−pa(M−1)$ for me, certainly at least as much as $pb(M−1)$. We obtain the recursion $$\large a(1)=1,a(M)=1−pa(M1)$$ $$\large a(M)=1p(1pa(M2))=1p+p^2a(M2)$$ $$\large a(M)=1p+p^2p^3+...+(p)^Ma(1)$$ But Since $a(1)=1$, $$\large a(M)=1p+p^2p^3+...+(p)^M$$ $$\large a(M)=\dfrac{1(p)^M}{1(p)}$$ $$\large b(M)=1a(M)$$ $$\large b(M)=1\dfrac{1(p)^M}{1+p}=\frac{p+(p)^M}{1+p}.$$ So, After multiply with $10^9$ we get our final $a(M)$ and $b(M)$. Link to the solution:https://www.codechef.com/viewsolution/8037182 answered 16 Sep '15, 16:57

Can anyone help me out? suppose the test cases are: 4 1 0.5 2 0.5 3 0.5 4 0.5 for 1 0.5 output > 10^9 0.0 ... ok . 2 0.5 output> 510^8 510^8 ... ok 3 0.5 output > 750000000.0000 250000000.0000 > why???? .. see chef has 750000000.0 i.e decision is made at t=1 . And chef offer other thief 250000000.0 because at the beginning of 3rd min other thief will be able to stole only 250000000.0 money .BUT why other thief agreed to chef ? I mean if other thief would not have agreed to chef then he will offer 500000000.0 to chef after the beginning of the 2nd minute and able to keep 500000000.0 with himself . And in that case chef also would not able declined to other thief because after 2nd min both of them will have reduce amount of money . same problem with 4 0.5 > output> 625000000.0000 375000000.0000 ??? again decision made at beginning of 1st minute. Why other thief always agreed to chef ?. I doing something wrong . Please correct me answered 14 Sep '15, 17:53
1
@aragar .. Thanks a lot . I was thinking after t time both can (10^9 X p^t) amount of money . But actually total money both can take away is (10^9 X p^t) .
(14 Sep '15, 18:44)

I am little bit confuse in this problem, in the problem statement it is written that: answered 14 Sep '15, 19:56

Here is a simple solution. At time t1, the thief(thief 1) who has the chance would divide the money in his favor. That is the division would be {max*p^(t1),0}. Keeping this in mind the other thief(thief2) will divide the money as {maxp^(t2)maxp^(t1), (max*p^(t1)} in the previous chance as the sum of money will be more and thief 1 will be getting the amount he wants in the last chance. The same logic goes on every chance and the chef would hence choose the division as ( max –maxp+maxp^2maxp^3…… maxp^(t1), maxpmaxp^2+maxp^3…… maxp^(t1)) This forms a simple geometric progression which can be calculated using G.P.formula. https://www.codechef.com/viewsolution/8165228 answered 14 Sep '15, 21:09

I think there is some problem with the Editorialist's solution. I was thinking on the same grounds but I don't know why it's showing such output. answered 18 Oct '15, 22:17

https://www.codechef.com/viewsolution/10856885 Can anybody tell me why is this not working? answered 19 Jul '16, 20:31
in printf use precision upto 6 decimal place ,i.e., %0.6lf.. Here's your corrected code https://www.codechef.com/viewsolution/10857144
(19 Jul '16, 21:20)
