Koto Municipal Subway
InterviewTime limit8sMemory limit512 MB
Given D and E, find the integer point (x, y) with x + y = D that minimizes |sqrt(x^2 + y^2) - E| and print that minimum difference.
- Level
Easy3 of 10
- Topics
- Math, Brute force, Implementation
- Solved
- No attempts yet
Problem
Koto is a city famous for its grid of roads, as shown in the figure below. The roads running north-south and the roads running east-west are spaced 1 km apart. Let the Koto station at the southwesternmost intersection of Koto be (0, 0), and write the position x km east and y km north of it as (x, y) (0 ≤ x, y).
Anticipating an increase in tourists from the Olympics to be held five years later, the city decided to build a new subway line starting from Koto station. It is now planning to lay rails from Koto station to the newly built Shin-Koto station, the next station after Koto. The rails run straight from Koto station toward Shin-Koto station. Therefore, if the location of Shin-Koto station is (x, y), the length of the rails is √(x2 + y2). The cost of laying the rails is proportional to the length of the rails laid. Even if the rail length is a decimal such as 1.5 km, the cost is likewise 1.5.
The location (x, y) of Shin-Koto station has not yet been decided, and it will be chosen to satisfy the following conditions.
- It is an intersection. That is,
xandyare each integers. - The shortest distance walked along the roads from Koto station is exactly
D. That is,x+y=D.
Among the locations satisfying the two conditions above, the city chooses the location of Shin-Koto station so that the difference | √(x2 + y2) - E | between the rail cost and the rail budget E set by the city is minimized. Here |A| denotes the absolute value of A. Your job is to write a program that outputs the difference between the cost of laying the rails and the budget when Shin-Koto station is built as described above.
Input
The input consists of multiple datasets, and the number of datasets in one input is at most 100. The format of each dataset is as follows.
D E
D (1 ≤ D ≤ 100) is an integer representing the shortest distance walked along the roads from Koto station to Shin-Koto station. E (1 ≤ E ≤ 100) is an integer representing the budget for rail construction.
The end of the input is indicated by a line consisting of two zeros separated by a space.
Output
For each dataset, output in one line the difference between the cost and the budget when the rails are laid so as to satisfy the conditions of the problem. The answer must not have an absolute error greater than 10-3. Note that failing to output a newline at the end of each line or outputting unnecessary characters will be judged as a wrong answer.
Hint
In the first dataset, as shown in the figure below, the intersections 2 km along the roads from Koto station are candidates for the location where Shin-Koto station will be built.
When Shin-Koto station is built at each intersection, the difference between the cost of laying the rails and the budget 1 is as follows.
- (2, 0) : | √(22 + 02) - 1 | = 1.0
- (1, 1) : | √(12 + 12) - 1 | = 0.4142135623...
- (0, 2) : | √(02 + 22) - 1 | = 1.0
Therefore, the difference between the cost and the budget is minimized when the station is built at (1, 1).