f928: 連環炸彈.................Boom!
Tags : 遞迴
Accepted rate : 23人/24人 ( 96% ) [非即時]
評分方式:
Tolerant

最近更新 : 2021-09-12 21:55

Content

現在有 N 個炸彈,由左至右分別為 x0, x1, ..., xN-1
依據每個炸彈不同的爆炸威力 xi (0 ≤ i ≤ N-1),可以被分為三種爆炸狀態:

xi = 1 為啞炮:
只會引爆自己,不會波及其他炸彈
(此處的啞炮並不是指某小說中,出生巫師家庭卻不會用魔法的人)

xi = 2 為左右炮:
引爆自己後,會波及左右 xi-1 和 xi+1,總共兩個炸彈
但如果被波及的位置根本沒有炸彈(即超出 0 ~ N-1 的範圍),則該位置不受影響

xi = k (k ≥ 3)為怪怪炮:
引爆自己後,會波及左邊 xi-k 、 xi-2k 和 右邊 xi+k、 xi+2k,總共四個炸彈
但如果被波及的位置根本沒有炸彈(即超出 0 ~ N-1 的範圍),則該位置不受影響

當被波及的炸彈引爆後,
會繼續依照以上規則繼續引爆其周遭炸彈,也就是所謂的「連環爆炸反應」



給予 N 個炸彈和各個炸彈的爆炸類型 x0 ~ xN-1
現在指定一個 T 值 (0 ≤ T ≤ N-1),即決定要引爆的初始炸彈編號。
請問在經過完整的「連環爆炸反應」後,最後這 N 個炸彈的狀態會變為如何?
其中若 xi 不變代表該炸彈不被引爆,若 xi = 0 則表示該位置炸彈將被引爆。

Input

第一行有一個正整數 N,
代表總共有 N 個炸彈 ( 1 ≤ N ≤ 1000 )

第二行由左至右有 N 個正整數 x( 1 ≤ xi ≤ 10 ),
兩兩之間以空格隔開,代表炸彈目前狀態

第三行有一個正整數 T ( 0 ≤ T ≤ N-1 ),
代表要被引爆的初始炸彈編號

Output

輸出經過完整的「連環爆炸反應」後,這 N 個炸彈的最終狀態
由左至右分別為 x0, x1, ..., xN-1,兩兩之間以空格隔開,並且結尾需換行

其中 xi 不變代表該炸彈不被引爆,xi = 0 代表炸彈將被引爆

Sample Input #1
5
1 1 1 1 1
2
Sample Output #1
1 1 0 1 1
Sample Input #2
5
1 1 2 1 1
2
Sample Output #2
1 0 0 0 1
Sample Input #3
13
1 1 1 1 1 1 3 1 1 1 1 1 1
6
Sample Output #3
0 1 1 0 1 1 0 1 1 0 1 1 0
Sample Input #4
13
1 1 1 1 1 1 3 1 1 2 1 1 1
6
Sample Output #4
0 1 1 0 1 1 0 1 0 0 0 1 0
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (5%): 1.0s , <1K
公開 測資點#1 (5%): 0.5s , <1K
公開 測資點#2 (5%): 0.5s , <1K
公開 測資點#3 (5%): 0.5s , <1K
公開 測資點#4 (5%): 0.5s , <1K
公開 測資點#5 (5%): 0.5s , <1M
公開 測資點#6 (5%): 0.5s , <1K
公開 測資點#7 (5%): 0.5s , <1K
公開 測資點#8 (5%): 0.5s , <1K
公開 測資點#9 (5%): 0.5s , <1K
公開 測資點#10 (5%): 0.5s , <1K
公開 測資點#11 (5%): 0.5s , <1K
公開 測資點#12 (5%): 0.5s , <1K
公開 測資點#13 (5%): 0.5s , <1K
公開 測資點#14 (5%): 0.5s , <1K
公開 測資點#15 (5%): 0.5s , <1K
公開 測資點#16 (5%): 0.5s , <1M
公開 測資點#17 (5%): 0.5s , <1M
公開 測資點#18 (5%): 0.5s , <1M
公開 測資點#19 (5%): 0.5s , <1M
Hint :

10%:x只會有 1
30%:x只會有 1 或 2 
60%:無特別限制 

Tags:
遞迴
出處:
[管理者:
mushroom.cs9... (mushroom)
]


ID User Problem Subject Hit Post Date
27070
wallacechu04... (Wallace Chu)
f928
bfs
37 2021-09-11 22:29
27038
s1082942@g.n... (sellie)
f928
68 2021-09-08 19:01