Paper Frame
Autumn Tournament (2013)
Submission name: border.cpp
Problem summary
Cover the four sides of an a by b rectangle using strips of length k. A strip may remain whole or be cut into pieces of positive integer length. Each side may contain any number of whole strips but at most one piece from a cut strip. Find the minimum number of original strips needed.
Input
Three integers a, b, k.
Output
The minimum number of strips.
Constraints
1 ≤ a, b, k ≤ 100000.
Worked example
Original statement sample.
Input
33 41 8
Output
19
Solution analysis
- A side of length s must use floor(s/k) whole strips and, when s mod k is nonzero, one remaining piece of that length. Using fewer whole strips would require a single piece longer than k, which is impossible. Add the whole-strip counts for all four sides.
- Only four remaining pieces need packing into original strips. For every subset of these pieces, calculate its total length. A subset fits in one strip exactly when its total is at most k. Let dp[mask] be the minimum strips for the pieces in mask; try every nonempty fitting submask as the contents of one final strip.
- For 33, 41, 8, whole strips contribute 2·4 + 2·5 = 18. The four remaining lengths are all 1, so one more strip suffices and the answer is 19.
Why it works
Every side requires the stated whole strips and remaining piece. Any feasible treatment of the remaining pieces partitions them into subsets of total length at most k. Conversely, each such subset can be cut from one strip. The recurrence tries every possible last subset, so induction on the number of pieces proves dp optimal; adding the compulsory whole strips gives the global optimum.
Watch out. Do not just round up the total perimeter: the limit of one cut piece on each side constrains packing. Ignore zero remainders.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
int main(){
int a,b,k;
cin>>a>>b>>k;
vector<int>pieces;
int whole=0;
for(int side:{a,b,a,b}){
whole+=side/k;
if(side%k!=0){
pieces.push_back(side%k);
}
}
int states=1<<static_cast<int>(pieces.size());
vector<int>sum(states,0);
vector<int>dp(states,5);
dp[0]=0;
for(int mask=1;mask<states;++mask){
for(int i=0;i<static_cast<int>(pieces.size());++i){
if((mask&(1<<i))!=0){
sum[mask]+=pieces[i];
}
}
// Select all pieces cut from the final strip.
for(int part=mask;part!=0;part=(part-1)&mask){
if(sum[part]<=k){
dp[mask]=min(dp[mask],dp[mask^part]+1);
}
}
}
cout<<whole+dp[states-1]<<'\n';
}