b089. 微生物 (live) - Zero1 Online Judge System

Content

科學家正在研究一種微蟲的生長周期，並發現以下的一些規律：

微蟲的壽命是 𝐿 個周期
微蟲在生長到第 𝑀 個周期時就進入成熟期稱為成蟲。成蟲都會參與繁殖。
在每個周期內新出生的微蟲數目等於所有還生存的成蟲的數量的總和之 1/𝑃 取整。
剛出生的微蟲視為第一周齡的蟲體 (即沒有所謂 0 周齡的蟲)。
壽命到達 𝐿 周齡的成蟲會參與一生中的最後一次繁殖, 然後在周期末自然死亡。
在蟲群中, 不定期會出現一次病毒, 每次病毒出現時就會有以下結果:
- 只有成蟲才會感染到這種病毒, 新感染到病毒的成蟲每個周齡群(即同一周齡的成蟲的群體) 中都會死去該周齡群的一半 (取整數, 如該群的數目為9, 則會死4 餘下5, 若數目為10,則死去和餘下的數目相同)。
- 曾感染病毒的生還者會終身免疫, 即在自然老死前再也不會感染病毒, 也就不會因感染病毒而死亡 (當然, 它們還是會因周齡到 𝐿 而自然老死)。
- 因病毒而死亡的情況會發生在繁殖完成後及自然老死前。
- 病毒在一個周期內只會出現最多一次。

為方便計算我們假設以上的所有數目都是準確的。即的生長沒有不確定性或隨機性。

在實驗開始時, 我們有 𝑁 隻微蟲, 且所有的微蟲都是剛出生的第一周期蟲。在實驗期間, 科學家觀察到有 𝑄 次的病毒出現, 科學家記錄了病毒出現的時間, 他們想知道在病毒出現的那個周期的期未, 跟據上述的生長規則, 蟲群生還的總數目應為多少 (生還的數目包括周齡為 𝐿 的, 在該周期末將會自然死亡的生還者及在當周期剛出生的蟲在內)。

Input

輸入的第一行有 5 個正整數 𝑁 𝐿 𝑀 𝑃 𝑄, 它們的代表的意義見上面的描述。
接下來有 𝑄 行, 每行有一個正整數 𝑡, 它代表在第 𝑡 個周期時, 病毒出現了一次。而實驗開始時視為第一個周期。

其中, 病毒出現的周期記錄時間未必一定是順時間序。但可以保證輸入中沒有重複出的周期 𝑡, 且所病毒出現的周期都有包括在輸入資料內。

Output

輸出應有 𝑄 行, 每行有一個非負整數。它順序對應輸入的每次病毒出現時, 在該周期未還生存的蟲的總數。

這個總數包括該周期出生的蟲, 還生存的成年蟲包括周齡為 𝐿 的成年蟲在內。

Sample Input #1

Sample Output #1

98
111
84

Sample Input #2

Sample Output #2

84
98
111

測資資訊：

記憶體限制： 64 MB
不公開測資點#0 (10%): 1.0s , <1K
不公開測資點#1 (10%): 1.0s , <1M
不公開測資點#2 (10%): 1.0s , <1M
不公開測資點#3 (10%): 1.0s , <1M
不公開測資點#4 (10%): 1.0s , <1M
不公開測資點#5 (10%): 1.0s , <1M
不公開測資點#6 (10%): 1.0s , <1M
不公開測資點#7 (10%): 1.0s , <1M
不公開測資點#8 (10%): 1.0s , <1M
不公開測資點#9 (10%): 1.0s , <1M

Hint ：

對應於以上的輸入, 蟲的周期變代如下:

周期數	1周齡蟲數	2周齡蟲數	3周齡蟲數	4周齡蟲數
第1周期	99	0	0	0
第2周期	0	99	0	0
第3周期	49	0	99	0
第4周期	49	49	0	99
第5周期	24	49	49	0
出現病毒	24	49	25	0
第6周期	37	24	49	25
出現病毒	37	24	25	25
第7周期	24	37	24	25
第8周期	30	24	37	24
第9周期	30	30	24	37
第10周期	27	30	30	24
出現病毒	27	30	15	12

其中, 當病毒在第6周期出現時, 5周齡的蟲群因是病毒生還者, 所以它們不會受感染因而數目保持為25。

1 ≤ 𝑁 ≤ 1,000, 4 ≤ 𝐿 ≤ 2,000, 1 < 𝑀 ≤ 𝐿, 1 ≤ 𝑄 ≤ 90,000, 1 > 𝑡 ≤ 150,000
有20分的數據中, 其 𝑡 的值是按時間順序排列在輸入檔案中的
有60分的數據中 𝑄 ≤ 20,000
有80分的數據中 𝑄 ≤ 60,000

Tags:

出處:

MOIJ 2023 [管理者：

lamkinun@gma... (Kinda Lam)

]

ID	User	Problem	Subject	Hit	Post Date
沒有發現任何「解題報告」