Contest

CAKEWALK

# PROBLEM:

Given integers X and Y. Determine the minimum number of moves required to change X to Y, where in one move, you can either add 2 or subtract 1 from X.

# EXPLANATION:

A simple problem, with a little casework:

Y \le X - In this case, Chef has to go X-Y steps backwards, from his current position. Since he can go only one step backwards in each move, the minimum number of moves required is thus X-Y.

Y > X - Here, Chef has to go Y-X steps forward, from his current position.
When Y-X is even, Chef can make exactly \frac{Y-X}{2} forward moves (since each forward move takes him two steps ahead) to reach Y.
When Y-X is odd, Chef can make \frac{Y-X+1}{2} forward moves (taking him to Y+1), followed by 1 backward move (taking him to Y).

It can be trivially deduced that no better sequence of moves exists.

O(1)

per test case.

# SOLUTIONS:

Editorialistâ€™s solution can be found here

Experimental: For evaluation purposes, please rate the editorial (1 being poor and 5 excellent)

• 1
• 2
• 3
• 4
• 5

0 voters