# TWONMS - Editorial

Author: Ramazan Rakhmatullin
Testers: Lewin Gan, Marek Sommer
Editorialist: Pawel Kacprzak

Cakewalk

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.

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 64-bit integers.

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:

1. 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)}

2. 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.

3 Likes

#include
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=b
i;flag=0;} }
cout<<max(a,b)/min(a,b);
return0;}

can anyone tell me whatâ€™s problem in my logicâ€¦subtask 2 is not correct
https://www.codechef.com/viewsolution/30538322

1 Like

N can be up to 10^9 which is too much for you to loop through. Please go through the editorial first.

1 Like

how to fix?

What i did here is
Since we are multiplying each a , b with 2 one at a time c times.
So we can observe that if c is odd there will be one extra 2 (multiplied by a )
and if c is even (both numbers will be multiplied same times).So they cancel out each other anyway.
Therefore final solution becomes
if(c is odd)
a = 2*a ;