宇宙中有一條酷酷的隕石軌道,有 $N$ 個事件依序發生。事件由一個整數 $X$ 代表:
1. $X > 0$:一顆大小為 $X$ 的隕石向右飛行,進入軌道的最右側。
2. $X < 0$:一顆大小為 $|X|$ 的隕石向左飛行,直接撞入軌道。它會與軌道最右側(也就是最晚進入且尚未被摧毀)向右飛行的隕石發生碰撞。
向右隕石較小:向右的爆炸消失,向左的繼續向左飛,與下一個向右飛行的隕石碰撞。
兩者一樣大:兩顆同時爆炸消失。
向左隕石較小:向左的爆炸消失。
根據結果也會有以下兩種可能:
殘骸收集:任何爆炸的隕石,其殘骸(大小等於原體積)會立刻被一台資源回收船吸入其內部的回收管道中。若兩顆隕石同時爆炸,先吸入向右飛行的殘骸,再吸入向左飛行的殘骸。
厲害的隕石:向左飛行的隕石若在碰撞中存活,它會停留在軌道的最右側。此時若緊鄰它左側的是另一顆向左飛行且大小相同的隕石,兩者會融合為一顆大小為原本體積 $+1$ 且繼續向左飛的隕石。這個厲害的隕石會不斷向左側飛行,直到左側沒有隕石或大小不同為止。
3. $X = 0$:資源回收船發動發射程序。
若回收管道內還有殘骸,回收船會將管道內存放最久(最先被吸入)的一塊殘骸射出,並將其當作一顆向左飛行的隕石,這顆殘骸會的運作邏輯會跟 $2$ 點的向左飛行的隕石一模一樣。
所有事件結束後,請輸出軌道上最終剩下的隕石(向左飛的輸出為負數,向右飛的為正數),順序為軌道的由左至右。
第一行包含一個整數 $T$ ($1 \le T \le 10$),代表測試資料筆數。
每筆測資第一行包含一個整數 $N$。
第二行包含 $N$ 個整數 $X_i$ ($-10^9 \le X_i \le 10^9$)。
對每筆測資,輸出最終留下的隕石,數字間以空白分隔。如果沒有隕石留下來,不用輸出直接換行就好。
2 6 5 10 -5 -10 -10 -10 4 10 5 -5 0
-11 10
$\mathbf{30}$%:$\sum N \le 10^4$,輸入中保證不包含 0。
$\mathbf{70}$%:無特別限制
範例說明:
第一筆測資: 5 進入, 10 進入,-5 撞 10 爆掉,-10 撞 10 兩顆隕石都爆掉,軌道剩 5,-10 撞 5 存活並進入軌道。最後一個 -10 進入軌道,發現左側也是 -10,變成厲害的隕石體積 +1 = -11。
第二筆測資: 10 進入, 5 進入,-5 撞 5 兩顆都爆(回收管道吸入 5 , 5),遇到 0,管道吐出最早進入的 5 變成 -5 射出,-5 撞 10 爆掉(管道再吸入 5),最後軌道剩 10。
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||