[Solved] Algorithm Homework11-Ways to Add

A very simple problem: given a integer N, how many ways can K integers less than N add up to N?For example, for N = 6 and K = 2, there is 7 ways:0 + 61 + 52 + 43 + 34 + 25 + 16 + 0For N = 3 and K = 3, there is 10 ways.0 + 0 + 30 + 1 + 20 + 2 + 10 + 3 + 01 + 0 + 21 + 1 + 11 + 2 + 02 + 0 + 12 + 1 + 03 + 0 + 0The result could be very large, please output the answer modulo 1000000007 (10^9 + 7).Input One line containing two integers N, K, 1 <= N,K <= 100.Output A single line containing the answer modulo 10^9+7.Example 1Input:6 2Output:7Example 2Input:3 3Output:10Page 1/1Batch ProcessingSince Light Kingdom did not pay you salary for a whole year, you decided to leave and work for Conflict Empire. Now, youare again an operator of a super computing center and in control of M nodes.One day, a research institute from Conflict Empire submitted N computational tasks numbered from 1 to N. Given therunning time needed for each task, you are to distribute the tasks among the available nodes such that the node withheaviest workload completes as early as possible. Restriction: every node must process at least one task and must processa contiguous subsection of tasks. That is, you need to find a sequence 0 = L0 < L1 < < LM-1 < LM = N where the i-th nodeprocesses tasks Li-1+1, Li-1+2, , Li.InputThe first line of the input contains two integers N and M (1 <= M <= N <= 500), representing the number of tasks and thenumber of nodes you control, respectively. The second line contains N integers Ti(1 <= Ti < 10,000,000), representing thetime needed to complete each task.OutputPrint one line containing the input T1, T2, , TN divided into M parts such that the maximum sum of a single part isminimized. You should use character / to separate the parts and there must be a space character between every numbersor /s.If there is more than one solution, print the one that minimizes the sum of the first part, then the second part and so on.Example 1Input:9 3100 200 300 400 500 600 700 800 900Output:100 200 300 400 500 / 600 700 / 800 900Example 2Input:5 4100 100 100 100 100Output:100 / 100 / 100 / 100 100Page 1/2Date OverflowThe Year 2000 problem, also known as the Y2Kproblem, the Millennium bug, Y2K bug, the Y2K glitch,or Y2K, refers to events related to the formatting andstorage of calendar data for dates beginning in the year2000. Problems were anticipated, and arose, becausemany programs represented four-digit years with onlythe final two digits making the year 2000indistinguishable from 1900. The assumption of atwentieth-century date in such programs could causevarious errors, such as the incorrect display of datesand the inaccurate ordering of automated dated recordsor real-time events.In fact, there are also many other, similar problems.Suppose you have two computers C1 and C2 with different bugs:One with the ordinary Y2K bug (i.e. displaying a1:=1900 instead of b1:=2000), and one displaying a2:=1904 instead ofb2:=2040 (i.e., after the year 2040, the computer starts showing wrong year, starting with 1904).Now imagine you see C1 displays the year y1:=1941 and C2 the year y2:=2005.You know the actual year cannot be 1941 since in that case C2 will display the same year, and it can not be 2005,either. If the year is 2005, y1 would be 1905, hence its impossible.Looking at y1, we know the actual year could be 1941, 2041, 2141, etc.Then we calculate what C2 would display for 1941, 2041, 2141. It turns it will be 1941, 1905, 2005.So its possible the actual year is 2141.To calculate the actual year from those buggy computers requires a lot of work. You are hired to write a program to solvethis problem: Find the first possible real year, knowing what some other computers say (yi) and knowing their bugs(displaying ai instead of bi).Note that the year ai is definitely not after the year the computer was built. Since the actual year cant be before the year thecomputers were built, the year your program is looking for cant be before any ai .InputThe first line contains 1 integer n, the number of computers, 1 <= n <= 20.In the following n lines, each line contains 3 integer yi, ai, bi for each computer, 0< = ai <= yi < bi < 10000.yi is the year the i-th computer displays, bi is the year the bug will happen, and ai is the year displayed instead of bi.OutputOutput an integer z where z is the smallest possible year followed by a newline.If there is no such year less than 10000, output -1.Example 1Input:21941 1900 20002005 1904 2040Output:2141Example 2Page 2/2Input:21941 1900 20001940 1900 2000Output:-1Example 33101 100 200101 100 201101 100 202Output:101Example 421240 1234 12451913 1900 2001Output:2923Page 1/1Ayus CandiesAyu has three flavors of candies: banana flavored, grape flavored and cherry flavored. She also has three boxes numbered1, 2 and 3, each of which contains some of those candies. Now Ayu wants to move candies such that after the movement,each box contains the candies of only one flavor and no two boxes contain same flavored candies. Your task is to help Ayufind the minimum number of candy movements.InputThe input consists of only one line, containing 9 integers. The first three integers represent the number of banana flavored,grape flavored and cherry flavored candies in the first box, the second three integers represent the number of bananaflavored, grape flavored and cherry flavored candies in the second box, and the last three integers represent the number ofbanana flavored, grape flavored and cherry flavored candies in the third box. It is guaranteed that the total number ofcandies never exceeds 231.For example, the input 10 15 20 30 12 8 15 8 31 indicates that there are 10 banana flavored candies in box 1, 12grape flavored candies in box 2 and 31 cherry flavored candies in box 3.OutputPrint one line S x indicating which flavor of candies go in which box to minimize the number of candy movements. S is astring of three letters G , B and C (representing the flavor of grape, banana and cherry, respectively) indicating the flavorassociated with each box. x is the minimum number of candy movements.If there is more than one solution, print the alphabetically smallest string as S .Example 1Input:1 2 3 4 5 6 7 8 9Output:BCG 30Example 2Input:5 10 5 20 10 5 10 20 10Output:CBG 50Page 1/2Grocery DeliveryNia hates shopping and she really despises grocery shopping. She orders her groceries from a local store. In preparationfor drone deliveries, the store has new rules about packing items for delivery:they will deliver exactly two boxes to the customer (even if the order is small and one of the boxes is empty)the capacity of each box is the same and equal to W.Nia knows the volume occupied by each item on her shopping list: the ithitem has the volume vi. With the new rules, she hasto prioritize the items that she orders since not everything can fit in the two boxes. Her list is arranged in the order of priority:from the most important item to the least important one (i.e., the ithitem is always more important than the i+1stitem). Asshe prepares the list to send to the store, she only orders the highest priority items and as soon as she comes to an itemthat is too large to fit in the remaining space in the boxes, she skips that item and all the items below.The question is how many items from her list she will be able to order and which item should be placed in which box.InputThe first line contains 2 integers N and W, indicating the number of items and the capacity of a box, 1 <= N <= 200, 1 <= W<= 10000.The second line contains N integers, indicating the volume of items in Nias list. They are in the order of priority as describedabove.OutputThe first line of output should specify the number of items that can be ordered.For each item that can be ordered, output a line containing 1st if the item is to be placed in the 1st box and 2nd if theitem is to be placed in the 2nd box. If several arrangements of the items are possible, any one will do.Example 1Input:5 101 2 100 3 4Output:21st1stPage 2/2Explanation of example 1:Nia has to remove the 3rd item since its too large (this means that the 4th and the 5th items are also removed from theorder, even though they could fit in the second box).The first 2 items will be ordered. Any arrangement of the items in boxes will do.Example 2Input:7 5025 30 10 10 15 7 8Output:61st2nd2nd2nd1st1s