No.451 575
タグ : / 解いたユーザー数 112
作問者 :
🐬hec
Note
This problem was created as the Day 2 problem of Advent Calendar Contest Advent Calendar 2016.
Story (you can solve the problem without reading this)
Lately, whenever Iruka mutters something like "本日はYukicoderの出題日" ("today is the day of the Yukicoder problem"), the other animals point out that it is a 575. Because of this, Iruka has become interested in detecting 575s.
By the way, this problem's date is December 2. Does that remind you of anything?
That's right. If we regard the date as the sequence {12,2}, then since 12=5+7 and 2=7-5, {5,7,5} appears.
In other words, [12,2] is made of {the sum of the first and second terms, the difference obtained by subtracting the third term from the second term} of {5,7,5}.
Extending this idea, we can generate a new sequence from a given sequence by looking at each pair of two consecutive terms from the left and alternately taking their sum and difference.
When Iruka was told this fact, Iruka became interested in the fact that a sequence of length n generated in this way can be decomposed into the original sequence of length n+1.
So, for Iruka's sake, we decided to write a program to verify this.
Problem Statement
You are given a sequence $\{b_1,b_2,\cdots,b_n\}$ of $n$ terms. Output a sequence $\{a_1,a_2,\cdots,a_n,a_{n+1}\}$ of $n+1$ terms satisfying the following conditions.
$\begin{eqnarray} b_i = \begin{cases} a_i+a_{i+1} & (i \equiv 1 \mod 2) \\ a_i-a_{i+1} & (i \equiv 0 \mod 2) \end{cases}\end{eqnarray} (1 \le i \le n)$
$1 \le a_i \le 10^{18} \ (1 \le i \le n+1)$
$a_i \in \mathbb{N} \ (1 \le i \le n+1)$
Input
$n$ $b_1$ $b_2$ $\vdots$ $b_n$
$1 \le n \le 10^5$
$1 \le b_i \le {10}^{18} \ (1 \le i \le n)$
$b_i \in \mathbb{N} \ (1 \le i \le n)$
Output
If there is no sequence $\{a_1,a_2,\cdots,a_n,a_{n+1}\}$ satisfying the conditions, output $-1$ as shown below.
$-1$Otherwise, output a sequence satisfying the conditions in the following format.
$n+1$
$a_1$
$a_2$
$\vdots$
$a_{n+1}$
Print a newline at the end.
Sample
Sample 1
Input
2 12 2
Output
3 5 7 5
This is the example described in the story.
Sample 2
Input
1 5
Output
2 1 4
Other sequences such as {2,3} and {3,2} also satisfy the conditions.
Sample 3
Input
1 1
Output
-1
Since the sum of two positive integers is at least 2, no sequence satisfying the conditions exists.
Sample 4
Input
10 933 925 304 138 179 19 101 13 469 200
Output
11 1 932 7 297 159 20 1 100 87 382 182
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。