TRICKYDL Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest

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.

AUTHOR’S AND TESTER’S SOLUTIONS:

TESTER’s solution

Editorialist’s solution

2

We can approach this problem in one more way. Consider f(x) = A*x+1-2^x.Differentiate to find max we get
x = log2(A/ln(2)).Check the values at [x] and [x+1] where [.] is greatest integer function and we would get D2. Once you have maximum we need 6 more iterations i.e. x+1 to x+6 and we can find D1.

3 Likes
3 
#include <bits/stdc++.h>
#define ll long long int
#define ibs ios_base::sync_with_stdio(false)
#define cti cin.tie(0)
using namespace std;//coded by abhijay mitra
#define watch(x) cout << (#x) << " is " << (x) << endl
int main()
{
    ibs;cti;
    int t;cin>>t;cout<<"\n";
    while(t--){
        ll a;cin>>a;ll d=1;
        while((pow(2,d)-1)/d <a) d++;
        cout<<d-1<<" ";
        d=log2((float)a/log(2));
        if(a*d+1-pow(2,d)<a*(d+1)+1-pow(2,(d+1)))
            cout<<d+1<<"\n";
        else cout<<d<<"\n";
    }
    return 0;
}

implementation c++