Login with GitHub. Nope?
修正 C++ 的程式碼在使用一定量動態記憶體後會產生 RF 的問題 @ 2019/12/6 4:45pm NeoHOJ 強勢復活中 (Open beta)
Submit  Ranklist

Problem : 52 - 瀚瀚數列

Problem Statistics

Solved Member: 21  Submission: 192  User Tried: 24

Statement:

數學家瀚瀚決定作一台電腦,用他所發現的和瀚瀚數列。

瀚瀚數列的故事就如同蔣公逆水上流一般的悅耳動聽感人肺腑:
從前從前(Day 0),HH家養了一對小兔子。
每一對小兔子過一天會長大,而每一對大的兔子則會在一天後生一對小兔子。

聰明的你可以遞推得出來:
Day 1:變成1對大兔子
Day 2:變成1對大兔子 + 1對小兔子
Day 3:變成2對大兔子 + 1對小兔子

瀚瀚以H(x)來表示第x天的兔子對數,可以發現第0項到第4項為1,1,2,3,5,且遞推方程為:

$$ \large H(n)= \begin{cases} 1 & \text{if } n \le 1 \\ H(n-1)+H(n-2) & \text{else} \end{cases} $$

不只如此,瀚瀚輕鬆的解出了遞迴:
$$\large H(n) = \frac{1}{\sqrt{5}} [(\frac{1+\sqrt{5}}{2})^{n+1} - (\frac{1-\sqrt{5}}{2})^{n+1}]$$

瀚瀚還因此拿到了費爾茲獎(瀚瀚表示遺憾,數學沒有諾貝爾獎QAQ)。他進一步的想要製造一台電腦來拿到圖靈獎,裡面的進位制使用瀚瀚數列。

瀚瀚表示法用來表示數列中的關係,以$(B_1 , B_2 , B_3 ... B_n)$來表示,其中$B_i$不是1就是0,代表$B_1 \times H(1) + B_2 \times H(2) + B_3 \times H(3) + ... + B_n \times H(n)$的整數。(注意,是從第1項開始而不是第0項)
其中n又稱為這個數字的"位數"。

舉例來說:(0,0,0,0,1,0,0,1)這個8位數代表42。

但是他發現表示法並不唯一,例如(0,0,0,0,1,1,1,0)或者(1,1,0,1,0,1,1)都是42,於是他決定這樣規範這個數列:
1. 如果n>1,$B_n = 1$,最高項一定是1。
2. 如果$B_i = 1$,那麼$B_{i+1} = 0$,不能有連續2個1存在。

所以42只有一種表示法:(0,0,0,0,1,0,0,1),其他都不合法。
瀚瀚保證,其他數字的表示法也一定是唯一的。

瀚瀚決定請你來幫忙他的機器實現加法,作為獎賞,他會分一點點圖靈獎的獎金給你!

Task:

給你2個瀚瀚表示法的數列,請你相加並且轉換為瀚瀚表示法。

Input:Output:

第1行最開始有一個數字n($1 \leq n \leq 1000000$),代表第一個數字的位數。
後面有n個整數,代表加數的瀚瀚表示法。
第2行最開始有一個數字m($1 \leq m \leq 1000000$),代表第二個數字的位數。
後面有m個整數,代表被加數的瀚瀚表示法。
輸出只有1行,最前面的數字是結果的位數。後面的數字為瀚瀚表示法的相加結果,每兩個數字之間用一個空白做間隔。

Sample Input:Sample Output:

4 0 1 0 1
5 0 1 0 0 1
6 1 0 1 0 0 1

Source:

POI 12 Stage 2

Problem Setter

Testdata:

TestTimeMemoryScore
02000ms32768kb
1-ocen2000ms32768kb
12000ms32768kb10
2-ocen2000ms32768kb
22000ms32768kb10
3-ocen2000ms32768kb
32000ms32768kb10
4-ocen3000ms32768kb
42000ms32768kb10
52000ms32768kb10
62000ms32768kb10
72000ms32768kb10
82000ms32768kb10
92000ms32768kb10
104000ms32768kb10