Full Hotel Rooms
National Olympiad — Municipal round (2018 season)
Submission name: hotel.cpp
Problem summary
Place n students in double and triple rooms. Every used room must be full. Minimize the number of rooms, and report how many rooms of each size are needed.
Input
One integer n.
Output
The number of double rooms followed by the number of triple rooms.
Constraints
2 ≤ n ≤ 100.
Worked example
An independently prepared example for this explanation.
Input
7
Output
2 1
Solution analysis
- Try each possible number of triple rooms from 0 through n/3. Subtract their occupants from n. The remaining students can occupy full double rooms exactly when the remainder is even.
- For each feasible choice, the number of doubles is remainder/2. Keep the combination with the smallest total number of rooms. The tiny input bound makes this direct enumeration easy to check.
- For n=7, one triple room leaves four students for two doubles, using three rooms. Zero triples leaves an odd remainder, while two triples leave one student, so the answer is 2 1.
Why it works
Every valid arrangement has some enumerated number of triple rooms. Once this number is fixed, the number of double rooms is uniquely determined; the parity test accepts exactly the valid arrangements. Selecting their minimum room count is optimal.
Watch out. All rooms must be full: rounding n/3 upward does not by itself give a valid arrangement.
Commented C++17 solution
An independently written complete program with standard headers.
#include <algorithm>
#include <array>
#include <iostream>
#include <numeric>
#include <string>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
int bestRooms = n + 1;
int bestDouble = 0;
int bestTriple = 0;
for (int triples = 0; triples <= n / 3; ++triples) {
int remainder = n - 3 * triples;
// The remaining beds must form completely filled double rooms.
if (remainder % 2 == 0) {
int doubles = remainder / 2;
if (doubles + triples < bestRooms) {
bestRooms = doubles + triples;
bestDouble = doubles;
bestTriple = triples;
}
}
}
cout << bestDouble << ' ' << bestTriple << '\n';
}