| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 서브태스크 참고 | 1024 MB | 91 | 67 | 50 | 79.365% |
Addition and squaring do not commute. That is, the square of the sum of all elements of a list of integers is not necessarily equal to the sum of the squares of those same elements. However, this is true for some lists; one example is $[3,-2,6],ドル because $(3+(-2)+6)^2=49=3^2+(-2)^2+6^2$. Let us call these lists squary.
Given a (not necessarily squary) list of relatively small integers, we want to know whether it is possible to add at least 1ドル$ and at most $K$ more elements such that the final list is squary. Each added element must be an integer between $-10^{18}$ and 10ドル^{18},ドル inclusive, and these do not have to be distinct from each other or from the initial list's elements.
The first line of the input gives the number of test cases, $T$. $T$ test cases follow. Each test case is described in two lines. The first line contains two integers $N$ and $K,ドル the number of elements of the initial list and the maximum number of elements you may add, respectively. The second line contains $N$ integers $E_1,E_2,…,E_N,ドル representing the $N$ elements of the initial list.
For each test case, output one line containing Case #x: y, where $x$ is the test case number (starting from 1). If it is possible to add at least 1ドル$ and at most $K$ elements (each an integer between $-10^{18}$ and 10ドル^{18},ドル inclusive) to the initial list such that the square of the sum of its elements equals the sum of the squares of its elements, $y$ should be $z_1$ $z_2$ $\dots$ $z_r,ドル where 1ドル≤r≤K$ and the $z_i$ values are the additional elements. If there is no way to accomplish this, $y$ should be IMPOSSIBLE.
시간 제한: 5 초
시간 제한: 10 초
4 2 1 -2 6 2 1 -10 10 1 1 0 3 1 2 -2 2
Case #1: 3 Case #2: IMPOSSIBLE Case #3: -1000000000000000000 Case #4: 2
In Sample Case #1, we can end up with the example list given in the problem statement.
In Sample Case #2, we have to add exactly one element. If we call that element $x,ドル the sum of the entire list is $x$ and its square is $x^2$. The sum of the squares of all elements, on the other hand, is $x^2+10^2+(-10)^2=x^2+200≠x^2,ドル so the case is impossible.
In Sample Case #3, any integer in the$[-10^{18},10^{18}]$ range is a valid answer.
In Sample Case #4, notice that the input might contain duplicate elements, and that it is valid to create even more duplicates with the elements you choose to add.
3 3 10 -2 3 6 6 2 -2 2 1 -2 4 -1 1 12 -5
Case #1: 0 Case #2: -1 15 Case #3: 1 1 1 1 1 1 1 1 1 1 1
In Case #1 of the additional samples, we are given the example list from the problem statement, which is already squary, but we need to add at least one element to it. Adding a 0ドル$ keeps the list squary.
In Case #3 of the additional samples, we present one of multiple possible valid answers. Notice that it is permissible to add fewer than $K$ elements; here $K$ is 12ドル$ but we have only added 11ドル$ elements.
Contest > Google > Code Jam > Google Code Jam 2022 > Round 1C B번