[Solved] Algorithm Homework9-No Change

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 toget the garage kit and is willing to pay more than M, if necessary, but he wants to overpay as little as possible. Moreover, hewants to minimize the number of coins he uses.Please help him figure out which coins he should use for the purchase.InputThe 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 positiveintegers 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 theprice of the kit.OutputOutput a single line containing two integers: the total amount paid and the total number of coins used.Example 1Input:14351020Output:15 2Example 2Input:53235Output:5 1Page 1/1Array PartitionGiven an array A of N natural numbers and a number M (1 <= M <= N). Split the given array into M consecutive subarrayssuch 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 isminimum possible for 3 splits. (Any other split would result in at least one subarray whose sum of values is greater than 4.)InputThe 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 <= NOutputOutput one integer followed by a newline, indicating the minimal maximum sum of any subarray in the optimal split.Example 1Input:4 34 3 2 1Output:4Example 2Input:4 14 3 2 1Output:10Example 3Input:3 21 100 2Output:101Page 1/2Badminton ClassKou school is preparing for badminton championship. In this championship players are mixed doubles. The coach iscreating 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 malestudent 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.InputThe first line of the input contains two integers M (1 <= M <= 10000) and F (1 <= F <= 10000), representing the number ofmale and female students, respectively. Each of the following M lines describe the skill levels of the male students. Theneach of the following F lines describe the skill level of the female students. All skill levels are between 2 and 60.OutputYou should print a line that contains the number of male students that could not be matched. If this number is not zero, youshould also print an additional number indicating the skill level of the least skilled unmatched male student.Example 1Input:4 4262522135252324Output:0Example 2Input:1 2203040Output:0Example 3Input:4 25510152018Page 2/2Output:2 5Page 1/2XiangliuPolycephalic or multi-headed animals are rare in biology but common in mythology and heraldry: multi-headed snakes, likethe 8-headed Yamata no Orochi in Japanese mythology, the 9-headed Lernaean Hydra in Greek mythology and 3-headedCerberus in Greek mythology.Xiangliu, known in the Classic of Mountains and Seas,is a N-headed snake monster that brings flooding anddestruction in Chinese mythology.Now it appears at the plain of Xia Kingdom. The king Yuis alarmed, and calls on his archers to slay the serpentand save the kingdom.To slay Xiangliu and stop flooding, the archers mustshoot down all its heads. There are M archers in thekingdom. Each archer can shoot down one of thesnakes heads. The heads of the snake are of differentsizes. In order to shoot down a head, an archer have tobe able to draw a longbow which had a draw weightproportional to the size of that head. The archersdemand that for shooting down a head, an archer mustbe paid a wage equal to one gold coin per each poundof the archers 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 theking, decide how many and which archers to hire.InputThe first line contains 2 integers, indicating the number N of heads that Xiangliu has, and the number m of archers in thekingdom. 1 N,M 10^5.The next N lines contain positive integers no greater than 10^9 that give the sizes of the snakes heads. The i-th integer aimeans 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-thhead of Xiangliu.The following M lines each contain a positive integer no greater than 10^9, and specify the maximum draw weights of thearchers in the kingdom, also in pounds.OutputOutput a number followed by a newline, indicating the minimum number of gold coins that the kings needs to pay to slay theserpent. If it is not possible for archers of Xia to slay the dragon, output the line Xia is doomed!.Example 1Input:2 345487Output:11Example 2Input:3 1Page 2/2111100Output:Xia is doomed!Example 3Input:3 21 100 2Output:101Page 1/2SprinklersFarmer John has a large field, and he is thinking of planting sweet corn in some part of it. After surveying his field, FJ foundthat 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 ofoperation and its position as the distance from the left end of the center line. Farmer John wants to plant sweet corn in thewhole 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.InputThe first line contains integer numbers n, l and w with1 n 10,000, 1 l 10,000,000, and 1 w 100.The next n lines contain two integers giving theposition x (0 x l) and radius of operation r (1 r 1000) of a sprinkler.The picture above illustrates the first case from thesample input.OutputOutput 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 25 34 11 27 210 213 316 219 4Output:6Example 2Input:3 10 13 59 36 1Output:2Example 3Page 2/2Input:3 10 15 31 19 1Output: