PROBLEM LINK:
Author: Hasan Jaddouh
Tester: Teja Vardhan Reddy
Editorialist: Hussain Kara Fallah
DIFFICULTY:
Cakewalk
PREREQUISITES:
NONE
PROBLEM:
Chef is running a money exchange campaign. At the i^{th} day, he gives his first friend 2^{i-1} Rupees. His second friend gives him (to Chef) A Rupees every day.
You are given A (A \leq 10^9). You need to find D_1 the maximum number of days the campaign can run such that at the end of each day Chef’s total balance is positive.
You need to find D_2 which is the day when Chef had the maximum balance (at the end of it) among all campaign days.
Explanation:
Let’s approach this problem easily and without solving equations. The first thing we can see is that neither values can exceed 35. (It’s a hint given for you in the samples). Anyway, we can easily prove that the upper bound for the maximum number of days cannot exceed that.
Suppose that A=10^9. Until the 30^{th} day, Chef’s balance would remain increasing (because 2^{29}<10^9. His balance at the end of that day would be around 30*10^9 (well it’s less but let’s just assume that). After 30^{th} day, the amount that he will give to his friend (let’s say P) P>10^9. We can see that P needs no more than 6 iterations to reach 32*10^9 and his balance would go negative for sure. (This is not a precise calculation but easy estimation for the upper bound).
So let’s just do a simple simulation, maintaining current giveaway P that doubles at each iteration, the current balance, and the maximum balance. Update these values after each iteration and break when our balance goes negative. That’s it.
Check implementation for details if you need.