cppAcademy
FROM LEARNING TO COMPETING

Intermediate.
Put your skills to the test.

Bulgarian Informatics Group D · 2007–2026

270 independently explained problems: 54 Municipal, 54 Regional, 105 National Olympiad and 57 Autumn Tournament tasks. Start with the easier tasks and work upwards. Difficulty labels are learning estimates, not official ratings; Group D also includes challenging national-level problems. The six 2017 National tasks shared by Groups C and D use their existing permanent URLs. Years follow Arena’s competition-season labels. Source clarifications and special grader requirements are noted on affected tasks.
GROUP D2021 · MediumBinary Search

Reconstruct the Queue

Autumn Tournament (2021)

Submission name: queue.cpp

Solve in Editor →

Problem summary

A queue initially has at least two students. In each round newcomers enter the gaps starting with the last gap, then skipping K gaps before choosing the next gap towards the front, continuing wherever possible. Given the final length N, find the smallest possible initial length.

Input

N and K.

Output

The minimum possible initial queue length.

Constraints

1 < N < 10^16; 0 ≤ K < 100.

Worked example

Original statement sample.

Input

10 1

Output

5

Solution analysis

  1. A queue of x students has x−1 gaps. Selecting every (K+1)-st gap from the back admits ceil((x−1)/(K+1)) newcomers. Thus a round deterministically changes x to F(x)=x+(x+K−1)/(K+1), using integer division.
  2. F is strictly increasing, since x increases and the number of newcomers never decreases. Therefore a final length y has at most one predecessor. Binary-search x in [2,y−1] for the first F(x)≥y. If equality holds, replace y by x and repeat; if not, y cannot result from another round and is the smallest starting length.
  3. For N=10,K=1, F(7)=7+ceil(6/2)=10, and F(5)=5+ceil(4/2)=7. There is no x with F(x)=5, so the answer is 5. For N=8,K=0, every F(x)=2x−1 is odd; no round can end at 8 and its initial length must already be 8.

Why it works

Strict monotonicity makes each reverse step unique. Every valid earlier starting length must follow this unique predecessor chain. Continuing until the chain has no predecessor therefore returns its smallest attainable initial length.

Complexity: O((K+2)·log²N) time and O(1) space. For x≥2, each forward round increases x by at least x/(2(K+1)), so there are O((K+2)log N) reverse rounds; each binary search costs O(log N).

Watch out. Do not assume an inverse exists for every length. K=0 creates only odd next lengths. Use 64-bit arithmetic; N can exceed a 32-bit integer.

Commented C++17 solution

An independently written complete program with standard headers.

#include<iostream>
using namespace std;
int main(){
    long long length;
    int skipped;
    cin>>length>>skipped;
    auto afterRound=[&](long long previous){
        return previous+(previous+skipped-1)/(skipped+1);
    };
    while(length>2){
        long long low=2,high=length-1;
        while(low<high){
            long long middle=low+(high-low)/2;
            if(afterRound(middle)>=length){
                high=middle;
            }
            else{
                low=middle+1;
            }
        }
        if(afterRound(low)!=length){
            break;
        }
        // The increasing transition has at most one predecessor.
        length=low;
    }
    cout<<length<<'\n';
}

Source: Arena Olimpiici ↗