×

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

This question is marked "community wiki".

74484795
accept rate: 12%

19.5k348496535

# 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;}

2★mageshp
1
accept rate: 0%

 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,026
×1,529
×281
×34
×13

question asked: 23 Jun '17, 05:50

question was seen: 1,811 times

last updated: 27 Jul '17, 07:18