Contest Python: USACO Bronze › Checkpoint 2 — Mock Contest 2

Questions: Checkpoint 2 — Mock Contest 2

You have about 35–45 minutes to solve six problems. Each problem reads the whole contest input from standard input and prints the exact output. Read the input in your program with:

import sys
data = sys.stdin.read()

Write each answer as a complete program in your notebook, and run it with piped input, for example python my_solution.py < case.txt. Do not call input().

Question 1: Snack Sizes

The first line contains N M, the second line contains the smallest snack size each of N kids will accept, and the third line contains the sizes of M snacks. Each kid receives at most one snack, each snack goes to at most one kid, and a kid is happy when the snack's size is at least that kid's smallest accepted size. Print the maximum number of happy kids. Sort both lists, then sweep the snacks from smallest to largest, giving each snack to the least demanding kid still waiting when it is big enough and skipping it otherwise. In the sample, the snack of size 2 is too small for every kid still waiting and is skipped, and the final snack 8 is the only one large enough for the kid who needs 7, raising the answer from 3 to 4.

Constraints. 1 <= N, M <= 100000. Every size is between 1 and 1000000. Trying every way to hand out the snacks will not finish in time.

Sample Input

4 5
3 1 7 5
2 4 1 6 8

Sample Output

How this is checked: Checked by running your program on 5 test inputs (1 sample, 4 hidden) and comparing its output word by word.

Your code

Also check yourself

The automatic check cannot see these, so tick each one when your work does it.

Sort both lists, then sweep the snacks from smallest to largest, giving each snack to the least demanding kid still waiting when it is big enough and skipping it otherwise.

For parents and teachers: report a problem

Question 2: Water Jug Log

The first line contains the capacities A B of jug A and jug B, and both jugs start empty. The second line is N, and each of the next N lines is one command: FILL A or FILL B fills that jug to its capacity, EMPTY A or EMPTY B empties it, and POUR A B or POUR B A pours from the first jug named into the second until the first is empty or the second is full, whichever happens first. Apply every command in order and print the final amounts in jug A and jug B, separated by one space. In the sample, the first pour stops when jug B is full and leaves 2 in jug A, and the final pour moves only 1 unit because jug B already holds 2 of its 3.

Constraints. 1 <= A, B <= 1000000000. 1 <= N <= 100000. Every command is one of the six commands listed above.

Sample Input

5 3
6
FILL A
POUR A B
EMPTY B
POUR A B
FILL A
POUR A B

Sample Output

4 3

How this is checked: Checked by running your program on 5 test inputs (1 sample, 4 hidden) and comparing its output word by word.

Your code

For parents and teachers: report a problem

Question 3: Savings Goal Days

The first line contains N Q, the second line contains the positive amount saved on each of N days in order, and the third line contains Q savings goals. For each goal, print on its own line the first day number (days are numbered from 1) on which the total saved so far is at least that goal, or -1 if the total never reaches it. Build one cumulative-sum array; because every amount is positive, the running totals only grow, so binary-search that array for each goal. In the sample, the goal 14 is reached exactly on the final day, and the goal 15 is never reached.

Constraints. 1 <= N, Q <= 100000. Every daily amount is between 1 and 1000, and every goal is between 1 and 1000000000000. Scanning the days again for every goal will not finish in time.

Sample Input

5 5
3 1 4 1 5
4 1 9 14 15

Sample Output

How this is checked: Checked by running your program on 5 test inputs (1 sample, 4 hidden) and comparing its output word by word.

Your code

Also check yourself

The automatic check cannot see these, so tick each one when your work does it.

Build one cumulative-sum array
binary-search that array for each goal.

For parents and teachers: report a problem

Question 4: Road Trip Refuels

The first line contains L D N: the destination is at position L on a straight road, a full tank drives exactly D units, and there are N fuel stations. The second line contains the station positions, and it is missing when N is 0. You start at position 0 with a full tank, and a stop at a station fills the tank again. Print the fewest stops needed to reach the destination, or -1 if it cannot be reached. Sort the stations, and from each stopping point drive to the farthest station you can still reach, until the destination itself is within reach. In the sample, stopping at the first reachable station 2 would waste fuel; the greedy stops are 5, 11, and the final input station 16, from which the destination 20 is within reach.

Constraints. 1 <= L, D <= 1000000000 and 0 <= N <= 100000. Station positions are distinct, and every station lies strictly between 0 and L. Trying every set of stops will not finish in time.

Sample Input

20 6 5
5 11 2 8 16

Sample Output

How this is checked: Checked by running your program on 5 test inputs (1 sample, 4 hidden) and comparing its output word by word.

Your code

Also check yourself

The automatic check cannot see these, so tick each one when your work does it.

Sort the stations, and from each stopping point drive to the farthest station you can still reach, until the destination itself is within reach.

For parents and teachers: report a problem

Question 5: Lead Changes

The first line is N, and each of the next N lines contains one scoring event T p: team T, which is A or B, scores p points. Both teams start at 0. After each event, the team with more points is leading, and nobody is leading while the scores are tied. A lead change happens after an event when a team is leading and the most recent earlier leader (from the last earlier event after which someone was leading) was the other team; the first time any team leads is not a change, and a tie does not end the old leader's run. Print the number of lead changes. In the sample, team A leads again after the tie at 5 5, which is not a change because A also led just before the tie, and the final event puts B in front for the third lead change.

Constraints. 1 <= N <= 100000. 1 <= p <= 1000. Every team letter is A or B.

Sample Input

7
A 2
B 2
B 1
A 3
B 2
A 1
B 3

Sample Output

How this is checked: Checked by running your program on 5 test inputs (1 sample, 4 hidden) and comparing its output word by word.

Your code

For parents and teachers: report a problem

Question 6: Solar Panel Placement

The first line contains R C K, and the next R lines contain a grid of C integer sunlight readings; a reading is negative where a shadow falls. A square solar panel covers exactly K rows and K columns of neighboring cells and must lie completely inside the grid. Build one 2D prefix-sum grid, use the four-term inclusion-exclusion formula to total every possible K-by-K placement, and print the greatest placement total. In the sample, the best placement sits in the bottom-right corner, and the bottom-right reading 9 changes the answer from 8 to 16.

Constraints. 1 <= K <= R <= 1000, K <= C <= 1000, and R * C <= 1000000. Every reading is between -1000000000 and 1000000000, so every placement total may be negative. Re-adding the K * K cells of every placement will not finish in time.

Sample Input

Sample Output

How this is checked: Checked by running your program on 6 test inputs (1 sample, 5 hidden) and comparing its output word by word.

Your code

Also check yourself

The automatic check cannot see these, so tick each one when your work does it.

Build one 2D prefix-sum grid, use the four-term inclusion-exclusion formula to total every possible K-by-K placement

For parents and teachers: report a problem

Back to Checkpoint 2 — Mock Contest 2