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
Nekosyndrome Testdata:
Test | Time | Memory | Score |
---|
0 | 2000ms | 32768kb | |
1-ocen | 2000ms | 32768kb | |
1 | 2000ms | 32768kb | 10 |
2-ocen | 2000ms | 32768kb | |
2 | 2000ms | 32768kb | 10 |
3-ocen | 2000ms | 32768kb | |
3 | 2000ms | 32768kb | 10 |
4-ocen | 3000ms | 32768kb | |
4 | 2000ms | 32768kb | 10 |
5 | 2000ms | 32768kb | 10 |
6 | 2000ms | 32768kb | 10 |
7 | 2000ms | 32768kb | 10 |
8 | 2000ms | 32768kb | 10 |
9 | 2000ms | 32768kb | 10 |
10 | 4000ms | 32768kb | 10 |