PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: mexomerf
Tester: yash_daga
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
There are N urinals. Two urinals in use must have another one between them.
Find the maximum and minimum number of people who can use these urinals simultaneously, while leaving no place for anyone else to join.
EXPLANATION:
For the maximum number, it’s best for the people to use alternating urinals.
That is, urinals 1, 3, 5, \ldots
The maximum number that can be used this way is \left\lceil\frac{N}{2} \right\rceil.
The minimum requires a bit more thought.
Notice that:
- At least one of the first two urinals must be used; otherwise someone extra can use urinal 1.
- Among any three consecutive urinals, at least one must be used; otherwise the middle one would be free.
- At least one of the last two urinals must be used, just as in the first point.
With this in mind, it can be seen that the optimal pattern is
010010010\ldots 010010
where 1 denotes a used urinal.
Since N \leq 1000 you can just simulate this process and count the number of urinals used.
Alternately, you can see that the number of ones will be exactly \left\lceil\frac{N}{3} \right\rceil.
Here, \left\lceil \ \right\rceil denotes the ceiling function.
TIME COMPLEXITY:
\mathcal{O}(1) per testcase.
CODE:
Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
print((n+1)//2, (n+2)//3)