Sum of Repeating Base-b Numbers
National Olympiad — National round (2018 season)
Submission name: ratsum.cpp
Problem summary
Add two nonnegative rational numbers written in base b, with optional nonrepeating and parenthesized repeating fractional parts. Output the shortest normal notation: no unnecessary leading/trailing zeroes, minimal preperiod and period, and no repeating (b−1) tail.
Input
Base b in decimal, followed by two valid base-b representations. Digits above 9 use A…Z.
Output
The normal base-b representation of their sum.
Constraints
2 ≤ b ≤ 36; each input representation has at most 1000 characters.
Worked example
An independently prepared example for this explanation.
Input
5 1242.1(2) 002.322(22)
Output
1300
Solution analysis
- Align the integer parts and use T=max(nonrepeating lengths) fractional digits before the shared periodic tail. Each input’s digits after T are periodic; a missing period is treated as the repeating digit zero. Their joint period has length L=lcm(period lengths), at most one million.
- At the start of the infinite tail, determine the carry by comparing its repeated digitwise sums to the all-(b−1) sequence. The first unequal position determines whether the tail sum is below or above one; exact equality means one. Add one whole period right-to-left with that carry. If all resulting digits are b−1, replace the tail by zero and increase the outgoing carry: this is the terminating representation of a repeating maximal-digit tail.
- Propagate the carry backward through the T finite fractional digits and then the integer digits. Minimize a nonzero output period using the prefix function, and move its boundary left while its final periodic digit matches the last finite digit, rotating the period. In the example the two base-5 numbers represent 197.3 and 2.7 in decimal; their sum is 200 decimal, or 1300 base 5.
Why it works
A repeated length-L digit-sum block represents its weighted integer value divided by bᴸ−1. Comparing its digits to b−1 therefore gives its integer carry, except that an all-maximal result is normalized upward afterward. Right-to-left base-b addition with this periodic carry satisfies the same recurrence at both ends of the period and hence represents the infinite sum exactly. Finite-part addition is ordinary positional addition. The prefix function finds the shortest repeating block; shifting matching boundary digits left removes every redundant preperiod digit. Removing zero tails and leading zeroes then yields the shortest conventional representation.
Watch out. An exact tail sum of one carries into the finite part. Normalize repeating maximal digits such as decimal 0.(9). Periods start at different offsets when finite fractional lengths differ. Avoid expanding the rational denominator.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
#include<numeric>
#include<string>
#include<vector>
// Algorithm: Align the integer parts and use T=max(nonrepeating lengths) fractional digits
// before the shared periodic tail.
using namespace std;
int digit(char symbol){
return symbol<='9'?symbol-'0':symbol-'A'+10;
}
char symbol(int value){
return static_cast<char>(value<10?'0'+value:'A'+value-10);
}
struct Number{
string integer,finite,period;
explicit Number(const string&text){
size_t point=text.find('.');
if(point==string::npos){
integer=text;
}
else{
integer=text.substr(0,point);
size_t opening=text.find('(',point);
if(opening==string::npos){
finite=text.substr(point+1);
}
else{
finite=text.substr(point+1,opening-point-1);
period=text.substr(opening+1,text.size()-opening-2);
}
}
if(period.empty()){
period="0";
}
}
int fractional(int position)const{
if(position<static_cast<int>(finite.size())){
return digit(finite[position]);
}
return digit(period[(position-finite.size())%period.size()]);
}
};
int main(){
int base;
string first,second;
cin>>base>>first>>second;
Number a(first),b(second);
int finiteLength=static_cast<int>(max(a.finite.size(),b.finite.size()));
int periodLength=lcm(static_cast<int>(a.period.size()),static_cast<int>(b.period.size()));
vector<int>sums(periodLength),period(periodLength);
for(int i=0;i<periodLength;i++){
sums[i]=a.fractional(finiteLength+i)+b.fractional(finiteLength+i);
}
int carry=1;
for(int value:sums){
if(value!=base-1){
carry=value>base-1;
break;
}
}
for(int i=periodLength-1;i>=0;i--){
int value=sums[i]+carry;
period[i]=value%base;
carry=value/base;
}
if(all_of(period.begin(),period.end(),[&](int value){
return value==base-1;
})){
fill(period.begin(),period.end(),0);
carry++;
}
string finite(finiteLength,'0');
for(int i=finiteLength-1;i>=0;i--){
int value=a.fractional(i)+b.fractional(i)+carry;
finite[i]=symbol(value%base);
carry=value/base;
}
string integer;
int integerLength=static_cast<int>(max(a.integer.size(),b.integer.size()));
for(int i=0;i<integerLength||carry;i++){
int value=carry;
if(i<static_cast<int>(a.integer.size())){
value+=digit(a.integer[a.integer.size()-1-i]);
}
if(i<static_cast<int>(b.integer.size())){
value+=digit(b.integer[b.integer.size()-1-i]);
}
integer+=symbol(value%base);
carry=value/base;
}
while(integer.size()>1&&integer.back()=='0'){
integer.pop_back();
}
reverse(integer.begin(),integer.end());
vector<int>prefix(periodLength);
for(int i=1;i<periodLength;i++){
int j=prefix[i-1];
while(j&&period[i]!=period[j]){
j=prefix[j-1];
}
if(period[i]==period[j]){
j++;
}
prefix[i]=j;
}
int length=periodLength-prefix.back();
if(periodLength%length){
length=periodLength;
}
period.resize(length);
bool zeroTail=all_of(period.begin(),period.end(),[](int value){
return value==0;
});
int offset=0;
while(!finite.empty()){
int previous=(offset+length-1)%length;
if(digit(finite.back())!=period[previous]){
break;
}
finite.pop_back();
offset=previous;
}
cout<<integer;
if(!finite.empty()||!zeroTail){
cout<<'.'<<finite;
if(!zeroTail){
cout<<'(';
for(int i=0;i<length;i++){
cout<<symbol(period[(offset+i)%length]);
}
cout<<')';
}
}
cout<<'\n';
}