Pigeon Cells
Autumn Tournament (2015)
Submission name: kletki.cpp
Problem summary
Place K pigeons in N cells in a row, one per cell, spacing them as evenly as possible. Distance between consecutive pigeons means the number of empty cells between them. Find how many consecutive pairs have the smaller gap. See the source note about the original wording.
Source clarification. The official editorial https://infos.infosbg.com/files/Contests/ETI/2015/E/analyses/kletki_analysis.pdf explicitly uses only gap sizes d and d+1 and derives this formula, confirming the intended balanced-gap interpretation. The original statement merely maximizes the minimum gap, which alone is not sufficient to force balancing: N=9,K=4 admits optimal gaps (1,1,3) and (1,2,2), with different counts of minimum gaps. The English summary explicitly states the editorial’s intended balancing condition.
Input
Two integers N and K.
Output
The number of consecutive pigeon pairs at the minimum gap.
Constraints
2 ≤ N ≤ 10000; 1 < K ≤ N.
Worked example
Original statement sample.
Input
8 4
Output
2
Solution analysis
- There are K−1 internal gaps and N−K empty cells. Put pigeons at both ends so all empty cells can contribute to their separation.
- Divide N−K by K−1. If quotient is d and remainder is r, evenly distributing empty cells makes r gaps contain d+1 cells and the other K−1−r gaps contain d cells. Output K−1−r. This is the interpretation used in the official editorial.
- For N=8 and K=4, there are four empty cells and three gaps. Their balanced sizes are 1,1,2, so two pairs have the minimum distance 1.
Why it works
In a balanced placement, gaps differ by at most one. Euclidean division uniquely determines how many have each size: (K−1)d+r=N−K. Thus exactly K−1−r have size d. No placement can have a larger minimum, because that would require at least (K−1)(d+1)>N−K empty cells.
Watch out. Distance counts empty cells, not the difference between occupied indices. The denominator is K−1.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
using namespace std;
int main(){
int cells,pigeons;
cin>>cells>>pigeons;
int gaps=pigeons-1;
int extra=(cells-pigeons)%gaps;
// Each extra empty cell enlarges one of the balanced gaps.
cout<<gaps-extra<<'\n';
}