One Chocolate Break
National Olympiad — National round (2009 season)
Submission name: cut.cpp
Problem summary
A rectangular chocolate bar has M by N unit blocks. Break it once along a straight grid line into two pieces. Find the smallest possible difference between their block counts.
Source clarification. The published bounds permit 1 × 1 although no break into two nonempty pieces exists. The formula follows the intended nontrivial-bar cases; no official impossible-case output is specified.
Input
Two positive integers M and N.
Output
The minimum difference.
Constraints
1 ≤ M, N ≤ 100.
Worked example
An independently prepared example for this explanation.
Input
5 8
Output
0
Solution analysis
- A cut between rows produces areas kN and (M − k)N. Their difference is |M − 2k|N, minimized by choosing a cut nearest the middle.
- If either dimension is even, a middle cut divides the bar exactly in half. If both are odd, a middle cut across M leaves difference N, and one across N leaves difference M.
- For a 5 by 8 bar, split the dimension of length 8 into 4 and 4. Both pieces have 20 blocks, so the answer is 0. For 5 by 7, the best difference is 5.
Why it works
Every straight break preserving whole blocks is parallel to one side. The nearest-middle cut minimizes the difference in each orientation. An even dimension gives zero; with both dimensions odd the two orientation minima are M and N, so their smaller value is optimal.
Watch out. Check both dimensions. A 1 by 1 bar has no legal two-piece break; the published bounds do not exclude it or specify an output for it.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int rows, columns;
cin >> rows >> columns;
// An even dimension permits an exactly central cut.
if (rows % 2 == 0 || columns % 2 == 0) {
cout << 0 << '\n';
} else {
cout << min(rows, columns) << '\n';
}
}