Time Limit: 1 sec
Memory Limit: 16MB
Lagrange's four-square theorem states that every positive integer can be
expressed as the sum of four squares of integers. For example:
3 = 12 + 12 + 12 + 02
31 = 52 + 22 + 12 + 12
However some positive integers can be expressed even as the sum of three squares
of non-negative integers. For example:
3 = 12 + 12 + 12
17 = 02 + 12 + 42
In this problem you have to find expression of given integer K as the sum of three squares, or state that it is impossible.
a b c
". Where a <= b
<= c and K = a2 + b2 + c2
. If there is more
than one possible answer, print the one that comes first lexicographically. If
expression in three squares of non-negative integers do not exist print "-1
" (see examples).
3
13
15
17
0 2 3
-1
0 1 4
Problem setters: Aleksej Viktorchik, Leonid Shishlo.
Huge Easy Contest #1