Two Loaders
National Olympiad — Regional round (2022 season)
Submission name: loader.cpp
Problem summary
Two loaders always make trips together. The weaker can carry one item of weight at most A, the stronger one item of weight at most B. An item heavier than B requires both loaders and occupies a whole trip. Find the minimum trips to move all items.
Input
A B N, followed by N item weights, one per line.
Output
The minimum number of joint trips.
Constraints
1 ≤ A < B ≤ 100; 1 ≤ N ≤ 100,000; 1 ≤ weights ≤ A+B.
Worked example
An independently prepared example for this explanation.
Input
25 60 8 60 20 70 10 30 50 40 80
Output
6
Solution analysis
- Classify items as light (weight ≤ A), medium (A < weight ≤ B), or heavy (weight > B). Every heavy item forces one trip with both loaders.
- Each medium item forces a trip for the stronger loader. Pair as many medium items as possible with light items carried by the weaker loader. Any remaining light items travel two per trip.
- The sample has two heavy, four medium and two light items. Two medium trips also carry the two light items. Thus the answer is 2+4=6 trips.
Why it works
Heavy items cannot share trips. Medium items cannot be paired with each other because only the stronger loader can carry one, so at least their count in trips is needed. Pairing light items with these trips maximizes useful free slots. Remaining light items require and can achieve two per trip, proving optimality.
Watch out. An item exactly A is light; exactly B is medium. Each loader carries at most one item on a solo-load trip.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int a, b, n;
cin >> a >> b >> n;
int light = 0;
int medium = 0;
int heavy = 0;
for (int i = 0; i < n; i++) {
int weight;
cin >> weight;
if (weight <= a) {
light++;
} else if (weight <= b) {
medium++;
} else {
heavy++;
}
}
// Medium-item trips offer one free slot for a light item.
int remainingLight = max(0, light - medium);
cout << heavy + medium + (remainingLight + 1) / 2 << '\n';
}