Queue
Autumn Tournament (2021)
Submission name: line.cpp
Problem summary
A queue repeatedly grows by inserting exactly one new student into each gap between consecutive students. Given its final size N, find the smallest possible initial size. Zero insertion rounds are possible.
Input
One integer N.
Output
The minimum possible initial queue size.
Constraints
1 < N < 10000.
Worked example
Original statement, example 1.
Input
29
Output
8
Solution analysis
- A queue of x students has x − 1 gaps. After one round its size becomes 2x − 1, which is odd.
- Reverse this operation whenever the current size is odd: replace it with (N + 1)/2. Stop at an even size, because it cannot be the result of a round.
- For 29, reversing gives 15 and then 8. Each reversal gives a smaller possible starting queue, and 8 cannot be reversed further.
Why it works
An odd final size has exactly one possible predecessor, (N + 1)/2; an even size has none. Each reversal strictly decreases a size greater than one. Consequently all possible earlier sizes lie on this unique chain, and its last size is the smallest.
Watch out. Do not reverse an even number. A final size already even is itself the answer.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
using namespace std;
int main(){
int n;
cin>>n;
// Undo the unique possible final insertion round.
while(n%2==1){
n=(n+1)/2;
}
cout<<n<<'\n';
}