Albums for a Stamp Collection
National Olympiad — Municipal round (2019 season)
Submission name: postagestamps.cpp
Problem summary
Each album has m two-sided sheets and p×q stamp slots per page. Different denominations cannot share a page. Find the fewest albums.
Input
n m p q followed by n denominations.
Output
Minimum album count.
Constraints
1 ≤ n ≤ 10^6; 1 ≤ m ≤ 40; 2 ≤ p,q ≤ 10; denominations 1…1000.
Worked example
Input and output for the worked example discussed below.
Input
11 2 2 3 20 25 20 20 50 20 10 20 20 20 10
Output
2
Solution analysis
- Count each denomination in a fixed-size array. A page holds pq stamps, but unused slots cannot be filled by another denomination.
- Denomination v requires ceil(count[v]/pq) pages. Add these page requirements, then take ceil(totalPages/(2m)), since a sheet has two pages.
- Seven value-20 stamps in the sample need two pages; values 10,25,50 each need one. Five pages in four-page albums require two albums.
Why it works
Every denomination needs at least its rounded page count and exactly that allocation is feasible.
Complexity: O(n+1000) time and O(1000) space.
Watch out. Round upward separately for each denomination and count both sides of a sheet.
Commented C++17 solution
An independently written complete program with standard headers.
// Every denomination needs at least its rounded page count and exactly that allocation is feasible.
#include<iostream>
#include<vector>
using namespace std;
int main(){
int n,sheets,rows,slots;
cin>>n>>sheets>>rows>>slots;
vector<int>frequency(1001);
while(n--){
int value;
cin>>value;
frequency[value]++;
}
int pages=0;
int capacity=rows*slots;
for(int count:frequency){
pages+=(count+capacity-1)/capacity;
}
cout<<(pages+2*sheets-1)/(2*sheets)<<'\n';
}