Problem G
Working From Home
Nicole has started her own business which she runs from her home office. While on some days she works hard, on others she struggles to find the motivation to get back to the grind. Fortunately, she has come up with a new system: she sets a target to work $m$ minutes every workday, and if she hits her target she rewards herself by watching an episode of her favourite TV show.
Nicole quickly realized that on the days when she worked extra hard, she would then feel burnt out the next day and not even try to hit her target. All that extra work didn’t count in her new system! She thus decided that she would adjust her target each day by subtracting $p\% $ of how far she went above her previous day’s target from the baseline target $m$ (even if this makes the new target negative). Similarly, when she goes below her target, she would adjust the next day’s target by adding $p\% $ of how much she fell short to the baseline target $m$. To keep things simple, she’ll round up (towards positive infinity) when this gives a non-integer target.
As an example, if Nicole set her target to $m = 240$ minutes and worked $w_1 = 300$ minutes the first day ($60$ minutes above her target), and set $p = 50$, then she would watch an episode and set the second day’s target to $210$ minutes ($30$ minutes less than the baseline target). If she then worked $w_2 = 200$ minutes the second day, missing her new target by $10$ minutes, she wouldn’t earn an episode that day. She would then set her third day’s target to $5$ minutes above the baseline of $240$ minutes, making the next target $245$ minutes.
Given $m$, $p$, and how long Nicole works for the first $n$ workdays that she tries out this system, how many episodes of the show will she watch?
Input
Input begins with a line consisting of the three space-separated integers $1 \leq m \leq 1\, 000$, $0 \leq p \leq 100$, and $1 \leq n \leq 20\, 000$ as described in the problem statement, followed by $n$ lines each consisting of a single integer $0 \leq w_ i \leq 1\, 440$, the number of minutes that Nicole worked on the $i^{th}$ workday of her system.
Output
Output the number of days that Nicole reaches her target and watches an episode of her show.
| Sample Input 1 | Sample Output 1 |
|---|---|
240 50 3 300 200 245 |
2 |
| Sample Input 2 | Sample Output 2 |
|---|---|
480 20 2 434 489 |
0 |
