TopCoder

Thumb 5b3
Nekosyndrome
かわいいは正義!

User's AC Ratio

60.0% (3/5)

Submission's AC Ratio

30.0% (3/10)

Description

費氏數列的處理,一向都是相當地費事。當然今天也不例外。各位應該有聽說過費式數列,或許沒有聽過以費式數列為基底的數字表示法吧!費氏數列基本上就是 (1,1,2,3,5,8,...),定義第零項、第一項都是1,自第二項起,每一項的數值皆等於前兩項的和。接下來我們來考慮費氏進位制:

說得單純一些,就是我們考慮將一個正整數 X 表示成費氏數列當中某些不重複項的和。例如

35 = 1 + 34 = 1 + 13 + 21 = 1 + 5 + 8 + 21 = 1 + 2 + 3 + 8 + 21

看起來有很多種表示法對吧?但若我們規定「選出來的數字不能有相鄰的項」,那麼一切就會變得簡單些了,例如:

35 = 1 + 34
30 = 1 + 8 + 21
28 = 2 + 5 + 21
12 = 1 + 3 + 8
7 = 2 + 5

巧合的是,可以證明恰好只有一種這樣的表示方法。

我們可以用類似二進位數的方法來表達這樣的一個正整數在「費氏進位制」底下長的樣子。

不過,現在費事的地方來了,我們要怎麼樣對兩個「費氏進位」的數字作加法呢?

Input Format

輸入僅包含兩列,第一列首先會有一個正整數 N (1<=N<=1,000,000) 代表數字 X 以費氏進位制表示的總位數,接下來會有 N 個以一個空白隔開的 1 或 0 代表費氏數列的「第幾項」有、或沒有被選到。第二列也是以同樣格式輸入的數字 Y。

例如:
若X以十進位表示為 28,那麼 X 在輸入中就會變成:7 0 1 0 1 0 0 1。

Output Format

請以相同格式輸出 X+Y 的費氏進位表示法。

Sample Input

7 0 1 0 1 0 0 1
4 0 1 0 1

Sample Output

8 1 0 0 0 0 0 0 1

Hints

換算成十進位就是 28 + 7 = 35 啦!

在VCOJ上面的測試資料中,
至少有佔總分60%以上的測試資料滿足 N<=1,000。

Problem Source

原TIOJ1521 / 2009宵夜盃練習賽I。Problem Setter:Tmt。

Subtasks

For Testdata: 0 ~ 0, Score: 6
For Testdata: 1 ~ 1, Score: 6
For Testdata: 2 ~ 2, Score: 6
For Testdata: 3 ~ 3, Score: 6
For Testdata: 4 ~ 4, Score: 6
For Testdata: 5 ~ 5, Score: 6
For Testdata: 6 ~ 6, Score: 6
For Testdata: 7 ~ 7, Score: 6
For Testdata: 8 ~ 8, Score: 6
For Testdata: 9 ~ 9, Score: 6
For Testdata: 10 ~ 10, Score: 6
For Testdata: 11 ~ 11, Score: 6
For Testdata: 12 ~ 12, Score: 6
For Testdata: 13 ~ 13, Score: 6
For Testdata: 14 ~ 14, Score: 6
For Testdata: 15 ~ 15, Score: 10
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 10000 65536 262144
1 10000 65536 262144
2 10000 65536 262144
3 10000 65536 262144
4 10000 65536 262144
5 10000 65536 262144
6 10000 65536 262144
7 10000 65536 262144
8 10000 65536 262144
9 10000 65536 262144
10 10000 65536 262144
11 10000 65536 262144
12 10000 65536 262144
13 10000 65536 262144
14 10000 65536 262144
15 10000 65536 262144