Scouts Share Mushrooms
National Olympiad — Regional round (2013 season)
Submission name: scout.cpp
Problem summary
Place each scout’s mushrooms consecutively in a single row. Choose the largest spacing such that taking every spacing-th mushroom can supply k mushrooms, stopping after exactly k removals. Print how many each scout retains.
Input
n and k, then n mushroom counts in scout order.
Output
n remaining counts on one line, separated by spaces without a trailing space.
Constraints
1 ≤ n,k ≤ 100; each count is 0…100; k is no greater than the total.
Worked example
An independently prepared example for this explanation.
Input
10 7 4 1 2 2 0 3 5 1 1 5
Output
3 1 1 1 0 2 4 0 1 4
Solution analysis
- Let S be the total count. To select k equally spaced positions, spacing s must satisfy k*s ≤ S, so the largest possible spacing is floor(S/k).
- Among the first p positions, the number removed is min(k,floor(p/s)). For a scout whose block ends at p and starts just after q, subtract the difference of these prefix removal counts.
- In the sample S=24 and k=7, so s=3. Remove positions 3,6,9,12,15,18,21, then stop; position 24 stays.
Why it works
The largest feasible spacing is floor(S/k) because k times any larger spacing exceeds S. Removed positions are exactly s,2s,…,ks, so the capped prefix formula counts them precisely. Taking its difference over each scout’s block gives exactly that scout’s removals.
Watch out. Stop after k removals. Without the cap, extra multiples near the row’s end would be removed incorrectly. Scouts may have zero mushrooms.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n, k;
cin >> n >> k;
vector<int> mushrooms(n);
int total = 0;
for (int &count : mushrooms) {
cin >> count;
total += count;
}
int spacing = total / k;
int prefix = 0;
for (int i = 0; i < n; i++) {
// Capped prefix counts stop removing mushrooms after the kth one.
int before = min(k, prefix / spacing);
prefix += mushrooms[i];
int after = min(k, prefix / spacing);
if (i > 0) {
cout << ' ';
}
cout << mushrooms[i] - (after - before);
}
cout << '\n';
}