Triway Cup '19 Summer Junior P1 - Getting Snappy - Olympiads Online Judge

Triway Cup '19 Summer Junior P1 - Getting Snappy

View as PDF

Submit solution

All submissions

Best submissions

Points: 5

Time limit: 1.25s

Memory limit: 256M

Author:

ManchurioX

Problem type

DISCLAIMER: This problem statement contains NO spoilers to the film Avengers: Endgame and is in no way, shape, or form affiliated to Marvel Entertainment. Uses of characters, settings, and scenes are parodical only.

To celebrate finally defeating the Avengers, Thanos decides to retire from his titanous ways and work on his garden. He's come to see that he's actually quite the farmer, and harvested a bountiful amount of space papayas.

Thanos wants to make himself a pot of papaya soup, but he's strictly on a perfectly balanced diet (as all things should be), and the sheer abundance of papayas is too much to digest. His last harvest produced $N$ $N$ papayas, but Thanos only wants an $M$ $M$ amount for his soup. He hires you, a computer scientist, to help him decide how he can get the optimal papaya value.

Unfortunately, being an almighty titan has its downsides, as Thanos can only reduce the number of papayas by half each time (the quotient is rounded down if it is a decimal number). Thanos is generally flexible when it comes to papaya consumption, but he much prefers an amount that is closer to $M$ $M$ . If there are two amounts that are the same difference from $M$ $M$ , Thanos prefers the higher amount.

Calculate the closest possible final number of papayas to $M$ $M$ to make a somewhat perfectly balanced diet for Thanos.

Input Specification

Line 1: 2 integers $N$ $N$ and $M$ $M$

Constraints

$0 < M < N < 10^4$ $0 < M < N < 10^{4}$

Output Specification

A single integer, representing the closest value possible to $M$ $M$ .

Sample Input

Copy

365 12

Sample Output

Copy

Explanation

Let $\lfloor x \rfloor$ $⌊ x ⌋$ denote the largest integer less than or equal to $x$ $x$ .

We can compute what happens each time Thanos reduces the number of papayas by half:

$\displaystyle \begin{aligned} \left\lfloor\frac{365}{2}\right\rfloor &= 182 \\ \left\lfloor\frac{182}{2}\right\rfloor &= 91 \\ \left\lfloor\frac{91}{2}\right\rfloor &= 45 \\ \left\lfloor\frac{45}{2}\right\rfloor &= 22 \\ \left\lfloor\frac{22}{2}\right\rfloor &= 11 \\ \left\lfloor\frac{11}{2}\right\rfloor &= 5 \\ \left\lfloor\frac{5}{2}\right\rfloor &= 2 \\ \left\lfloor\frac{2}{2}\right\rfloor &= 1 \\ \left\lfloor\frac{1}{2}\right\rfloor &= 0 \end{aligned}$ $\begin{aligned} ⌊ \frac{365}{2} ⌋ & = 182 \\ ⌊ \frac{182}{2} ⌋ & = 91 \\ ⌊ \frac{91}{2} ⌋ & = 45 \\ ⌊ \frac{45}{2} ⌋ & = 22 \\ ⌊ \frac{22}{2} ⌋ & = 11 \\ ⌊ \frac{11}{2} ⌋ & = 5 \\ ⌊ \frac{5}{2} ⌋ & = 2 \\ ⌊ \frac{2}{2} ⌋ & = 1 \\ ⌊ \frac{1}{2} ⌋ & = 0 \end{aligned}$

We see that $11$ $11$ is the closest we can get to $12$ $12$ , thus the answer is $11$ $11$ .

Comments

-2

emily_hu0922 commented on May 30, 2021, 2:51 p.m.

Dmoj: no spoilers

also Dmoj: to celebrate finally defeating the Avengers...

8

thomas_li commented on May 30, 2021, 5:59 p.m.

Thanos wins in Infinity War though