有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。
第一行有兩個正整數n 與m，
第二行有n個正整數，依序是各房間的點數p(i)，
第三行有 m 個正整數依序是各鑰匙需要的點數Q(i)。
同一行連續二數字間以空白隔開。n不超過2e5，m不超過2e4，p(i)總和不超過1e9，Q(i)不超過所有p(i)總和。
輸出拿到最後一把鑰匙時所在的房間編號。
7 3 2 1 5 4 3 5 3 8 9 12
4
| ID | User | Problem | Subject | Hit | Post Date |
沒有發現任何「解題報告」 |
|||||