Equal Numbers After Splitting Digits
Национална олимпиада - Национален кръг 2026
Submission name: great.cpp
Problem summary
Split a decimal string into two nonempty parts representing the same integer. Leading zeros in the right part are allowed. Print the left part length, or −1 if impossible.
Input
T followed by T decimal strings.
Output
A valid left length, or −1, for each string.
Constraints
1 ≤ T ≤ 10; each string has 1 to 400000 digits and starts with a nonzero digit.
Worked example
The worked example illustrates the rule described in the analysis.
Input
3 123123 123122 120012
Output
3 -1 2
Solution analysis
- The left part has no leading zeros. The right part must therefore consist of some zeros followed by an exact copy of the left part. If the copy has length k, the string has the form A + zero padding + A, so k≤floor(L/2).
- Start at index floor(L/2) and skip zeros to find the first nonzero digit of the right copy. This position is forced: the zero padding covers the midpoint, and the repeated copy begins with a nonzero digit.
- Let k=L−start. Reject if k is zero or exceeds start. Check that positions k through start−1 are all zero, then compare the first k digits with the final k digits.
- For 120012, the midpoint is index 3. Skip its zero to reach index 4, so k=2. The middle 00 is zero padding and both copies are 12. For 123122, the copies differ.
Why it works
Any valid string A0…0A has its first nonzero position at or after the midpoint exactly at the final A. Thus the algorithm finds the unique candidate length. The padding and equality checks are necessary and sufficient for that candidate to represent equal integers.
Watch out. Odd lengths can be valid. Do not reject right-side leading zeros. Avoid numeric conversion, which overflows on long inputs. Both parts must be nonempty.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: Any valid string A0…0A has its first nonzero position at or after the midpoint exactly at
// the final A. Thus the algorithm finds the unique candidate length.
#include<algorithm>
#include<array>
#include<cstdint>
#include<iostream>
#include<numeric>
#include<string>
#include<vector>
using namespace std;
int splitLength(const string&digits){
int length=static_cast<int>(digits.size());
int start=length/2;
while(start<length&&digits[start]=='0'){
++start;
}
int size=length-start;
if(size==0||size>start){
return -1;
}
for(int i=size;i<start;++i){
if(digits[i]!='0'){
return -1;
}
}
for(int i=0;i<size;++i){
if(digits[i]!=digits[start+i]){
return -1;
}
}
return size;
}
int main(){
int tests;
cin>>tests;
while(tests--){
string digits;
cin>>digits;
cout<<splitLength(digits)<<'\n';
}
}