An Overcrowded Aquarium
National Olympiad — Municipal round (2010 season)
Submission name: aquarium.cpp
Problem summary
Each goldfish needs at least 3 liters of water. Given an aquarium volume V and N fish, decide whether it is overcrowded and find the minimum number of fish to move elsewhere.
Input
Two integers V and N.
Output
YES and the number to move on one line if overcrowded; otherwise NO.
Constraints
1 ≤ V, N ≤ 10^18.
Worked example
An independently prepared example for this explanation.
Input
12 5
Output
YES 1
Solution analysis
- The maximum number of fish that can remain is floor(V/3). Integer division computes this directly.
- Compare N against this capacity. If N is larger, move exactly N − capacity fish. Otherwise the aquarium is already large enough.
- With 12 liters, four fish can remain. Starting with five requires moving one, so the output is YES 1.
Why it works
Every remaining fish needs 3 liters, so at most floor(V/3) can stay. Keeping that many is feasible. Thus an excess of N − floor(V/3) is both necessary and sufficient when positive, and no move is needed otherwise.
Watch out. Use 64-bit integers. Dividing V by 3 avoids multiplying a potentially large fish count.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
using namespace std;
int main() {
long long volume, fish;
cin >> volume >> fish;
// Integer division gives the greatest feasible number of fish.
long long capacity = volume / 3;
if (fish > capacity) {
cout << "YES " << fish - capacity << '\n';
} else {
cout << "NO\n";
}
}