PROBLEM LINK:Author: Ramazan Rakhmatullin 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: $$\max(A, B) \div \min(A, B)$$ 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: $$\frac{\max(A, B)}{\min(A, B)}$$ EXPLANATION:There are two different subtasks in this problem. In both of them, there are up to $100$ test cases to handle. Subtask 1In 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 $64$bit integers. Subtask 2In 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 now, let's write down a first few values of $A(i)$ and $B(i)$:
it's easy to spot the pattern here:
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$:
thus the final result can be computed using a single integer division operation. AUTHOR'S AND TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 23 Jun '17, 05:50

include<iostream>using namespace std; int main() {int flag=0,i,a,b,n; cin>>a>>b>>n; for(i=1;i<=n;i++) {if(flag==0) {a=ai;flag=1;} else {b=bi;flag=0;} } cout<<max(a,b)/min(a,b); return0;} answered 27 Jul '17, 07:18
