TWONMS - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice
Contest

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:

\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 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 64-bit 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:

  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.

1 Like
2

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