TopCoder

Nekosyndrome
かわいいは正義!

User's AC Ratio

50.0% (3/6)

Submission's AC Ratio

13.6% (3/22)

Tags

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 1

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

Sample Output 1

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

No. Testdata Range Score
1 0 6
2 1 6
3 2 6
4 3 6
5 4 6
6 5 6
7 6 6
8 7 6
9 8 6
10 9 6
11 10 6
12 11 6
13 12 6
14 13 6
15 14 6
16 15 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 10000 65536 262144 1
1 10000 65536 262144 2
2 10000 65536 262144 3
3 10000 65536 262144 4
4 10000 65536 262144 5
5 10000 65536 262144 6
6 10000 65536 262144 7
7 10000 65536 262144 8
8 10000 65536 262144 9
9 10000 65536 262144 10
10 10000 65536 262144 11
11 10000 65536 262144 12
12 10000 65536 262144 13
13 10000 65536 262144 14
14 10000 65536 262144 15
15 10000 65536 262144 16