Maximum Product after Cutting a Digit Ring
National Olympiad — Regional round (2015 season)
Submission name: maxpro.cpp
Problem summary
Join the decimal strings of two positive integers into a ring. Cut it at two different boundaries to make two nonempty numbers, and maximize their product.
Input
Two positive integers less than 10^15.
Output
The exact maximum product.
Constraints
Each input has at most 15 digits; the combined ring has at most 30 digits.
Worked example
Input and output for the worked example discussed below.
Input
456 70
Output
42270
Solution analysis
- Choose where the first resulting strip begins: this is a rotation of the combined digit string. Then choose the first strip’s length from 1 through L−1; the remaining digits form the second strip. These two choices cover every pair of cuts.
- Individual strips and their products may exceed 64-bit range. Represent them as decimal strings and multiply by the schoolbook algorithm: accumulate products of digit pairs, then propagate carries from right to left.
- Normalize leading zeros in each product and compare products first by digit count, then lexicographically. These comparisons exactly match numeric order for nonnegative decimal integers.
- For 456 and 70, rotate the ring 45670 to 70456 and cut it as 7045 and 6. Their product is 42270; all other rotations and cuts give no larger value.
Why it works
Every two-cut partition can be described by starting at one cut and reading one nonempty strip followed by the other, so rotation-plus-length enumeration is complete. Decimal multiplication computes every product exactly, and numeric comparison retains its maximum. Reversed naming of the two strips only repeats a candidate harmlessly.
Watch out. Do not concatenate numerically or use long long for products up to 30 digits. Consider cuts crossing the original join. Both strips must remain nonempty.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
using namespace std;
string multiply(const string&a,const string&b){
vector<int>digits(a.size()+b.size(),0);
for(int i=int(a.size())-1;i>=0;i--){
for(int j=int(b.size())-1;j>=0;j--){
digits[i+j+1]+=(a[i]-'0')*(b[j]-'0');
}
}
for(int i=int(digits.size())-1;i>0;i--){
digits[i-1]+=digits[i]/10;
digits[i]%=10;
}
string result;
for(int digit:digits){
if(digit!=0||!result.empty()){
result+=char('0'+digit);
}
}
return result.empty()?"0":result;
}
int main(){
string first;
string second;
cin>>first>>second;
string ring=first+second;
string best="0";
for(size_t start=0;start<ring.size();start++){
string rotation=ring.substr(start)+ring.substr(0,start);
for(size_t length=1;length<ring.size();length++){
// Enumerate both cut boundaries and multiply without fixed-width overflow.
string product=multiply(rotation.substr(0,length),rotation.substr(length));
if(product.size()>best.size()||(product.size()==best.size()&&product>best)){
best=product;
}
}
}
cout<<best<<'\n';
}