Chemical Laboratory
National Olympiad — National round (2016 season)
Submission name: chemlab.cpp
Problem summary
Tubes hold substances numbered 0–9. For g = 1, 2, …, n, form g consecutive equal groups of size floor(n/g), leaving any unused tubes at the end unchanged. For each group, take the substance s in its left middle tube. If s is nonzero, add s modulo 10 to each tube whose one-based position within the group is divisible by s. The amount s is fixed for that group’s operation. Find the final sum of substance numbers.
Input
n followed by a string of n digits without spaces.
Output
The sum of all final tube digits.
Constraints
1 ≤ n ≤ 10,000.
Worked example
An independently prepared example for this explanation.
Input
8 70389411
Output
37
Solution analysis
- Process group counts in their stated order because changes affect later stages. At a fixed count g, the group length is n / g and group j begins at j × length.
- The left middle has offset (length − 1) / 2. Save its current digit s before changing any tube. For s > 0, update local positions s, 2s, 3s, … up to length, replacing each digit by (digit + s) % 10.
- In the sample the first whole-row group uses substance 8, changing the last digit from 1 to 9. At two groups the last group uses 4 and changes that digit to 3. Later two final digits become 2 and 4, leaving [7, 0, 3, 8, 9, 4, 2, 4], whose sum is 37.
Why it works
At each stage the division and group starts produce exactly the maximal equal-sized consecutive groups specified. The saved middle digit is the substance selected before that group’s mixing, and the update loop visits exactly its divisible local positions. Thus each group operation is simulated correctly. Induction over all groups and stages gives the final tube contents, whose sum is output.
Watch out. Positions restart from one in every group. Choose the left middle for even lengths. Substance zero must not be used as a divisor, and the selected substance must be saved before updates.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
string digits;
cin >> n >> digits;
vector<int> tube(n);
for (int i = 0; i < n; ++i) {
tube[i] = digits[i] - '0';
}
for (int groups = 1; groups <= n; ++groups) {
int length = n / groups;
for (int group = 0; group < groups; ++group) {
int start = group * length;
// Save the middle substance before any tube in this group is changed.
int substance = tube[start + (length - 1) / 2];
if (substance == 0) {
continue;
}
for (int position = substance; position <= length; position += substance) {
int index = start + position - 1;
tube[index] = (tube[index] + substance) % 10;
}
}
}
int total = 0;
for (int substance : tube) {
total += substance;
}
cout << total << '\n';
return 0;
}