CODEWITHSUNDEEP
c++algorithm
cha kyungjun
cha kyungjun

Reputation: 11

ACM International Collegiate Programming Contest Asia Regional D Henry

Given a fraction a / b, where a and b are positive integers and a < b, choose the largest unit fraction 1 / x_1 such that 1 / x_1 <= a / b. Then subtract 1 / x_1 from a / b, and repeat the process for the remainder: choose the largest unit fraction 1 / x_2 such that 1 / x_2 <= (a / b) - (1 / x_1). Repeat again until there is no remainder. This procedure will result in a series of unit fractions 1 / x_1, 1 / x_2, 1 / x_3, ... that sum up to the given fraction a / b. This procedure always terminates for any input fraction a / b with a finite number of distinct unit fractions. Write a program that prints out the denominator of the last fraction in the resulting series.

Example:

5/7 = 1/2 + 1/5 + 1/70

Sample input:

3 
4 23
5 7
8 11

Output:

138
70
4070

Code:

My code is for C++ language

#include <iostream>
#include <fstream>
using namespace std;
int testCase;
double a;
double son;
double mom;

int main()
{
    ifstream file("input.txt");
    file >> testCase;

    while (testCase--)
    {
        file >> son;
        file >> mom;

        while (son != 1)
        {
            a = (int)(mom / son) + 1;
            son = (son * a) - mom;
            mom = mom * a;
        }
        cout << mom << endl;
    }
    file.close();
}

I think my algorithm is correct, but my school grading system says it is exceeding the runtime limit. I don't know why.

Upvotes: 1

Views: 101

Answers (1)

Zhuoran He
Zhuoran He

Reputation: 973

You probably forgot to divide mom and son by their greatest common divisor (GCD) at each step. This can probably let certain examples run forever or longer than expected. Check if this is the problem. Also, why do you use double type for son and mom? The numerator and denomenator of a fraction are supposed to be integers. If they can be very big integers, just use unsigned long int or size_t (synonymous in c++). The double data type does not have so many significant digits as size_t.

Upvotes: 1

Related Questions