Marcus Approximation

View as PDF

Submit solution


Points: 12 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type

Marcus is a mathematician working at the University of Waterloo. Recently, he had been playing with triangles, and as he is a magnificent mathematician, he soon discovered a powerful formula to count right triangles under a certain hypotenuse. Are you able to keep up with Marcus?

More formally, given an integer hypotenuse h, Marcus would like you to count the number of non-degenerate triangles with integer legs and a hypotenuse (possibly non-integral) at most h. In this case, a triangle is defined as an ordered pair (a,b) (representing the lengths of its legs) such that a,b \in \mathbb{Z} and 1 \le a,b.

Lastly, to ensure the runtime and integrity of your solution, it will be run on T test cases.

Your solution will be accepted if it has a relative error of at most 10^{-3}. Relative error will be determined using the following formula:

If your answer is p and the correct answer is q, then your answer will be considered correct if

\displaystyle 0.999q \le p \le 1.001q

It is guaranteed that the output data has exactly the correct answer.

Constraints

For all subtasks:

T \in \{10, 100\}

1 \le h \le 10^9

Subtask 1 [10%]

T=10

1 \le h \le 10

Subtask 2 [10%]

T=10

1 \le h \le 1\,000

Subtask 3 [20%]

T=10

1 \le h \le 10^5

Subtask 4 [60%]

T=100

1 \le h \le 10^9

Input Specification

The first line will contain T, the number of test cases.

The next T lines will each contain an integer, the value of h for that test case.

Output Specification

Output the answer to each test case on a separate line.

Note: while the correct answer is always an integer, the float checker is used to determine if your solution is correct, so outputting a floating-point value is OK.

Sample Input

10
1
2
3
4
5
6
7
8
9
10

Sample Output

0
1
4
8
15
22
30
41
54
69

Explanation

Here are the answers for the first few test cases:

For h=1, there are no triangles that satisfy the requirement.

For h=2, the triangle that satisfies the requirement is (1,1).

For h=3, the triangles that satisfy the requirement are (1,2),(2,1),(2,2), along with the one that satisfies h=2.

For h=4, the triangles that satisfy the requirement are (1,3),(2,3),(3,1),(3,2), along with the ones that satisfy h=3.


Comments

There are no comments at the moment.