There are many great athletes in the world, and it's very hard to say who is the best in the world at a particular sport, especially when different athletes have won different competitions. Here's one possible system for ranking athletes:
1. Determine the number P of finishing places in any competition that will be worth points for athletes, and how many points Si each of those finishing places is worth. For example, for P = 3, one possible assignment would be 1000 points for 1st place, 500 for 2nd place, and 300 for 3rd place, and 0 for anything below that. (We assume there are no ties within competitions.)
2. Since not all competitions are equally important, assign a weight Wi to each one. The score gained by an athlete for a competition will be the points from step 1, modified by the weight for that competition. For example, we may decide that Olympics has a weight of 5, and, continuing with our example from above, the winner of the Olympics would receive 5 * 1000 = 5000 points.
3. Since we don't want to reward athletes simply for participating in many competitions, we count only the M highest scores received by an athlete across all competitions. For example, if M = 2 and an athlete earns scores of 1000*5, 500*1, and 300*3 in three different competitions, only the 5000 and 900 would be counted.
You are given the points per finishing place, the weights of the competitions, and the results of the competitions. Can you rank all of the athletes who appeared in the competitions? If multiple athletes have the same score, they will share the same rank and listed in alphabetical order of their names.
The first line of the input gives the number of test cases, T. T test cases follow; each test case consists of the following:
1. One line with an integer P, the number of top places for which points are awarded.
2. One line consists with P integers representing the scores Si for the top places, starting with first place and continuing down the places.
3. One line with an integer N, the number of competitions.
4. N lines, each of which represents a competition. Each line begins with Wi, the weight of this competition, and continues with the P names of the athletes who finished in the top P places. They are listed in descending order starting from first place.
5. One line with an integer M, the maximum number of competitions counted toward an athlete's score.
For each test case, output one line containing "Case #x:", where x is the test case number (starting from 1). Then output one line for each athlete, from highest rank to lowest rank, with the format r: name, where r is the rank of the athlete and name is the name of the athlete. You need to rank all of the athletes that appeared in the input.
Time limit: 30 seconds per test set.
Memory limit: 1 GB.
1 ≤ T ≤ 10.
1 ≤ Si ≤ 1000.
Si > Si+1.
1 ≤ Wi ≤ 1000.
Each name consists only of characters A through Z, and is at most 10 characters long.
1 ≤ P ≤ 10.
1 ≤ N ≤ 10.
1 ≤ M ≤ 10.
1 ≤ P ≤ 100.
1 ≤ N ≤ 100.
1 ≤ M ≤ 100.
1 2 1000 500 6 5 BOLT GAY 4 GAY BOLT 1 GAY TIANBING 1 GAY PEIMENG 1 TIANBING LARRY 1 PEIMENG LARRY 2
Case #1: 1: BOLT 2: GAY 3: PEIMENG 3: TIANBING 5: LARRY
Alien tech company G has a very old file transfer tool that is still in use today. While the tool is running, it reassures users by giving status updates on both the percentage of files transferred so far and the number of files transferred so far. The status updates during the process might look like this:
20% |==>-------| 1 files transferred 100% |==========| 5 files transferred
But the percentage isn't precise; it is simply truncated before the decimal point (i.e. floored to the next lowest or equal 1%). That is, both 1.2% and 1.7% would be displayed as 1%.
Some users may want to know the exact total number of files, so you want to modify the tool so that the status updates look like this:
20% |==>-------| 1 out of 5 files transferred 100% |==========| 5 out of 5 files transferred
But you've realized that it may or may not be possible to know the number of files. Given the status updates that the tool displays, either figure out how many files there are, or determine that it can't be done (i.e., there are multiple possible values for the number of files). The status updates are not guaranteed to occur at regular intervals and are not guaranteed to occur whenever a file is transferred.
The first line contains T, the number of test cases. T test cases follow. Each test case consists of one line with an integer N, the number of status updates output by the tool, followed by N lines with the format Pi Ki, where Pi and Ki are integers representing the percentage and number of files transferred at some point in the process. The updates are given listed in chronological order -- that is, both the Pi values and the Ki values are nondecreasing throughout a test case.
For each case, output a line starts with "Case #x: y", where x is the number of the case (starting from 1), and y is either the total number of files, or -1 if that number is ambiguous.
Time limit: 30 seconds per test set.
Memory limit: 1 GB.
1 ≤ T ≤ 50.
1 ≤ N ≤ 100.
0 ≤ Pi ≤ 100
0 ≤ Ki ≤ 2000
The answer is guaranteed not to exceed 2000.
0 ≤ Ki ≤ 1015
The answer is guaranteed not to exceed 1015.
3 2 20 1 100 5 10 25 241 27 262 43 407 44 413 57 536 64 601 67 637 84 789 95 893 96 903 10 0 0 8 2 8 2 17 4 30 7 39 9 69 16 73 17 82 19 91 21
Case #1: 5 Case #2: -1 Case #3: 23
The country of elves is planning to hold an elimination tournament, and there are 2N elves who would like to take part. At the start of the tournament, they will be given unique ID numbers from 1 to 2N, and the Elf President will line them up in some order.
The tournament is a series of matches between two elves, and every match has one winner and one loser (there are no ties). In the first round, the first elf in the line competes against the second elf in the line, the third elf competes against the fourth elf, and so on. After the first round, the 2N-1 elves who lost leave the line, and the 2N-1 elves who won remain where they are. Then, the remaining elves play the second round in the same way: the first remaining elf in the line competes against the second remaining elf in the line, the third remaining elf competes against the fourth remaining elf, and so on. After N rounds, there will be only one elf remaining, and that elf is the winner.
M of the elves are sensitive, which means that they will be very sad if they have to compete in matches against their friends during the games. Specifically, the ith elf will be sad if they have to compete with their friends in the first Ki rounds. (Note that friendship is not necessarily mutual: if one elf considers another elf to be a friend, the other elf does not necessarily consider that elf to be a friend.)
The Elf President wants to know: is there a way to specify the initial positions of all 2N elves to guarantee that no elf will be sad, no matter what happens in the tournament?
The first line of the input gives the number of test cases, T. T test cases follow. Each test case consists of one line with two integers N and M, then M sets of two lines each, in which the first line has integers Ei, Ki, and Bi for one elf, and the second has Bi integer ID numbers of that elf's friends.
For each test case, output one line containing "Case #x: ", where x is the case number (starting from 1), followed by YES or NO.
Time limit: 30 seconds per test set.
Memory limit: 1 GB.
1 ≤ T ≤ 200.
0 ≤ M ≤ 2N.
1 ≤ Ei ≤ 2N.
1 ≤ Ki ≤ N.
M ≤ sum(Bi) ≤ min(2 * M, 2N).
1 ≤ N ≤ 3.
N = 4.
3 1 1 1 1 1 2 2 2 1 1 1 2 3 1 1 4 3 3 1 2 2 3 4 2 2 2 5 6 7 1 1 8
Case #1: NO Case #2: YES Case #3: YES
You have a square N by N matrix M of nonnegative integers. We would like to make a list of the maximum values in every sub-matrix of size K by K within M, and then find the sum of those values together. (Note that the same entry of M might be the maximum value in more than one sub-matrix, in which case it will show up multiple times in the list.) Can you find that sum?
To simplify the input of the matrix, you are given two arrays A and B of length N, and two integers C and X. Then the entry Mij (for the ith row and jth column of the matrix) equals (Ai*i+Bj*j + C) mod X, where i and j are in the range [1, N].
The first line of the input gives the number of test cases, T. T test cases follow. Each test case begins with one line with four integers, N, K, C and X. Then there are two lines with N integers each, representing the arrays A and B.
For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1) and y is the sum of the maximum values in all sub-matrices of size K by K.
Memory limit: 1 GB.
1 ≤ T ≤ 100.
1 ≤ Ai, Bi ≤ 100000.
1 ≤ C ≤ 100000.
1 ≤ X ≤ 1000000007.
1 ≤ K ≤ N.
Time limit: 30 seconds.
1 ≤ N ≤ 50.
Time limit: 90 seconds.
1 ≤ N ≤ 3000.
3 1 1 1 5 1 1 2 1 5 11 1 2 3 4 3 2 3 109 6 4 3 2 1 5
Case #1: 3 Case #2: 19 Case #3: 80
39 31 611 11 2413 13 2614 14 27