Contest Python: USACO Bronze › Checkpoint 1 — Mock Contest 1
Questions: Checkpoint 1 — Mock Contest 1
You have about 40 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: Strongest Column
The first line contains R C, and the next R lines each contain C nonnegative integers. Build the grid as a list of lists, find the column with the greatest sum, and print its 1-based column number and sum separated by one space; if several columns have the same greatest sum, print the leftmost one. In the sample, the final grid value makes the last column the unique winner.
Constraints. 1 <= R, C <= 100.
Every grid value is between 0 and 1000.
Sample Input
3 4
2 5 1 4
3 1 6 2
1 2 0 7Sample Output
4 13How this is checked: Checked by running your program on 3 test inputs (1 sample, 2 hidden) and comparing its output word by word.
Question 2: Practice Room Gate
The input contains five flags in this order: registered guest badge blocked coach, where each flag is 1 for true or 0 for false. Print OPEN exactly when the person is not blocked, is either registered or a guest, and has either a badge or a coach; otherwise, print CLOSED. Write this rule as one Boolean expression that uses and, or, and not. In the sample, the final coach flag is the condition that opens the room.
Constraints. Each flag is 0 or 1.
The flags always appear in the stated order.
Sample Input
0 1 0 0 1Sample Output
OPENHow this is checked: Checked by running your program on 4 test inputs (1 sample, 3 hidden) and comparing its output word by word.
Question 3: Best Trading Gain
The first line is N, and the second line contains N daily prices in time order. Choose one day to buy and a later day to sell, and print the greatest possible gain sell price - buy price; print 0 if every later price is lower than or equal to every possible earlier buying price. Keep the smallest earlier price and best gain during one left-to-right scan. In the sample, the final price creates the greatest gain.
Constraints. 2 <= N <= 200000.
Every price is between 0 and 1000000000.
Checking every buy day with every later sell day is O(n²) and will not finish in time; use one O(n) scan.
Sample Input
7
9 7 12 5 11 6 15Sample Output
10How this is checked: Checked by running your program on 3 test inputs (1 sample, 2 hidden) and comparing its output word by word.
Question 4: Mutual Partner Picks
The first line is N, and each of the next N lines contains two different one-word names a b, meaning student a picked student b as a project partner; the same pick may appear more than once. Two students form a mutual pair when each picked the other. Store every pick as a (picker, picked) tuple in a set, and find the mutual pairs by testing whether the reversed tuple is also in the set. Print the number of mutual pairs on the first line, then each pair on its own line as x y with the alphabetically earlier name first, listing the pairs in alphabetical order of x and then of y by calling sorted with a named key function. When there are no mutual pairs, print only 0. In the sample, Mia Zoe is listed twice but still makes one pair, and the final pick Ben Ava completes the pair Ava Ben, raising the count from 2 to 3.
Constraints. 1 <= N <= 100000.
Each name starts with one uppercase English letter followed by lowercase English letters, and on every line a and b are different names.
Comparing every pick with every other pick will not finish in time.
Sample Input
7
Mia Zoe
Ava Ben
Zoe Mia
Ben Cy
Mia Zoe
Cy Ben
Ben AvaSample Output
3
Ava Ben
Ben Cy
Mia ZoeHow this is checked: Checked by running your program on 6 test inputs (1 sample, 5 hidden) and comparing its output word by word.
Question 5: Nearest Charging Station
The first line contains N Q, the second line contains the positions of N charging stations along one straight road, and the third line contains the positions of Q houses on the same road. For each house, print on its own line the distance to its nearest station. Sort the station positions once, then use binary search to find the first station at or after the house, and compare that station with the one just before it; at either end of the road, one of the two may not exist. In the sample, the house at 16 is 4 from both 12 and 20, and the final house at 30 lies beyond every station, so only the station before it exists and its answer is 10.
Constraints. 1 <= N, Q <= 100000.
Every position is between 0 and 1000000; station positions are distinct, and a house may stand at a station (distance 0).
Checking every station for every house will not finish in time.
Sample Input
4 5
12 3 20 8
1 9 16 20 30Sample Output
2
1
4
0
10How this is checked: Checked by running your program on 4 test inputs (1 sample, 3 hidden) and comparing its output word by word.
Question 6: Evenly Spaced Picks
The first line is N, and the second line contains N distinct positive integers. Print the number of ways to choose three positions i < j < k whose values are evenly spaced in that order, meaning value[j] - value[i] equals value[k] - value[j]; the common step may be positive or negative. Use three fixed-depth nested loops that choose the positions in increasing order. In the sample, the two evenly spaced picks are 2 8 14 and 8 11 14, and both use the final value; 2 5 8 does not count, because 8 comes before 5 in the list.
Constraints. 3 <= N <= 150.
Every value is between 1 and 1000000.
Do not generate subsets or permutations, and do not use recursion.
Sample Input
6
2 8 5 11 4 14Sample Output
2How this is checked: Checked by running your program on 5 test inputs (1 sample, 4 hidden) and comparing its output word by word.