Problem B
Closing Early
Byron, the owner of a popular pizza shop renowned for its exclusive Hawaiian pizza, faces a unique challenge today. His shop operates on a strict policy: no pizza slices are wasted at the end of the day. Byron, an avid gamer, is eager to wrap up his day to play his favorite game, Hyper Space Pixel Conquerors (HSPC). However, he needs to ensure that he doesn’t have any leftover pizza slices before he leaves.
At the start of the day, Byron’s shop has exactly $R$ slices of Hawaiian pizza ready. Each whole pizza has exact $S$ slices of pizza. Throughout the day, $N$ customers will visit his shop in a sequential order. The $i^{\text {th}}$ customer will order $A_ i$ slices of pizza. Byron, will prepare pizzas as necessary. That is, he will prepare an additional pizza only if he does not have enough slices of pizza ready to serve the current customer.
Byron’s goal is to find the smallest number $k$ such that, after serving the first $k$ customers, he can close the shop without any pizza going to waste. The rest of the customers will be turned away. This occurs when the total number of pizza slices served, minus the initial $R$ slices, is exactly divisible by $S$. Formally, he wants to find the smallest number $k$ such that:
\[ A_1 + A_2 + \ldots + A_ k \equiv R \pmod{S}. \]Note that $k$ may be $0$ if $R = 0$ and no customers should be served.
Input
The first line containing three space-separated integers $R,S,N$ ($0 \leq R < S \leq 10^9$, $1 \leq N \leq 10^5$) — the remaining slices at the start of the day, the number of slices in a single pizza, and the number of customers, respectively.
The second line contains $N$ integers, where the $i^{\text {th}}$ integer is $A_ i$ ($0 < A_ i \leq 10^9$) — the number of slices of pizza the $i^{\text {th}}$ customer will order.
Output
A single integer $k$, the smallest number such that, after serving $k$ customers, Byron will have no pizza left over. Note that it may be the case that $k=N$. If Byron cannot close the shop without leftovers, then output $-1$.
| Sample Input 1 | Sample Output 1 |
|---|---|
7 10 5 2 1 4 12 6 |
3 |
| Sample Input 2 | Sample Output 2 |
|---|---|
0 7 3 1 2 3 |
0 |
| Sample Input 3 | Sample Output 3 |
|---|---|
5 9 7 4 2 1 3 3 6 3 |
-1 |
