시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 14 | 4 | 4 | 30.769% |
Professor is preparing a task for higher math students.
The task is the following. The students are given $n$ integers $x_1, x_2, \ldots, x_n$, and an integer $m$ ($1 \le m < 2^n$).
The student must choose $n$ integers $a_1, a_2, \ldots, a_n$, each either $-1$, $0$, or $1$, at least one non-zero value be chosen. The chosen integers must satisfy the condition that $a_1x_1+a_2x_2+\ldots+a_nx_n$ is divisible by $m$.
The professor has decided that the answer to the task should be some given array of integers $a_1, a_2, \ldots, a_n$ ($-1 \le a_i \le 1$, at least one of them is not equal to $0$). To make his job of checking students' solutions easier, he wants to choose such integers $x_1, x_2, \ldots, x_n$ and an integer $m$, that his array $a_1, a_2, \ldots, a_n$ is the only possible solution. Unfortunately it is not possible, because the array $-a_1, -a_2, \ldots, -a_n$ is always a solution too.
So the professor relaxes his requirements, and wants the only two solutions be $a_1, a_2, \ldots, a_n$ and $-a_1, -a_2, \ldots, -a_n$.
Help him choose integers $x_1, x_2, \ldots, x_n$ and an integer $m$.
The first line of input contains an integer $n$ ($1 \leq n \leq 30$).
The next line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($-1 \leq a_i \leq 1$). At least one of $a_i$ is not equal to $0$.
The first line of output must contain and integer $m$ ($1 \le m < 2^n$).
The next line must contain $n$ integers $x_1, x_2, \ldots, x_n$ ($-2^{30} < x_i < 2^{30}$).
If there are several possible answers, output any of them.
It is known that the answer always exists.
2 1 -1
3 1 4
In the given example the students must choose $a_1$ and $a_2$ so that $a_1 + 4a_2$ is divisible by $3$. There are two possible solutions:
Professor's requirements are met.