FracSum

TCCC06 Round 2B · 2006-08-22 · by dgoodman

TCCC06 Round 2B · 2006-08-22 · by dgoodman · Math

Show categories

Class Name: FracSum

Return Type: int

Method Name: decompose

Arg Types: (int, int)

Problem Statement

We want to be able to express a fraction as a sum of two fractions that have small denominators. Specifically, given a fraction a/b, we want to find fractions c/d and e/f such that

a/b = c/d + e/f, where d and f are positive
max(d,f) is as small as possible

Create a class FracSum that contains a method decompose that is given a and b and that returns the smallest value for max(d,f).

Constraints

a and b will each be between 1 and 2,000,000,000, inclusive.

Examples

14
10
Returns: 5

14/10 = 0/1 + 7/5 is one way to keep the denominators less than or equal to 5.

1
60
Returns: 12

1/60 = -2/5 + 5/12

8
90
Returns: 9

8/90 = -4/5 + 8/9

60
1
Returns: 1

1
1073741824
Returns: 1073741824

Submissions are judged against all 62 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class FracSum with a public method int decompose(int a, int b) · 62 test cases · 2 s / 256 MB per case