MONEYDOUBLE - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: yash_daga
Tester: kaori1
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

Chef has X rupees.
At the end of each year, he can either increase X by 1000 or double it.
What’s the maximum amount of money he can have after Y years?

EXPLANATION:

Since Y is pretty small (it’s at most 10, in fact), it’s possible to just simulate what happens for each of the Y years.

Now, for a given year, the choice can be made greedily. That is,

  • If Chef has \lt 1000 rupees, it’s better to add 1000 to his value.
  • If Chef has \geq 1000 rupees, it’s better to multiply it by 2.

Simply repeat these criteria Y times and print the final value of Chef’s money.

A slightly faster solution is to notice that you never need to add 1000 more than once; and if you do, it’ll be only in the first year.
So, the answer is also just the maximum of X\cdot 2^Y and (X+1000)\cdot 2^{Y-1}.

TIME COMPLEXITY:

\mathcal{O}(1) or \mathcal{O}(Y) per testcase.

CODE:

Editorialist's code (Python) 
for _ in range(int(input())):
    x, y = map(int, input().split())
    for i in range(y): x = max(x+1000, 2*x)
    print(x)
1 Like
2

def max_money(X, Y):
return max(X * (2 ** Y), (X + 1000) * (2 ** (Y - 1)))

Example usage:

X = 5000 # Initial amount of money
Y = 5 # Number of years
print(max_money(X, Y)) # Output: 320000