Contest Python: USACO Bronze › Unit 3 — Fast Enough?
Exercises: Unit 3 — Fast Enough?
Each problem is a program that reads the whole input from stdin and prints the exact output (real contest style — no solve() wrapper): import sys; data = sys.stdin.read(), parse it, decide which approach is fast enough, then print. Write each program in a .py file and run it with piped input, e.g. python my_solution.py < case.txt.
Exercise 1: Count Scores at Least the Target
The first line contains N T. The second line contains N scores. Print how many scores are at least T. Scan every score, including the last one. In the sample, the last score is the third qualifying score.
Constraints. 1 <= N <= 200000. An O(n²) approach will not finish in time; use one O(n) scan.
Sample Input
6 80
72 91 80 64 79 95Sample Output
3How this is checked: Checked by running your program on 2 test inputs (1 sample, 1 hidden) and comparing its output word by word.
Exercise 2: First Time the Total Reaches the Goal
The first line contains N G. The second line contains N positive points earned in order. Print the 1-based turn when the running total first becomes at least G, or -1 if it never does. In the sample, only the last value makes the total reach the goal.
Constraints. 1 <= N <= 200000. Recomputing every earlier total would be O(n²) and time out; keep one running total for O(n).
Sample Input
5 25
4 6 3 5 7Sample Output
5How this is checked: Checked by running your program on 2 test inputs (1 sample, 1 hidden) and comparing its output word by word.
Exercise 3: Longest Winning Streak
The first line contains N T. The second line contains N scores in game order. A winning game has a score at least T. Print the length of the longest unbroken winning streak. The sample's best streak ends at the last score.
Constraints. 1 <= N <= 200000. Checking every possible start and end would be O(n²) and time out; update a current streak and a best streak in O(n).
Sample Input
8 10
10 12 4 11 3 14 15 16Sample Output
3How this is checked: Checked by running your program on 2 test inputs (1 sample, 1 hidden) and comparing its output word by word.
Exercise 4: Most Frequent Number
The first line is N. The second line contains N positive integers. Print the number that appears most often. If several numbers tie, print the smaller number. Use a dictionary to keep a running frequency for each value. In the sample, the final input value creates the winning frequency.
Constraints. 1 <= N <= 200000. Comparing every value with every other value would be O(n²) and time out; count once and inspect the dictionary pairs for O(n).
Sample Input
7
8 3 8 5 3 8 3Sample Output
3How this is checked: Checked by running your program on 3 test inputs (1 sample, 2 hidden) and comparing its output word by word.
Exercise 5: Pair Sum Check
The first line contains N K. The second line contains N integers. Print YES if numbers at two different positions add to K; otherwise print NO. Keep previously visited numbers in a dictionary. In the sample, the last value completes the only matching pair.
Constraints. 2 <= N <= 200000. Trying every pair is O(n²) and will time out; use one O(n) pass with a dictionary.
Sample Input
6 17
4 12 8 2 20 5Sample Output
YESHow this is checked: Checked by running your program on 4 test inputs (1 sample, 3 hidden) and comparing its output word by word.
Exercise 6: Smallest Neighbor Gap
The first line is N. The second line contains N different integers. Print the smallest positive difference between two values. Rearrange the list in place with .sort(), then compare neighboring values in one scan. In the sample, the final input value belongs to the closest pair.
Constraints. 2 <= N <= 200000. Trying every pair is O(n²) and will time out; one in-place sort plus one scan is O(n log n).
Sample Input
6
40 3 22 15 60 21Sample Output
1How this is checked: Checked by running your program on 3 test inputs (1 sample, 2 hidden) and comparing its output word by word.
Exercise 7: First Repeated Value
The first line is N. The second line contains N positive integers in arrival order. Print the first value whose arrival repeats a value seen earlier, or -1 if every value is different. In the sample, the first repeat occurs at the last position.
Constraints. 1 <= N <= 200000. Rescanning all earlier arrivals for each value would be O(n²) and time out; remember arrivals in a dictionary for O(n).
Sample Input
7
9 2 14 6 3 11 2Sample Output
2How this is checked: Checked by running your program on 4 test inputs (1 sample, 3 hidden) and comparing its output word by word.
Exercise 8: Longest Distance Within a Limit
The first line contains N D. The second line contains N different positions along a path. After rearranging the positions in place with .sort(), print the largest gap between neighboring positions that is at most D, or -1 if no neighboring gap qualifies. In the sample, the final input position creates the answer.
Constraints. 2 <= N <= 200000. Checking every pair is O(n²) and will time out; one in-place sort and one scan is O(n log n).
Sample Input
7 12
40 3 18 70 90 55 81Sample Output
11How this is checked: Checked by running your program on 4 test inputs (1 sample, 3 hidden) and comparing its output word by word.
Exercise 9: Most Valuable Team
The first line is N. The second line contains N player values, which may be negative. A team is one or more neighboring players in the given order. Print the largest team total. If the running team becomes worse than starting again at the current player, start a new team there. In the sample, the decisive final player extends the best team. Keep a running total and running best rather than adding every possible team again.
Constraints. 1 <= N <= 200000. Trying every possible start and end is O(n²) and will time out; maintain running values in one O(n) scan.
Sample Input
6
-5 2 -8 1 4 10Sample Output
15How this is checked: Checked by running your program on 3 test inputs (1 sample, 2 hidden) and comparing its output word by word.