The Cheapest Paint Shop
National Olympiad — Municipal round (2016 season)
Submission name: paint.cpp
Problem summary
Four identical walls have dimensions a by b. Each of three shops sells one type of paint can with a stated coverage and price. Buy enough whole cans from one shop to paint all four walls. Find the minimum total cost.
Input
Three lines with coverage s, price in leva lv and stotinki st; then wall dimensions a b.
Output
The minimum cost as two integers: leva and stotinki.
Constraints
1 ≤ s ≤ 100; 0 ≤ lv ≤ 100; 1 ≤ st ≤ 100; 1 ≤ a, b ≤ 25.
Worked example
An independently prepared example for this explanation.
Input
3 2 80 5 4 20 4 3 50 4 7
Output
96 60
Solution analysis
- The required area is four times a × b. A shop covering s square metres per can needs ceiling(area / s) cans, computed exactly as (area + s − 1) / s.
- Convert every can price to stotinki using 100 × lv + st. Multiply by the required number of cans and compare the three totals. Convert the minimum back with division and remainder by 100.
- The example needs 4 × 4 × 7 = 112 square metres. The three shops require 38, 23 and 28 cans, costing 10640, 9660 and 9800 stotinki. The minimum is therefore 96 leva and 60 stotinki.
Why it works
For each shop, ceiling division is the least whole number of cans with sufficient coverage. All cans have nonnegative price, so this gives that shop’s minimum cost. Comparing all three permitted shops selects the overall minimum, and integer currency conversion preserves its exact value.
Watch out. Do not round the number of cans down. Compare total costs, not price per square metre. Avoid floating-point money.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <algorithm>
#include <limits>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int coverage[3];
int price[3];
for (int i = 0; i < 3; ++i) {
int leva, stotinki;
cin >> coverage[i] >> leva >> stotinki;
price[i] = 100 * leva + stotinki;
}
int a, b;
cin >> a >> b;
int area = 4 * a * b;
int best = numeric_limits<int>::max();
for (int i = 0; i < 3; ++i) {
// Ceiling division buys the least whole number of cans covering the area.
int cans = (area + coverage[i] - 1) / coverage[i];
best = min(best, cans * price[i]);
}
cout << best / 100 << ' ' << best % 100 << '\n';
return 0;
}