Ship Full Containers
National Olympiad — National round (2024 season)
Submission name: shipment.cpp
Problem summary
Each parcel has a recipient. Containers hold either M or K parcels (M>K), must be full, and cannot mix recipients. A recipient is satisfied when fewer than K of their parcels are left unshipped. Minimize the total number of containers.
Input
N M K, then N recipient identifiers.
Output
The minimum total number of containers.
Constraints
1 ≤ N ≤ 10^6; 1 ≤ K < M ≤ 10^6; recipient IDs are in [1,10^6].
Worked example
An independently prepared example for this explanation.
Input
16 5 2 1 2 3 2 2 3 2 2 4 4 2 2 3 4 3 3
Output
4
Solution analysis
- First count parcels per recipient, since recipients are independent. For a recipient with c parcels, use as many M-sized containers as possible, then as many K-sized containers as possible in the remainder.
- If x large containers are chosen, satisfaction forces exactly floor((c−xM)/K) small containers in an optimum: fewer leave at least K parcels, and more cannot be filled. Increasing x by one decreases that floor by at least one because M>K, so total container count never increases.
- Thus use floor(c/M)+floor((c mod M)/K) containers. In the sample recipient counts are 1,7,5,3: their needs are 0,2,1,1 containers, totaling four.
Why it works
For each feasible large-container count x, the required small count is floor((c−xM)/K). Replacing the option x by x+1 changes total count by 1 plus a floor decrease of at least one, so the maximum possible x is optimal. Summing independent recipient optima is globally optimal.
Watch out. A recipient with fewer than K parcels needs zero containers. Never mix parcels of different recipients, and do not require every parcel to be shipped.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, large, small;
cin >> n >> large >> small;
vector<int> count(1000001, 0);
for (int i = 0; i < n; i++) {
int recipient;
cin >> recipient;
count[recipient]++;
}
long long answer = 0;
for (int parcels : count) {
// Maximizing full large containers cannot increase the total count.
answer += parcels / large + (parcels % large) / small;
}
cout << answer << '\n';
}