Logs and Cuts
National Olympiad — Municipal round (2019 season)
Submission name: timber.cpp
Problem summary
Cutting logs X times produces N pieces, with each cut splitting one piece into two. Find the original number of logs and divide those logs between two carts as evenly as possible, with the first cart carrying no more than the second.
Input
Two integers X and N.
Output
The original number of logs on the first line; the two cart loads on the second line.
Constraints
1 ≤ X ≤ 100000000; 1 ≤ N ≤ 1000000000; X < N.
Worked example
An independently prepared example for this explanation.
Input
18 26
Output
8 4 4
Solution analysis
- Every cut increases the total number of pieces by exactly one. If there were L original logs, the final piece count is L+X, so L=N−X.
- To minimize the load difference, give floor(L/2) logs to the first cart and the remaining logs to the second. This produces a difference of zero for even L and one for odd L.
- For X=18 and N=26, there were 8 logs, split as 4 and 4. For X=1 and N=2, there was just one log; the required order of loads gives 0 and 1.
Why it works
The piece-count change per cut proves L=N−X. Two nonnegative integer loads summing to L cannot differ by less than zero if L is even or one if L is odd. The floor-and-remainder division attains these bounds and has the required order.
Watch out. A cart may carry zero logs, as in the second sample. Do not confuse cuts with pieces.
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() {
long long cuts, pieces;
cin >> cuts >> pieces;
// Each cut adds exactly one piece to the original log count.
long long logs = pieces - cuts;
long long first = logs / 2;
cout << logs << '\n';
cout << first << ' ' << logs - first << '\n';
}