以下是不重要的故事
超級貓貓 Poo 是一隻喜歡研究各種奇怪理論的貓貓🐱✨。其中信號與系統,就是 Poo 非常喜歡的一門理論。
信號 signal ,是傳遞有關一些現象的行為或屬性的資訊的函數 (cite from wiki)。而這門學問,旨在研究針對一個系統 (system) ,輸入信號 (input signal) 後,其輸出信號 (output signal) 會具有什麼性質,也關心這個系統有什麼性質,等等。
Poo 某天學習到了一個系統,針對輸入的離散信號 $x[n]$,輸出的信號會是 (-1)n $x[n]$。
Note: 離散信號,可以簡單想像成,從整數映射到實數的函數 $x$: $\mathbb{Z} \to \mathbb{R}$。比方說,$x[n]=n$ 代表 $x[0]=0$, $x[1] = 1$, $x[2]=2$ 的線性函數。
一個系統,可以簡單想像成,會把輸入函數 $x$ 轉換成另外一個輸出函數 $y$ 的機器。比方說 $y[n]=x[n]+1$ 代表這個系統,會讓輸出的函數 $y$ 在每個不同的整數點 $n$ ,和輸入函數 $x$ 呈現的關係是 $y[n]=x[n]+1$。若輸入 $x[n]=n$ 這個信號,則會得到 $y[n]=x[n]+1=n+1$ 這個平移過的線性函數。
為了簡化問題,這裡僅考慮有限長度的信號。也就是信號只會在某段範圍內是非 0 的值,超出這個範圍都是 0。並且總是將這段範圍平移到 $[0,L]$ 的範圍內。
所以給定 $L$ ,以及 $0$~$L$ 的輸入值,就可以唯一決定一個信號。
"輸入的離散信號 $x[n]$,輸出的信號會是 (-1)n $x[n]$" 這個系統的輸入輸出對應非常簡單,當 $n$ 為偶數,則輸出即輸入,當 $n$ 為奇數則變號。
但仔細研究這個系統的意義後, Poo 發現這是一個將 $x[n]$ 的頻譜平移 $\pi$ 的系統。其物理意義是,會將這個信號中最高頻的成分,平移到最低頻,並且將最低頻的成分,平移到最高頻。
這樣的系統在某些情境下蠻有用的。比方說,若我們已經有了 LPF (Low Pass Filter),也就是可以過濾掉信號高頻成分,留下低頻成分的一個系統。當我們想要去除信號的底噪,也就是信號的低頻成分時,可以將信號先通過 (-1)n 這個系統,平移信號的頻譜,再進入 LPF ,最後再通過一次 (-1)n 的系統將頻譜平移回來,即可將低頻成分濾除。 (利用 LPF 實作 HPF)。
Poo 讀完這段理論後覺得實在太有趣了,想要實際實作看看。但 Poo 只是一隻貓啊 !!!!!! 請你幫他實作這樣的系統 !
第一行為一個數字 $L$,表示這個信號的長度為 $L$ (僅在 $0$-$L$ 有值)
接下來 $L$ 行,代表這個信號在 $0$-$L$ 每個點的數值
第 $2$ 行,代表的是 $x[0]$ 的數值
第 $i$ 行,代表的是 $x[i-2]$ 的數值
比方說
3
1
2
3
代表
信號長度為 3
$x[0] = 1$
$x[1] = 2$
$x[2] = 3$
保證 $1\leq L \leq 1e6$,$-2147483647 \leq x[i] \leq 2147483647$。
請將 (-1)n $x[n]$ 的結果逐行輸出,僅需輸出 $0$-$L$ 的輸出值
以同一個例子,你需要輸出
1
-2
3
對於 Bonus 的部份,可以注意到本題的輸入量很大,用 input()
來讀取輸入會因為不必要的 overhead,而拖垮程式效能。相對的 File I/O 的 readline
會是更優的選擇。
No. | Testdata Range | Constraints | Score |
---|---|---|---|
1 | 0~5 | 時間限制為 5 秒 | 100 |
2 | 6~9 | [Bonus] 時間限制為 1 秒 | 20 |