問題一覧 > 通常問題

No.451 575

レベル : / AI推定難易度 : 1200 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (AC するまで非表示) / 解いたユーザー数 112
作問者 : 🐬hec
お気に入りにしたユーザー ProblemId : 1416 / 自分の提出
問題文最終更新日: 2026-06-25 02:27:48
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
Advent Calendar Contest 2016 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。