Sunday, September 25, 2011

ACM - UVA 202 - Repeating Decimals

Problem : 202 - Repeating Decimals
Solution : C++
Hints : http://algorithmist.com/index.php/UVa_202
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <sstream>
#include <set>
#include <math.h>
using namespace std;

int main ()
{
         int numerator;
         int denominator;

         while ( scanf ("%d %d", &numerator, &denominator) != EOF )
         {
             map <int, int> m;
             int quotient = numerator / denominator;
             int mod = (numerator % denominator) * 10;
             string beforeDecimal = "";
             char num [10];
             sprintf (num, "%d", quotient);
             beforeDecimal += num;
             beforeDecimal += '.';
             string afterDecimal = "";
             int repeatTermIndex = 1;

             while ( m [mod] == 0 )
             {
                 m [mod] = repeatTermIndex++;
                 quotient = mod / denominator;
                 mod %= denominator;
                 afterDecimal += (quotient + '0');
                 mod *= 10;
             }
             int parenthesisStart = m [mod];
             int repeatedCycle = repeatTermIndex - parenthesisStart;
             printf ("%d/%d = ", numerator, denominator);
             cout << beforeDecimal;

             if ( afterDecimal.size () == parenthesisStart )
             {
                 for ( int i = 0; i < afterDecimal.size () - 1; i++ )
                     cout << afterDecimal.at (i);
                 cout << "(" << afterDecimal.at (afterDecimal.size () - 1) << ")" << endl;
             }
             else if ( repeatTermIndex > 50 )
             {
                 for ( int i = 0; i < 50; i++ )
                 {
                     if ( i + 1 == parenthesisStart )
                         printf ("(");
                     cout << afterDecimal.at (i);
                 }
                 cout << "...)" << endl;
             }
             else {
                 for ( unsigned int i = 0; i < afterDecimal.size (); i++ )
                 {
                     if ( i + 1 == parenthesisStart )
                         printf ("(");
                     cout << afterDecimal.at (i);
                 }
                 cout << ")" << endl;
             }

             printf (" %d = number of digits in repeating cycle\n\n", repeatedCycle);
         }

     return 0;
}

No comments:

Post a Comment