|시간 제한||메모리 제한||제출||정답||맞힌 사람||정답 비율|
|2 초||512 MB||13||9||5||100.000%|
We consider decompositions of positive integers into sums of unique squares of positive integers, called decompositions in short from now on. For example, the number 30 has two decompositions: 12 + 22 + 52 = 12 + 22 + 32 + 42 = 30, whereas the number 8 has none.
Specifically, we are interested in how large the largest square in the decomposition of a given number n has to be. In other words, we want to determine the value k(n), defined as the minimum over decompositions of n of the maximum integer (not its square!) in the decomposition. We assume that k(n) = ∞ if n cannot be decomposed. For example, k(1) = 1, k(8) = ∞, k(30) = 4, k(378) = 12, k(380) = 10.
We call an integer x overgrown if there is an integer y > x such that k(y) < k(x). It follows from the previous example that 378 is overgrown.
For a given integer n, you are to determine k(n) and the number of overgrown integers no larger than n.
In the first and only line of the standard input, there is a single integer n (1 ≤ n ≤ 1018). There is a set of tests worth 45% of total score, in which n ≤ 50 000 000 holds, a subset of these worth 30% of total score, in which n ≤ 1 000 000 holds, and an even smaller subset of the latter worth 20% of total score, in which n ≤ 1000 holds.
Your program should print two integers, separated by a single space, to the standard output: first k(n) and then the number of overgrown integers in the range from 1 to n. If k(n) = ∞, then - (dash or minus sign) should be printed instead of the first number.