f928. 連環炸彈.................Boom!
標籤 : 遞迴
通過比率 : 225人/239人 ( 94% ) [非即時]
評分方式:
Tolerant

最近更新 : 2021-10-26 22:53

內容

現在有 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 則表示該位置炸彈將被引爆。

輸入說明

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

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

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

輸出說明

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

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

範例輸入 #1
5
1 1 1 1 1
2
範例輸出 #1
1 1 0 1 1
範例輸入 #2
5
1 1 2 1 1
2
範例輸出 #2
1 0 0 0 1
範例輸入 #3
13
1 1 1 1 1 1 3 1 1 1 1 1 1
6
範例輸出 #3
0 1 1 0 1 1 0 1 1 0 1 1 0
範例輸入 #4
13
1 1 1 1 1 1 3 1 1 2 1 1 1
6
範例輸出 #4
0 1 1 0 1 1 0 1 0 0 0 1 0
測資資訊:
記憶體限制: 64 MB
提示 :

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

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

本題狀況 本題討論 排行

編號 身分 題目 主題 人氣 發表日期
27070 wallacechu04 ... (Wallace Chu) f928
650 2021-09-11 22:29
27038 s1082942@g.n ... (sellie) f928
707 2021-09-08 19:01