Description
Chad has been looking for a rare anime garage kit for years.
He just learned about the seller that has exactly what he wants. The seller is a character known for strange rules of trade:
she never gives any change.
The price of the garage kit is M. Chad has brought N coins with him such that the i-th coin has value ai
. He is determined to
get the garage kit and is willing to pay more than M, if necessary, but he wants to overpay as little as possible. Moreover, he
wants to minimize the number of coins he uses.
Please help him figure out which coins he should use for the purchase.
Input
The first line contains one positive integer M, the price of the garage kit. The price will not exceed 10,000.
The following line contains one positive integer N, the number of coins Chad has, N <= 100.
The next N lines contain poisitve integers indicating the value of each coin that Chad has. The values archer any positive
integers no greater than 10,000.
Chad has brought enough money to buy the kit, so the total value of his coins will always be equal to or greater than the
price of the kit.
Output
Output a single line containing two integers: the total amount paid and the total number of coins used.
Example 1
Input:
14
3
5
10
20
Output:
15 2
Example 2
Input:
5
3
2
3
5
Output:
5 1
Page 1/1
Array Partition
Given an array A of N natural numbers and a number M (1 <= M <= N). Split the given array into M consecutive subarrays
such that the maximum sum of the values in the subarrays is minimal.
For example: A = [4,3,2,1], M = 3. The optimal split is {4}, {3}, {2,1}. The maximum sum of all subarrays is 4, which is
minimum possible for 3 splits. (Any other split would result in at least one subarray whose sum of values is greater than 4.)
Input
The first line contains 2 integer N, M as described above. 1 <= M <= N <= 10^5.
In the next line, there are N natural numbers indicating the elements of the array. 0 <= A[i] <= 10^9 for 1 <= i <= N
Output
Output one integer followed by a newline, indicating the minimal maximum sum of any subarray in the optimal split.
Example 1
Input:
4 3
4 3 2 1
Output:
4
Example 2
Input:
4 1
4 3 2 1
Output:
10
Example 3
Input:
3 2
1 100 2
Output:
101
Page 1/2
Badminton Class
Kou school is preparing for badminton championship. In this championship players are mixed doubles. The coach is
creating the pairs/teams for the championship according to students’ skill levels based on their previous year performance.
He wants to place the male student with the highest skill levels with the top female student. Then the second ranking male
student with the second ranking female students. And so on and so forth until the largest number of mixed doubles is built.
Your task is to determine how many male students are left unmatched and smallest skill level of such unmatched student.
Input
The first line of the input contains two integers M (1 <= M <= 10000) and F (1 <= F <= 10000), representing the number of
male and female students, respectively. Each of the following M lines describe the skill levels of the male students. Then
each of the following F lines describe the skill level of the female students. All skill levels are between 2 and 60.
Output
You should print a line that contains the number of male students that could not be matched. If this number is not zero, you
should also print an additional number indicating the skill level of the least skilled unmatched male student.
Example 1
Input:
4 4
26
25
2
21
35
25
23
24
Output:
0
Example 2
Input:
1 2
20
30
40
Output:
0
Example 3
Input:
4 2
5
5
10
15
20
18
Page 2/2
Output:
2 5
Page 1/2
Xiangliu
Polycephalic or multi-headed animals are rare in biology but common in mythology and heraldry: multi-headed snakes, like
the 8-headed Yamata no Orochi in Japanese mythology, the 9-headed Lernaean Hydra in Greek mythology and 3-headed
Cerberus in Greek mythology.
Xiangliu, known in the Classic of Mountains and Seas,
is a N-headed snake monster that brings flooding and
destruction in Chinese mythology.
Now it appears at the plain of Xia Kingdom. The king Yu
is alarmed, and calls on his archers to slay the serpent
and save the kingdom.
To slay Xiangliu and stop flooding, the archers must
shoot down all its heads. There are M archers in the
kingdom. Each archer can shoot down one of the
snake’s heads. The heads of the snake are of different
sizes. In order to shoot down a head, an archer have to
be able to draw a longbow which had a draw weight
proportional to the size of that head. The archers
demand that for shooting down a head, an archer must
be paid a wage equal to one gold coin per each pound
of the archer’s maximum draw weight.
After having lost a lot of money due to flooding, Yu wants to minimize the expense of slaying Xiangliu. Your job is to help the
king, decide how many and which archers to hire.
Input
The first line contains 2 integers, indicating the number N of heads that Xiangliu has, and the number m of archers in the
kingdom. 1 ≤ N,M ≤ 10^5.
The next N lines contain positive integers no greater than 10^9 that give the sizes of the snake’s heads. The i-th integer ai
means that the archer needs to be able to draw a longbow with a draw weight no less than ai pounds to shoot down the i-th
head of Xiangliu.
The following M lines each contain a positive integer no greater than 10^9, and specify the maximum draw weights of the
archers in the kingdom, also in pounds.
Output
Output a number followed by a newline, indicating the minimum number of gold coins that the kings needs to pay to slay the
serpent. If it is not possible for archers of Xia to slay the dragon, output the line “Xia is doomed!”.
Example 1
Input:
2 3
4
5
4
8
7
Output:
11
Example 2
Input:
3 1
Page 2/2
1
1
1
100
Output:
Xia is doomed!
Example 3
Input:
3 2
1 100 2
Output:
101
Page 1/2
Sprinklers
Farmer John has a large field, and he is thinking of planting sweet corn in some part of it. After surveying his field, FJ found
that it forms a horizontal strip l meters long and w meters wide.
There are n sprinklers installed at the horizontal center line of the strip. For each sprinkler you are given its radius of
operation and its position as the distance from the left end of the center line. Farmer John wants to plant sweet corn in the
whole field, but he wishes to turn on as few sprinklers as possible to save the water.
Find the minimum number of sprinklers that need to be turned on in order to water the entire field.
Input
The first line contains integer numbers n, l and w with
1 ≤ n ≤ 10,000, 1 ≤ l ≤ 10,000,000, and 1 ≤ w ≤ 100.
The next n lines contain two integers giving the
position x (0 ≤ x ≤ l) and radius of operation r (1 ≤ r ≤
1000) of a sprinkler.
The picture above illustrates the first case from the
sample input.
Output
Output one integer followed by a newline: the minimum number of sprinklers needed to water the entire strip.
If it is impossible to water the entire strip, output -1.
Example 1 (shown in the image above)
Input:
8 20 2
5 3
4 1
1 2
7 2
10 2
13 3
16 2
19 4
Output:
6
Example 2
Input:
3 10 1
3 5
9 3
6 1
Output:
2
Example 3
Page 2/2
Input:
3 10 1
5 3
1 1
9 1
Output:
-1
