Restaurant Seating
National Olympiad — Regional round (2014 season)
Submission name: rest.cpp
Problem summary
Arrange one row of tables along a restaurant wall. Chairs occupy the two opposite long sides; each chair needs X centimetres and each table side holds at most K chairs. Adjacent tables and both end walls need 50 cm gaps. Maximize total chairs and report the minimum tables needed for that capacity.
Input
A B C D describe side lengths A metres B centimetres and C metres D centimetres; then X and K.
Output
Maximum chairs on the first line; required tables on the second.
Constraints
0 < A,C,X,K ≤ 1000; 0 ≤ B,D < 100.
Worked example
An independently prepared example for this explanation.
Input
6 10 5 0 50 3
Output
16 3
Solution analysis
- Use the longer wall, converted to centimetres. With t tables there are t+1 gaps, consuming 50*(t+1) cm. Remaining length can hold floor(remaining/X) chair positions on each side.
- Each table side also has capacity K, so positions per side cannot exceed t*K. The achievable total is twice the smaller bound. Enumerate possible t and keep the largest total; retaining the earliest t gives the fewest tables.
- For a 610 cm wall, X=50 and K=3, three tables leave 410 cm after four gaps. That fits eight chairs per side (3+3+2), yielding 16 chairs on three tables.
Why it works
For fixed t, both the length bound and the per-table capacity bound are necessary. Any number of positions up to their minimum can be distributed across t tables, with at most K per side, and fitted within the remaining wall length. Thus the formula is attainable. A longer wall never reduces capacity, and enumerating all feasible table counts finds the maximum and its smallest t.
Watch out. Reserve gaps at both ends as well as between tables. Chairs count on both sides. Update table count only for a strictly larger capacity.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int a, b, c, d, width, capacity;
cin >> a >> b >> c >> d >> width >> capacity;
int length = max(a * 100 + b, c * 100 + d);
int bestChairs = 0;
int bestTables = 0;
for (int tables = 1; 50 * (tables + 1) <= length; tables++) {
// Reserve one gap at each end and one between adjacent tables.
int remaining = length - 50 * (tables + 1);
int perSide = min(tables * capacity, remaining / width);
int chairs = 2 * perSide;
if (chairs > bestChairs) {
bestChairs = chairs;
bestTables = tables;
}
}
cout << bestChairs << '\n' << bestTables << '\n';
}