You are not logged in. Please login at www.codechef.com to post your questions!

×

TWONMS - Editorial

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.

This question is marked "community wiki".

asked 23 Jun '17, 05:50

pkacprzak's gravatar image

5★pkacprzak ♦♦
74484795
accept rate: 12%

edited 24 Jun '17, 23:07

admin's gravatar image

0★admin ♦♦
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;}

link

answered 27 Jul '17, 07:18

mageshp's gravatar image

2★mageshp
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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