CalcRoot
SRM 246 · 2005-06-09 · by Andrew_Lazarev
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.
Constraints
- N will be between 1 and 1000000, inclusive.
- D will be between 1 and 1000, inclusive.
4 10 Returns: "2/1"
5 3 Returns: "7/3"
sqrt(5) = 2.236
12 10 Returns: "31/9"
sqrt(12) = 3.464
23743 763 Returns: "98462/639"
991746 903 Returns: "837522/841"
Submissions are judged against all 124 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class CalcRoot with a public method string approximate(int N, int D) · 124 test cases · 2 s / 256 MB per case