PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: abhigyan1245
Tester: kingmessi
Editorialist: iceknight1093
DIFFICULTY:
cakewalk
PREREQUISITES:
None
PROBLEM:
You’re the N-th person standing in a queue to obtain a ticket to an event.
Every second, the first and third person in the queue will receive a ticket and leave the line.
When will you receive your ticket?
EXPLANATION:
If N = 1 or N = 3, you’ll receive a ticket in the very first second.
If N = 2, you’ll receive a ticket in the second second; because after person 1 leaves the line you’ll be the first person remaining.
For N \gt 3, note that in the first second two people ahead of you will receive their tickets and leave the line.
This means one second has passed and you’re basically in the same situation, just that you’re now at position N-2 of the queue instead.
This leads to a very straightforward solution:
- While N \gt 3, add 1 to the answer and subtract 2 from N.
- Once N becomes \leq 3, utilize the cases observed initially: add 1 to the answer if N = 1 or N = 3, and add 2 to the answer if N = 2.
Implemented directly this takes \mathcal{O}(N) time which is fast enough for the given constraints.
It can be further optimized to constant time by doing some simple algebra to avoid the loop over N.
TIME COMPLEXITY:
\mathcal{O}(N) or \mathcal{O}(1) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n = int(input())
ans = 0
while n > 3:
n -= 2
ans += 1
if n == 1 or n == 3: ans += 1
else: ans += 2
print(ans)