PROBLEM LINK:
Author: Ramazan Rakhmatullin
Testers: Lewin Gan, Marek Sommer
Editorialist: Pawel Kacprzak
DIFFICULTY:
Cakewalk
PREREQUISITES:
Basic math
PROBLEM:
There is a simple game played with two integers A and B. The games consists of N turns. In every odd turn (1 st, 3 rd, \ldots) A is multiplied by 2. In every even turn (2 nd, 4 th, \ldots) B is multiplied by 2. The goal is to find the value of:
after N turns, where \div represents the integer division e.g. 4 \div 2 = 2 and 3 \div 2 = 1. For the purpose of more readable equations, Iâ€™m going to use regular division operator instead of \div operator, but remeber that it denotes integer division in this problem, so the final answer can be written as:
EXPLANATION:
There are two different subtasks in this problem. In both of them, there are up to 100 test cases to handle.
Subtask 1
In the first subtask, N is at most 30, which allows to simply simulate every turn of the game to find the final values of A and B and then compute the final result as \frac{\max(A, B)}{\min(A, B)}. Notice that since both A and B are at most 10^9, their final values after all turns are performed fits 64bit integers.
Subtask 2
In the second subtask, N can be up to 10^9, which makes the simulation of the game way too slow. Also, values of A and B will become extremely large. We need a better approach here. The way to do this is to exploit the fact that the final answer is the result of a division of two numbers.
Letâ€™s define:
A(i) := the value of A after i turns
B(i) := the value of B after i turns
now, letâ€™s write down a first few values of A(i) and B(i):
 i  0  1  2  3  4  5  6  7  8 

 A(i)  A  2A  2A  4A  4A  8A  8A  16A  16A 
 B(i)  B  B  2B  2B  4B  4B  8B  8B  16B 
itâ€™s easy to spot the pattern here:
 if i is even, then A(i) = c \cdot A and B(i) = c \cdot B for some integer c \geq 1
 if i is odd, then A(i) = 2c \cdot A and B(i) = c \cdot B for some integer c \geq 1
actually, c is always a power of 2, but we wonâ€™t use this fact.
Letâ€™s now take the closer look at the final answer to the problem, i.e. \frac{\max(A(N), B(N))}{\min(A(N), B(N))}, and consider two cases corresponding to the parity of N:

if N is even:
\frac{\max(A(N), B(N))}{\min(A(N), B(N))} = \frac{\max(c \cdot A, c \cdot B)}{\min(c \cdot A, c \cdot B)} = \frac{c \cdot \max(A, B)}{c \cdot \min(A, B)} = \frac{max(A, B)}{min(A,B)} 
if N is odd:
\frac{\max(A(N), B(N))}{\min(A(N), B(N))} = \frac{\max(2c \cdot A, c \cdot B)}{\min(2c \cdot A, c \cdot B)} = \frac{c \cdot \max(2A, B)}{c \cdot \min(2A, B)} = \frac{max(2A, B)}{min(2A,B)}
thus the final result can be computed using a single integer division operation.
AUTHORâ€™S AND TESTERâ€™S SOLUTIONS:
Setterâ€™s solution can be found here.
First testerâ€™s solution can be found here.
Second testerâ€™s solution can be found here.
Editorialistâ€™s solution can be found here.