Contest Python: USACO Bronze › Unit 5 — Searching & Complete Search
Exercises: Unit 5 — Searching & Complete Search
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, 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: Many Number Queries
The first line contains N Q, the second line contains N distinct integers, and the third line contains Q query integers; sort the stored integers once, then print YES or NO on its own line for each query to say whether it is present, using binary search for every query. In the sample, the final query is present only at the last position after sorting.
Constraints. 1 <= N, Q <= 200000.
-1000000000 <= value, query <= 1000000000.
A linear scan for every query will not finish in time.
Sample Input
5 4
11 2 7 4 19
5 2 12 19Sample Output
NO
YES
NO
YESHow 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: Count Many Targets
The first line contains N Q, the second line contains N integers, and the third line contains Q query integers; sort the stored integers once, then print on its own line how many times each query occurs, using two binary searches for its boundary positions. In the sample, the final query equals the final stored value, and all of its copies reach the last position after sorting.
Constraints. 1 <= N, Q <= 200000.
-1000000000 <= value, query <= 1000000000.
A query may be absent, and scanning all values for every query will not finish in time.
Sample Input
8 4
3 9 1 9 6 9 4 9
3 5 10 9Sample Output
1
0
0
4How 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: Many Insertion Positions
The first line contains N Q, the second line contains N distinct integers, and the third line contains Q query integers; sort the stored integers once, then print on its own line the zero-based position where each query could be inserted while keeping the list sorted, before any value greater than or equal to it. In the sample, the final stored value becomes last after sorting and is the decisive comparison for the final query's returned position N.
Constraints. 1 <= N, Q <= 200000.
-1000000000 <= value, query <= 1000000000.
Scanning the stored values for every query will not finish in time.
Sample Input
6 4
8 1 13 3 17 19
8 0 13 20Sample Output
2
0
3
6How 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: Pair Sum by Complement Search
The first line contains N T, and the second line contains N integers; print YES if two values at different positions sum to T, or NO otherwise. Sort the values, then for each position binary-search only later positions for its complement; do not use a scan whose two ends move inward. In the sample, the only successful pair uses the final input value, which is also last after sorting.
Constraints. 2 <= N <= 200000.
-1000000000 <= value, T <= 1000000000.
Checking every pair with nested loops will not finish in time.
Sample Input
5 23
1 8 12 4 19Sample Output
YESHow this is checked: Checked by running your program on 5 test inputs (1 sample, 4 hidden) and comparing its output word by word.
Exercise 5: Closest Pair Gap
The first line is N, and the second line contains N distinct integers; print the smallest absolute difference between any two values. Sort the values, then inspect each adjacent pair from left to right, because the closest pair must be adjacent after sorting; in the sample, the decisive pair ends at the final input value, which is last after sorting.
Constraints. 2 <= N <= 200000.
-1000000000 <= value <= 1000000000.
Checking all O(n²) pairs will not finish in time.
Sample Input
6
2 8 13 19 30 31Sample 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 6: Three Values Make the Target
The first line contains N T, and the second line contains N distinct positive integers; print YES if three values at three different positions sum to T, or NO otherwise. Use three fixed-depth nested loops that choose positions in increasing order; in the sample, the only successful triple uses the final input value.
Constraints. 3 <= N <= 150.
1 <= value, T <= 1000000.
Do not generate subsets or permutations.
Sample Input
7 59
2 5 9 14 20 31 40Sample 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 7: Smallest Delivery Capacity
The first line contains N D, and the second line contains N positive package weights in delivery order; one truck carries consecutive packages each day without changing their order, and its daily load cannot exceed one fixed capacity. Print the smallest capacity that delivers every package in at most D days; binary-search the answer and test each candidate with one left-to-right scan. In the sample, the final package supplies the decisive largest-weight boundary.
Constraints. 1 <= D <= N <= 200000.
1 <= weight <= 1000000000.
Trying every possible capacity will not finish in time.
Sample Input
5 3
4 2 7 3 9Sample Output
10How this is checked: Checked by running your program on 5 test inputs (1 sample, 4 hidden) and comparing its output word by word.
Exercise 8: Values in Each Range
The first line contains N Q, the second line contains N distinct integers, and the next Q lines each contain inclusive bounds L R; sort the values once and print, one answer per line, how many values lie from L through R. Use two binary searches per query: the first value not less than L, and the first value greater than R; in the sample, the final query includes the final input value, which is last after sorting.
Constraints. 1 <= N, Q <= 200000.
-1000000000 <= value, L <= R <= 1000000000.
Scanning all values for every range will not finish in time.
Sample Input
5 4
10 2 7 15 20
1 6
7 15
11 14
16 20Sample Output
1
3
0
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 9: Sum-and-Product Lock
The input contains two integers S P; a three-digit lock code has a first digit from 1 through 9 and two later digits from 0 through 9, its three digits add to S, and their product equals P. Print the smallest valid three-digit code, or NONE if no code works, by enumerating every candidate with three fixed-depth nested loops; in the sample, the final input value P rules out earlier sum-only candidates and makes 147 the smallest valid code.
Constraints. 0 <= S <= 27.
0 <= P <= 729.
Do not generate permutations or use recursion.
Sample Input
12 28Sample Output
147How this is checked: Checked by running your program on 4 test inputs (1 sample, 3 hidden) and comparing its output word by word.