Triway Cup '19 Summer Junior P1 - Getting Snappy

View as PDF

Submit solution

Points: 5
Time limit: 1.25s
Memory limit: 256M

Author:
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 papayas, but Thanos only wants an 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. If there are two amounts that are the same difference from M, Thanos prefers the higher amount.

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

Input Specification

Line 1: 2 integers N and M

Constraints

0 < M < N < 10^4

Output Specification

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

Sample Input

365 12

Sample Output

11

Explanation

Let \lfloor x \rfloor denote the largest integer less than or equal to 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}

We see that 11 is the closest we can get to 12, thus the answer is 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