PROBLEM LINK:
Author: Kirill
Tester: Kevin Atienza
Editorialists: Pushkar Mishra and Suhash Venkatesh
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
Let us start by taking an example. Let p = 0.5 and t = 4. We not proceed minute by minute.

First minute
Money left to take = 10^9.
Thief 1 to propose a plan. 
Second minute
Money left to take = 10^9 * 0.5.
Thief 2 to propose a plan. 
Third minute
Money left to take = 10^9 * 0.5^2.
Thief 1 to propose a plan. 
Fourth minute
Money left to take = 10^9 * 0.5^3.
Thief 2 to propose a plan.
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.
 If in the fourth minute, Thief 2 proposes a division of 0 and 10^9 * 0.5^3 respectively, Thief 1 will accept it.
 If in the third minute, Thief 1 proposes a division of 10^9 * 0.5^2  (10^9 * 0.5^3) and 10^9 * 0.5^3 respectively, Thief 2 will accept it.
 If in the second minute, Thief 2 proposes a division of 10^9 * 0.5  (10^9 * 0.5^2) + (10^9 * 0.5^3) and (10^9 * 0.5^2)  (10^9 * 0.5^3) respectively, Thief 1 will accept it.
 Finally, if in the second minute, Thief 1 proposes a division of 10^9  (10^9 * 0.5) + (10^9 * 0.5^2)  (10^9 * 0.5^3) and (10^9 * 0.5)  (10^9 * 0.5^2) + (10^9 * 0.5^3) respectively, Thief 2 will accept it.
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:
“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.”
We can make a very important observation here. The amount that Thief 1 will gain is given by:
val = 10^9(p^0  p^1 + p^2  p^3 \dots p^{M1}). Thus, the amount that Thief 2 gets is 10^9  val.
Subtask 2
If we observe the terms inside the bracket in the expression we got for val in subtask 1, we can see that it is basically the summation of terms of a Geometric Progression (GP).
The GP is: 1, p, p^2, p^3, \dots
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:
S = \frac{a(r^n  1)}{r1}
Thus, in this case, S = \frac{((p)^M  1)}{(p)1}.
This will work in \mathcal{O}(M) with linear exponentiation.
Subtask 3
The solution of subtask 2 can be optimised by using binary exponentiation to calculate (p)^M. This will allow us to compute the sum of the GP in \mathcal{O}(\log M).
COMPLEXITY:
\mathcal{O}(\log M) per test case.