Kap and Rikar
National Olympiad — Regional round (2011 season)
Submission name: kapri.cpp
Problem summary
For each number K with L decimal digits, square it. Split the square into its last L digits and the remaining leading digits (one fewer than L when the square has only 2L − 1 digits). Count numbers for which the two parts sum to K.
Input
N followed by N numbers K.
Output
The number of successful values.
Constraints
1 ≤ N ≤ 100; 1 ≤ K ≤ 10^6.
Worked example
An independently prepared example for this explanation.
Input
4 5 8 297 7
Output
1
Solution analysis
- Find the power p = 10^L immediately greater than K. This identifies the split position regardless of the square’s length.
- For square = K × K, the right part is square % p and the left part is square / p. Test whether their sum equals K and count each successful input occurrence.
- For K = 297, p = 1000 and K² = 88209. Splitting gives 88 and 209, whose sum is 297. The other three sample numbers fail, so the answer is one.
Why it works
Division and remainder by 10^L uniquely separate the square into its last L digits and all earlier digits, including a zero-valued leading part when appropriate. The equality test is exactly the stated success condition, so counting its true results gives the answer.
Watch out. The square can reach 10^12, so use 64-bit multiplication. Count repeated successful input values separately.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
using namespace std;
int main() {
int count;
cin >> count;
int answer = 0;
for (int i = 0; i < count; i++) {
long long number;
cin >> number;
long long power = 10;
while (power <= number) {
power *= 10;
}
// Division and remainder by 10^L split off exactly L digits.
long long square = number * number;
if (square / power + square % power == number) {
answer++;
}
}
cout << answer << '\n';
}