有 $n$ 個房間排列成一個圓環，以順時針方向由 $0$ 到 $(n - 1)$ 編號。玩家只能順時針方向依序通過這些房間。每當離開第 $i$ 號房間進入下一個房間時，即可獲得 $p(i)$ 點。玩家必須依序取得 $m$ 把鑰匙，鑰匙編號由 $0$ 至 $(m-1)$，兌換編號 $i$ 的鑰匙所需的點數為 $Q(i)$。一旦玩家手中的點數達到 $Q(i)$ 就會自動獲得編號 $i$ 的鑰匙，而且手中所有的點數就會被「全數收回」，接著要再從當下所在的房間出發，重新收集點數兌換下一把鑰匙。遊戲開始時，玩家位於 $0$ 號房。請計算玩家拿到最後一把鑰匙時所在的房間編號。
以下是一個例子。有 7 個房間，$p(i)$ 依序是 $(2, 1, 5, 4, 3, 5, 3)$ ，其中 0 號房間的點數是 $2$ 。假設所需要的鑰匙為 $3$ 把， $Q(i)$ 依序是 (8, 9, 12) 。從 0 號房出發，在「離開 2 號房，進入 3 號房」時，獲得恰好 $2+1+5 = 8$ 點，因此在進入 3 號房時玩家兌換到 0 號鑰匙；接著從 3 號房開始繼續累積點數，直到「離開 5 號房，進入 6 號房」時，手中的點數為 $12$，於是在進入 6 號房時獲得 1 號鑰匙，手中點數再次被清空。最後，從 6 號房出發，直到「離開 3 號房，進入 4 號房」時，方可獲得至少 $12$ 點的點數，來兌換最後一把鑰匙。因此，拿到最後一把鑰匙時所在的房間編號為 4 。
一開始在編號 0 的房間，依據接收到 $m$ 個任務，請求出完成第 $m$ 個任務後會停在哪個編號的房間？
第一行包含兩個正整數 $n, m (1\leq n\leq 200000, 1\leq m \leq 200000)$。
第二行包含 $n$ 個正整數 $p_0, p_1, p_2, \dots, p_{n-1}$，$p$ 的總和不超過 $10^9$。
第三行包含 $m$ 個正整數 $Q_0, Q_1, Q_2, \dots, Q_{m-1}$，$Q_i$ 不會超過 $p$ 的總和。
配分
輸出一個非負整數表示最後停在哪個編號的房間
7 3 2 1 5 4 3 5 3 8 9 12
4
4 3 1 3 5 7 4 2 2
0
| ID | User | Problem | Subject | Hit | Post Date |
沒有發現任何「解題報告」 |
|||||