CCO '22 P2 - Rainy Markets

View as PDF

Submit solution

Points: 17 (partial)
Time limit: 1.5s
Memory limit: 1G

Author:
Problem types
Canadian Computing Olympiad: 2022 Day 1, Problem 2

There are N covered bus shelters, labelled 1, \dots, N. The i^\text{th} bus shelter can fit B_i people inside.

For each i \in \{1, \dots, N-1\}, there is a sidewalk connecting bus shelter i to bus shelter i+1, with an open-air market in the middle. The i^\text{th} market has U_i umbrellas for sale, each costing \$1.

Right now, the i^\text{th} market has P_i people inside, and every person is in a market so all the bus shelters are empty.

Suddenly, it starts raining, and everyone at market i has to decide between three possibilities:

  • to go to bus shelter i;
  • to go to bus shelter i+1; or
  • to stay and buy an umbrella.

If a person is unable to find a place in a bus shelter or buy an umbrella, they will get wet.

If everyone coordinates optimally, can they all stay dry? If so, what is the least amount of money they need to spend, and which bus shelter should each person move to?

Input Specification

The first line of input contains an integer N.

The second line of input contains N space-separated integers B_i (1 \le i \le N), the capacity of bus shelter i.

The third line of input contains N-1 space-separated integers P_i (1 \le i \le N-1), the number of people at market i.

The fourth line of input contains N-1 space-separated integers U_i (1 \le i \le N-1), the number of umbrellas for sale at market i.

Marks AwardedNumber of bus sheltersMaximum people/bus sheltersMaximum people/marketMaximum umbrellas/market
5 marks2 \le N \le 10^60 \le B_i \le 2 \cdot 10^90 \le P_i \le 10^9U_i = 0
5 marks2 \le N \le 2\,0000 \le B_i \le 4000 \le P_i \le 2000 \le U_i \le 200
6 marks2 \le N \le 4\,0000 \le B_i \le 4\,0000 \le P_i \le 2\,0000 \le U_i \le 2\,000
9 marks2 \le N \le 10^60 \le B_i \le 2 \cdot 10^90 \le P_i \le 10^90 \le U_i \le 10^9

Output Specification

If every person can stay dry either under an umbrella or at a bus shelter, the output will be N+1 lines:

  • the first line will contain the word YES.
  • the second line will contain the least amount of money necessary to spend on umbrellas
  • the next N-1 lines will each contain three space-separated integers:
    • the number of people at market i moving to bus shelter i
    • the number of people at market i buying an umbrella
    • the number of people at market i moving to bus shelter i+1, where 1 \le i \le N-1.

If not every person can stay dry, the output will be one line containing the word NO.

If there are multiple possible correct outputs, any correct output will be accepted.

Sample Input 1

3
10 15 10
20 20
0 0

Output for Sample Input 1

NO

Explanation of Output for Sample Input 1

There are 35 spots available at bus shelters and no umbrellas available, but there are 40 people in the markets.

Sample Input 2

3
10 15 10
20 20
0 11

Possible Output for Sample Input 2

YES
5
10 0 10
5 5 10

Explanation of Output for Sample Input 2

Looking at market 1, 10 people will go to bus shelter 1, no one will buy an umbrella, and 10 people will go to bus shelter 2.

Looking at market 2, 5 people will go to bus shelter 2, 5 people will stay and buy an umbrella, and 10 people will move to bus shelter 3.

In total, 5 umbrellas were purchased, which costs \$5.


Comments

There are no comments at the moment.