Spring Tablecloths
National Olympiad — National round (2016 season)
Submission name: cloth.cpp
Problem summary
An even number m of rectangular tables all have length a; half have width b and half width c. Choose one fabric roll and cut all tablecloths without waste using strips across a roll of width a, or paired cloths across a roll of width b + c. Among rolls with enough length, choose the uniquely cheapest fabric. Prices are integer stotinki per centimetre of roll length.
Source clarification. The introductory prose mentions price per linear metre, but the formal constraints specify stotinki per centimetre, and the examples require that unit (500 cm × 125 = 625 lv). This solution follows the formal constraints and examples. It uses the two waste-free strip layouts described by the statement.
Input
m a b c; k; then k records giving fabric name, roll width, price per centimetre and available length in centimetres.
Output
If impossible print IMPOSSIBLE. Otherwise print the fabric name; its cost with lv and/or st units; and required length with m and/or sm units. Omit a zero remainder unit and omit a zero leading unit.
Constraints
2 ≤ m ≤ 100 and m even; 1 ≤ k ≤ 30; dimensions 1–10,000 cm; roll width ≤ 20,000 cm; price 1–10,000 stotinki/cm; available length ≤ 10,000,000 cm; names have 2–20 characters.
Worked example
An independently prepared example for this explanation.
Input
10 100 70 50 4 first 100 250 100 second 120 125 1000 third 120 780 1000 four 100 663 1000
Output
second 625 lv 5 m
Solution analysis
- If roll width equals a, every tablecloth can span the roll width. The purchased length is (m / 2) × (b + c). If roll width equals b + c, place one narrow and one wide cloth side by side per pair; the length is (m / 2) × a.
- Ignore rolls whose width matches neither layout or whose available length is insufficient. For each remaining roll, multiply the required centimetres by its integer price to obtain cost in stotinki. Keep the cheapest candidate.
- In the sample the second roll has width 120 = 70 + 50, so five pairs need 5 × 100 = 500 cm. At 125 stotinki/cm the cost is 62,500 stotinki, or 625 lv, and the length is 5 m. The first roll is too short and the other feasible rolls cost more.
Why it works
Each stated cutting layout covers every tablecloth exactly and fills the full width and purchased length, producing no waste. Its length follows from the number of individual cloths or pairs. The algorithm considers each permitted roll and layout, rejects exactly those without enough length, and selects the minimum cost among the feasible choices. Unit decomposition changes only presentation.
Watch out. Use centimetres and stotinki throughout. Check available length before comparing price. Output unit labels exactly, and omit zero remainder units.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <string>
#include <limits>
using namespace std;
void printUnits(long long value, const string &large, const string &small) {
if (value >= 100) {
cout << value / 100 << ' ' << large;
if (value % 100 != 0) {
cout << ' ';
}
}
if (value % 100 != 0 || value == 0) {
cout << value % 100 << ' ' << small;
}
cout << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long m, a, b, c;
cin >> m >> a >> b >> c;
int k;
cin >> k;
long long bestCost = numeric_limits<long long>::max();
long long bestLength = 0;
string bestName;
for (int i = 0; i < k; ++i) {
string name;
long long width, price, available;
cin >> name >> width >> price >> available;
long long required = -1;
// Two waste-free orientations determine the required roll length.
if (width == a) {
required = (m / 2) * (b + c);
}
if (width == b + c) {
required = (m / 2) * a;
}
if (required >= 0 && required <= available && required * price < bestCost) {
bestCost = required * price;
bestLength = required;
bestName = name;
}
}
if (bestName.empty()) {
cout << "IMPOSSIBLE\n";
} else {
cout << bestName << '\n';
printUnits(bestCost, "lv", "st");
printUnits(bestLength, "m", "sm");
}
return 0;
}