Filling a Strip
National Olympiad — Regional round
Submission name: strip.cpp
Problem summary
A strip has N cells. Put 1 in cell K. Put each successive integer 2…N immediately to the left or right of the already filled contiguous block, whenever that cell exists. Count the resulting fillings.
Input
N and K, supplied as whitespace-separated integers.
Output
The exact number of fillings.
Constraints
1 ≤ N ≤ 50; 1 ≤ K ≤ N.
Worked example
An independently prepared example for this explanation.
Input
6 3
Output
10
Solution analysis
- Exactly K−1 of the N−1 later placements must be to the left; all others go right.
- Choose which steps go left: the answer is C(N−1,K−1). Compute it using Pascal’s triangle.
Why it works
Every binary sequence with the required counts stays within each side’s capacity and uniquely determines a filling. Conversely every filling determines that sequence, giving a bijection.
Complexity: O(N²) time and O(N) memory.
Watch out. Use 64-bit integers; 32-bit counts overflow. N=1 gives one filling.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: Every binary sequence with the required counts stays within each side’s capacity and
// uniquely determines a filling. Conversely every filling determines that sequence, giving a
// bijection.
#include<iostream>
#include<vector>
using namespace std;
int main(){
int n,k;
cin>>n>>k;
vector<long long>c(n+1);
c[0]=1;
for(int row=1;row<n;row++){
for(int j=row;j>=1;j--){
c[j]+=c[j-1];
}
}
cout<<c[k-1]<<'\n';
}