PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: notsoloud
Tester: apoorv_me
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
Chef and Chefina play N games.
The loser of the i-th game pays 2^i coins to the winner.
If Chef wins exactly X games, find the maximum possible number of coins he can win.
EXPLANATION:
The powers of 2 form an increasing sequence, so it’s optimal for Chef to win the last X games (and hence lose the first N-X games).
Chef’s total coin gain is hence
\left(2^N + 2^{N-1} + \ldots + 2^{N-X+1}\right) - \left(2^1 + 2^2 + \ldots + 2^{N-X} \right)
Since N is quite small, this can be computed directly using a loop.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Editorialist's code (Python)
for _ in range(int(input())):
n, x = map(int, input().split())
ans = 0
for i in range(x):
ans += 2**(n-i)
for i in range(n-x):
ans -= 2**(i+1)
print(ans)