Riolku's Mock CCC S4 - Clumsy Cindy - Olympiads Online Judge

Riolku's Mock CCC S4 - Clumsy Cindy

Points: 12 (partial)

Time limit: 2.0s

Memory limit: 512M

Author:

Problem type

Cindy is trying to fill up her row of buckets!

Cindy has a row of $N$ $N$ buckets, each initially empty. She wants to fill them to different capacities, depending on the bucket sizes. To accomplish this, she will pour a certain amount into each bucket.

On one move, she pours $a_i$ $a_{i}$ units into bucket $i$ $i$ , but unfortunately, in her clumsiness, $b_i$ $b_{i}$ units get poured into the next bucket in line! If she pours into the last bucket, she clumsily spills onto the grass instead.

Cindy wants to fill each bucket to a certain capacity $c_i$ $c_{i}$ . If a bucket's water total exceeds the given capacity, the excess will be spilled onto the grass.

Cindy wants to fill her buckets as fast as possible. She can pour into each bucket as many times as she wants. She wonders: what is the minimum number of moves she has to make to fill all her buckets?

Constraints

$1 \le N \le 5\,000$ $1 \leq N \leq 5 000$

$1 \le a_i, b_i, c_i \le 5\,000$ $1 \leq a_{i}, b_{i}, c_{i} \leq 5 000$

Subtask 1 [2/15]

$1 \le N \le 10$ $1 \leq N \leq 10$

$1 \le a_i, b_i, c_i \le 2$ $1 \leq a_{i}, b_{i}, c_{i} \leq 2$

Subtask 2 [5/15]

$1 \le N \le 700$ $1 \leq N \leq 700$

$1 \le a_i, b_i, c_i \le 700$ $1 \leq a_{i}, b_{i}, c_{i} \leq 700$

Subtask 3 [8/15]

No additional constraints.

Input Specification

The first line will contain $N$ $N$ , the number of buckets.

The next line will contain $N$ $N$ integers, the values of $c_i$ $c_{i}$ .

The next $N$ $N$ lines will contain $a_i$ $a_{i}$ and $b_i$ $b_{i}$ . Note that $b_N$ $b_{N}$ indicates the amount of water spilled onto the grass, and can be ignored.

Output Specification

Output the minimum number of times Cindy has to pour to fill all the buckets.

Sample Input

Copy

Sample Output

Copy

Explanation for Sample Output

After pouring once into the first bucket, the amount of water in each bucket is:

Copy

6 5 0 0

After pouring once into the second bucket:

Copy

6 9 3 0

After pouring twice into the second-last bucket:

Copy

6 9 3 8

Note that overflow in buckets $3$ $3$ and $4$ $4$ is discarded.

It can be shown that it is impossible to fill the buckets in 3 moves or less.

Comments

0

TheGreenLobster commented on Sept. 19, 2023, 9:54 p.m. ← edit 2 →

I don't get what it wants us to do, are we supposed to simply output the amount of times the user attempts to fill in the $a_i$ $a_{i}$ and $b_i$ $b_{i}$ values till all the buckets are filled? The sample input and output doesn't clarify enough details regarding what were actually trying to do.

I'd think we're supposed to make some algorithm that finds all $N$ $N$ of $a_i$ $a_{i}$ and $b_i$ $b_{i}$ values to fill it up in the shortest amount of time, but the sample run doesn't exactly show that.

0

BalintR commented on Sept. 19, 2023, 10:39 p.m.

The Output Specification explains what you're supposed to output:

Output the minimum number of times Cindy has to pour to fill all the buckets.