703 . 補給兵問題

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

1xlc

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

100.0% (2/2)

Tags

apcsc apcsc-enumerate

Description

南宋年間，蒙古大軍自北方入侵中原，烽火四起，百姓生靈塗炭、苦不堪言。南宋趙氏朝廷退至臨安，坐守南方膏腴之地。其中，襄陽城堪稱通往南方的咽喉。現在，蒙古兵臨城下，干戈四起，守城將領已經做好準備了，而你則是負責運送砲彈的小兵。

已知襄陽城的城牆上有 N 個哨站，編號為 0 至 N−1，呈環狀排列，且對於所有的 0≤i<N，編號 i 的哨站有一條單行道通往編號 (i+1)modN 的哨站。每一個哨站有各自對於砲彈的需求量，一個正整數 pi 代表第 i 個哨站需要 pi 石的砲彈。而一旦你經過了一個哨站，你就會恰將 pi 石的砲彈給那個哨站。一開始你在編號為 0 的哨站，而你將收到 M 個型如「請送出至少 qi 個砲彈」的任務。也就是說，你會從現在這個哨站開始送砲彈，然後走到下一個哨站繼續送，直到送出的砲彈數量達到 qi 個為止。如果你從編號為 s 的哨站開始，送到編號 t 的哨站剛好送出足夠的砲彈的話，則你會停在編號為 (t+1)modN 的哨站，才算任務完成（0≤s,t<N）。

給定以上的資訊，請問你最後會停在哪個哨站？

Input Format

輸入將有 3 行。第一行包含兩個正整數 N,M(1≤N≤200000,1≤M≤20000)。第二行將包含 N 個正整數，第 i 個數字代表 pi−1(∑i=0N−1pi≤109)。最後一行將有 M 個正整數，其中第 j 個代表 qj(qj≤∑i=0N−1pi)。

此外，對於佔分 20% 的測試資料，還額外滿足 1≤N,M≤100。

Output Format

請輸出一個數字 k，代表最後你會停在哪一個哨站。

Sample Input 1

5 3
1 1 1 1 1
1 2 3

Sample Output 1

1

Sample Input 2

6 3
1 2 4 8 16 32
31 32 15

Sample Output 2

4

Sample Input 3

8 8
7 1 2 2 7 1 2 2
7 1 2 3 9 8 7 2

Sample Output 3

3

Hints

Problem Source

APCS 202007 第 3 題

Subtasks

No. Testdata Range Constraints Score
1 0~2 範例測資 0
2 0~16 1≤n,m≤100 20
3 0~35 無額外限制 80

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2000 262144 65536 1 2 3
1 2000 262144 65536 1 2 3
2 2000 262144 65536 1 2 3
3 2000 262144 65536 2 3
4 2000 262144 65536 2 3
5 2000 262144 65536 2 3
6 2000 262144 65536 2 3
7 2000 262144 65536 2 3
8 2000 262144 65536 2 3
9 2000 262144 65536 2 3
10 2000 262144 65536 2 3
11 2000 262144 65536 2 3
12 2000 262144 65536 2 3
13 2000 262144 65536 2 3
14 2000 262144 65536 2 3
15 2000 262144 65536 2 3
16 2000 262144 65536 2 3
17 2000 262144 65536 3
18 2000 262144 65536 3
19 2000 262144 65536 3
20 2000 262144 65536 3
21 2000 262144 65536 3
22 2000 262144 65536 3
23 2000 262144 65536 3
24 2000 262144 65536 3
25 2000 262144 65536 3
26 2000 262144 65536 3
27 2000 262144 65536 3
28 2000 262144 65536 3
29 2000 262144 65536 3
30 2000 262144 65536 3
31 2000 262144 65536 3
32 2000 262144 65536 3
33 2000 262144 65536 3
34 2000 262144 65536 3
35 2000 262144 65536 3
Submit
Back to Top