TopCoder problem "CalcRoot" used in SRM 246 (Division I Level Three)



Problem Statement

    

You are developing a new calculator with a square root function. To make things simple for your clients, you have decided to approximate square roots as simple fractions, rather than displaying a long sequence of digits.

You will be given N and D and should return the fraction closest to sqrt(N) for which the denominator is not greater than D. The fraction should be returned in the form "A/B" where A and B are positive integers with no common factors greater than one.

 

Definition

    
Class:CalcRoot
Method:approximate
Parameters:int, int
Returns:String
Method signature:String approximate(int N, int D)
(be sure your method is public)
    
 

Constraints

-N will be between 1 and 1000000, inclusive.
-D will be between 1 and 1000, inclusive.
 

Examples

0)
    
4
10
Returns: "2/1"
1)
    
5
3
Returns: "7/3"
sqrt(5) = 2.236
2)
    
12
10
Returns: "31/9"
sqrt(12) = 3.464
3)
    
23743
763
Returns: "98462/639"

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=4519

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=7221&pm=4519

Writer:

Andrew_Lazarev

Testers:

PabloGilberto , lbackstrom , brett1479

Problem categories:

Brute Force, Math