Exact Binary Fraction
National Olympiad — National round
Submission name: binfract.cpp
Problem summary
Convert a nonnegative decimal fraction to binary. Use parentheses for its shortest repeating cycle and the shortest possible prefix before that cycle. Omit unnecessary leading/trailing zeros, but print 0 for a zero integer part.
Input
One decimal fraction, with a dot separating the parts.
Output
Its exact binary representation.
Constraints
Each decimal part has at most six digits; the fractional part is nonzero.
Worked example
An independently prepared example for this explanation.
Input
1.5
Output
1.1
Solution analysis
- Convert the integer part by repeated division by two.
- For the fractional numerator over 10^d, repeatedly double the remainder, emit its quotient digit, and retain its remainder. Record the first output position of each remainder.
- A zero remainder terminates; a repeated remainder marks the cycle.
Why it works
The remainder determines every subsequent digit. Its first repetition identifies the earliest periodic suffix and the smallest repeating state cycle; zero gives the finite representation.
Watch out. Floating point cannot detect an exact repeating cycle reliably.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: The remainder determines every subsequent digit. Its first repetition identifies the
// earliest periodic suffix and the smallest repeating state cycle; zero gives the finite
// representation.
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;
int main(){
string s;
cin>>s;
int p=s.find('.'),whole=stoi(s.substr(0,p)),r=stoi(s.substr(p+1)),den=1;
for(int i=p+1;i<(int)s.size();i++){
den*=10;
}
string a;
do{
a+=char('0'+whole%2);
whole/=2;
}
while(whole);
reverse(a.begin(),a.end());
vector<int>pos(den,-1);
string f;
while(r&&pos[r]<0){
pos[r]=f.size();
r*=2;
f+=char('0'+r/den);
r%=den;
}
cout<<a<<'.';
if(!r){
cout<<f;
}
else{
cout<<f.substr(0,pos[r])<<'('<<f.substr(pos[r])<<')';
}
cout<<'\n';
}