PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: raysh07
Editorialist: iceknight1093
DIFFICULTY:
Cakewalk
PREREQUISITES:
None
PROBLEM:
There are N lily pads in a row.
A frog starts at lily pad N, and alternates jumping left and right; with the distance starting at N-1 and repeatedly decreasing by 1.
Where does the frog end up?
EXPLANATION:
Let the frog’s position be X.
Initially, X = N.
Now,
- After the first move, we have X = N - (N-1) = 1.
- After the second move, we have X = 1 + (N-2) = N-1.
- After the third move, we have X = N-1 - (N-3) = 2.
- After the fourth move, we have X = 2 + (N-4) = N-2.
\vdots
In general, it can be seen that after every pair of consecutive moves, the frog will effectively move one step to the left.
This is because it will jump left by some length (say D) and then jump right by one length less (so D-1), so if it was initially at X, it will end up at X - D + (D-1) = X-1.
So,
- If N-1 is even, we can pair up all adjacent moves, and each adjacent pair will result in a decrease of 1.
So, the frog’s overall position will decrease by exactly \frac{N-1}{2}, and so its final position is just
N - \frac{N-1}{2} = \frac{N+1}{2} - If N-1 is odd, then we can pair up the first N-2 moves; but the last move will be left alone.
The last move is an odd move, so it involves jumping left, and with a distance of 1.
The (N-2) paired moves decrease the position by 1, for an overall decrease of \frac{N-2}{2}.
So, the frog’s final position will be
N - \frac{N-2}{2} - 1 = \frac{N}{2}
Thus, the answer is just \frac{N+1}{2} if N is odd, and \frac{N}{2} if N is even.
The constraints are also small enough that you can simulate the process in \mathcal{O}(N) if you wish to.
TIME COMPLEXITY:
\mathcal{O}(1) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n = int(input())
print((n+1)//2)