h040: 釣魚 (Fishing)
Tags : binary index tree binary search hololive math pokemon
Accepted rate : 1人/1人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-01-14 20:16

Content

傳說中存在一種金光閃閃的鯉魚,人們稱之為「金鯉魚王」;白上吹雪是 一位熱衷於尋求「金鯉魚王」的人,她想要以釣魚的方式獲得「金鯉魚王」, 於是她準備好釣竿之後,隨即開始她的釣魚生活。 但是釣魚是一件需要十足耐心的活動,在中途選擇放棄時有所聞;假設白上 吹雪的初始耐心程度為正整數 V0,每當她釣到一隻並非「金鯉魚王」的魚,其耐 心程度會減 1。白上吹雪有著許多的朋友,白上吹雪的朋友們皆希望她能夠順利 釣到「金鯉魚王」;當她的耐心程度降為 0 時,大家會激勵她不要放棄,此時受 到大家激勵的白上吹雪其耐心程度會獲得回復並選擇繼續釣魚。若朋友越多,激 勵的效果會越好,但始終不會超過上一次的初始耐心程度,具體公式如下: 𝑉𝑡 = ⌊𝑉𝑡−1 × 𝑚𝑖𝑛(𝑙𝑜𝑔2 (𝐹𝑡 + 1) , 30) /30 ⌋ 其中 Vt 代表在第 t 次朋友們的激勵之後,白上吹雪將會回復至 Vt 的耐心程度, Ft 代表共有 Ft 位朋友參與第 t 次的激勵,⌊𝑥⌋代表取 x 的下整數(即不超過 x 的 最大整數)。朋友們同樣也有其耐心,在經過 N 次激勵之後將不再會有朋友激勵 白上吹雪,可將其視為 FN+1 = 0;若白上吹雪的耐心程度無法獲得回復(即 Vt = 0),她會因為耐心不足而選擇放棄繼續釣魚。 身為白上吹雪朋友的一員,除了適時激勵她之外,你同時也好奇在她放棄之 前是否真的能夠釣到「金鯉魚王」,為此你先對會參與激勵的朋友數進行評估, 並假設她會在第 K 竿釣到「金鯉魚王」,你想知道在如此模型及條件假設之下, 白上吹雪至少需要多少初始耐心程度 V0 才能夠釣到「金鯉魚王」?

Input

第一行包含一個正整數 N (1 ≤ N ≤ 4×10^4 ),表示在經過 N 次激勵之後將不再 會有朋友激勵白上吹雪。 第二行包含 N 個正整數 Fi (1 ≤ Fi ≤ 2×10^9 ),表示在第 i 次的激勵共有 Fi 位朋 友參與。 第三行包含一個正整數 Q (1 ≤ Q ≤ 100),表示接下來有 Q 筆詢問。 接下來的 Q 行每一行包含一個正整數 K (1 ≤ K ≤ 2×10^9 ),代表預計白上吹雪 將會在第 K 竿會釣到「金鯉魚王」。

Output

對於每筆詢問分別輸出一行,共輸出 Q 行;每行輸出一個整數 V0,代表對 於每筆詢問的假設中,在一開始白上吹雪至少需要多少初始耐心程度 V0 才能夠 釣到「金鯉魚王」。要注意的是,初始耐心程度 V0 須為正整數。

Sample Input #1
2
7 3
2
5
330
Sample Output #1
5
300
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (10%): 1.0s , <1M
公開 測資點#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. 對於第一筆詢問:

若 V0 = 4,則白上吹雪在被激勵之前可以釣 4 竿;但在被激勵之後其耐心程 度無法獲得回復(V1 = 0);故總共釣 4 竿,小於預測的 K = 5,並無法釣到 「金鯉魚王」。

若 V0 = 5,則白上吹雪在被激勵之前可以釣 5 竿,即可釣到「金鯉魚王」。

由上述可以得知,白上吹雪至少需要初始耐心程度 V0 = 5 才能夠釣到「金 鯉魚王」,故輸出 5。

 

2. 對於第二筆詢問:

若 V0 = 299,則白上吹雪在被激勵之前可以釣 299 竿;在第一次被激勵之 後其耐心程度回復至 V1 = 29,在下一次激勵之前可以釣 29 竿;在第二次 被激勵之後其耐心程度回復至 V2 = 1,在下一次激勵之前可以釣 1 竿;由 於朋友們已失去耐心激勵白上吹雪,其耐心程度無法獲得回復(V3 = 0); 故總共釣 299+29+1 = 329 竿,小於預測的 K = 330,並無法釣到「金鯉魚 王」。

若 V0 = 300,則白上吹雪在被激勵之前可以釣 300 竿;在第一次被激勵之 後其耐心程度回復至 V1 = 30,在下一次激勵之前可以釣 30 竿;截至目前 已可釣 300+30 = 330 竿,即可釣到「金鯉魚王」。 由上述可以得知,白上吹雪至少需要初始耐心程度 V0 = 300 才能夠釣到 「金鯉魚王」,故輸出 300。

Tags:
binary index tree binary search hololive math pokemon
出處:
TOI練習賽202112潛力組 [管理者:
pcshic (PCSHIC)
]


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