1001. A+B Format (20)
Calculate a + b and output the sum in standard format – that is, the digits must be separated into groups of three by commas (unless there are less than four digits).
Input
Each input file contains one test case. Each case contains a pair of integers a and b where 1000000 <= a, b <= 1000000. The numbers are separated by a space.
Output
For each test case, you should output the sum of a and b in one line. The sum must be written in the standard format.
Sample Input
1000000 9
Sample Output
999,991
Program
1  /* 
1 

1002. A+B for Polynomials (25)
This time, you are supposed to find A+B where A and B are two polynomials.
Input
Each input file contains one test case. Each case occupies 2 lines, and each line contains the information of a polynomial: K N1 aN1 N2 aN2 … NK aNK, where K is the number of nonzero terms in the polynomial, Ni and aNi (i=1, 2, …, K) are the exponents and coefficients, respectively. It is given that 1 <= K <= 10，0 <= NK < … < N2 < N1 <=1000.
Output
For each test case you should output the sum of A and B in one line, with the same format as the input. Notice that there must be NO extra space at the end of each line. Please be accurate to 1 decimal place.
Sample Input
2 1 2.4 0 3.2
2 2 1.5 1 0.5
Sample Output
3 2 1.5 1 2.9 0 3.2
Program
1 

1 

1003 Emergency（25）
As an emergency rescue team leader of a city, you are given a special map of your country. The map shows several scattered cities connected by some roads. Amount of rescue teams in each city and the length of each road between any pair of cities are marked on the map. When there is an emergency call to you from some other city, your job is to lead your men to the place as quickly as possible, and at the mean time, call up as many hands on the way as possible.
Input Specification
Each input file contains one test case. For each test case, the first line contains 4 positive integers: N (≤500)  the number of cities (and the cities are numbered from 0 to N−1), M  the number of roads, C1 and C2  the cities that you are currently in and that you must save, respectively. The next line contains N integers, where the ith integer is the number of rescue teams in the ith city. Then M lines follow, each describes a road with three integers c1
, c2 and L, which are the pair of cities connected by a road and the length of that road, respectively. It is guaranteed that there exists at least one path from C1 to C2.
Output Specification
For each test case, print in one line two numbers: the number of different shortest paths between C1 and C2, and the maximum amount of rescue teams you can possibly gather. All the numbers in a line must be separated by exactly one space, and there is no extra space allowed at the end of a line.
Sample Input
5 6 0 2
1 2 1 5 3
0 1 1
0 2 2
0 3 1
1 2 1
2 4 1
3 4 1
Sample Output
2 4
Program
1 

1 

1 

1004 Counting Leaves(30)
Description
A family hierarchy is usually presented by a pedigree tree. Your job is to count those family members who have no child.
Input Specification
Each input file contains one test case. Each case starts with a line containing 0<N<100, the number of nodes in a tree, and M (<N), the number of nonleaf nodes. Then M lines follow, each in the format:ID K ID[1] ID[2] ... ID[K]
where ID is a twodigit number representing a given nonleaf node, K is the number of its children, followed by a sequence of twodigit ID’s of its children. For the sake of simplicity, let us fix the root ID to be 01.
The input ends with N being 0. That case must NOT be processed.
Output Specification
For each test case, you are supposed to count those family members who have no child for every seniority level starting from the root. The numbers must be printed in a line, separated by a space, and there must be no extra space at the end of each line.
The sample case represents a tree with only 2 nodes, where 01 is the root and 02 is its only child. Hence on the root 01 level, there is 0 leaf node; and on the next level, there is 1 leaf node. Then we should output 0 1 in a line.
Sample Input
2 1
01 1 02
Sample Output
0 1
Program
1 

1005 Spell It Right(20)
Description
Given a nonnegative integer N, your task is to compute the sum of all the digits of N, and output every digit of the sum in English.
Input Specification
Each input file contains one test case. Each case occupies one line which contains an N (≤10100).
Output Specification
For each test case, output in one line the digits of the sum in English words. There must be one space between two consecutive words, but no extra space at the end of a line.
Sample Input
12345
Sample Output
one five
Program
1 

1006 Sign In and Sign Out(25)
Description
At the beginning of every day, the first person who signs in the computer room will unlock the door, and the last one who signs out will lock the door. Given the records of signing in’s and out’s, you are supposed to find the ones who have unlocked and locked the door on that day.
Input Specification
Each input file contains one test case. Each case contains the records for one day. The case starts with a positive integer M, which is the total number of records, followed by M lines, each in the format:
ID_number Sign_in_time Sign_out_time
where times are given in the format HH:MM:SS, and ID_number is a string with no more than 15 characters.
Output Specification
For each test case, output in one line the ID numbers of the persons who have unlocked and locked the door on that day. The two ID numbers must be separated by one space.
Note: It is guaranteed that the records are consistent. That is, the sign in time must be earlier than the sign out time for each person, and there are no two persons sign in or out at the same moment.
Sample Input
3
CS301111 15:30:28 17:00:10
SC3021234 08:00:00 11:25:25
CS301133 21:45:00 21:58:40
Sample Output
SC3021234 CS301133
Program
1 

1007 Maximum Subsequence Sum(25)
Description
Given a sequence of K integers { N1, N2, …, NK }. A continuous subsequence is defined to be { Ni, Ni+1, …, Nj } where 1≤i≤j≤K. The Maximum Subsequence is the continuous subsequence which has the largest sum of its elements. For example, given sequence { 2, 11, 4, 13, 5, 2 }, its maximum subsequence is { 11, 4, 13 } with the largest sum being 20.
Now you are supposed to find the largest sum, together with the first and the last numbers of the maximum subsequence.
Input Specification
Each input file contains one test case. Each case occupies two lines. The first line contains a positive integer K (≤10000). The second line contains K numbers, separated by a space.
Output Specification
For each test case, output in one line the largest sum, together with the first and the last numbers of the maximum subsequence. The numbers must be separated by one space, but there must be no extra space at the end of a line. In case that the maximum subsequence is not unique, output the one with the smallest indices i and j (as shown by the sample case). If all the K numbers are negative, then its maximum sum is defined to be 0, and you are supposed to output the first and the last numbers of the whole sequence.
Sample Input
10
10 1 2 3 4 5 23 3 7 21
Sample Output
10 1 4
Program
1 

1008 Elevator(20)
Description
The highest building in our city has only one elevator. A request list is made up with N positive numbers. The numbers denote at which floors the elevator will stop, in specified order. It costs 6 seconds to move the elevator up one floor, and 4 seconds to move down one floor. The elevator will stay for 5 seconds at each stop.
For a given request list, you are to compute the total time spent to fulfill the requests on the list. The elevator is on the 0th floor at the beginning and does not have to return to the ground floor when the requests are fulfilled.
Input Specification
Each input file contains one test case. Each case contains a positive integer N, followed by N positive numbers. All the numbers in the input are less than 100.
Output Specification
For each test case, print the total time on a single line.
Sample Input
3 2 3 1
Sample Output
41
Program
1 

1009 Product of Polynomials
Description
This time, you are supposed to find A×B where A and B are two polynomials.
Input Specification
Each input file contains one test case. Each case occupies 2 lines, and each line contains the information of a polynomial:
$K, N1, a_{N1}, N2, a_{N2} … NK, a_{NK}$, where K is the number of nonzero terms in the polynomial, Ni and aNi(i=1,2,⋯,K) are the exponents and coefficients, respectively. It is given that 1≤K≤10, 0≤NK<⋯<N2<N1≤1000.
Output Specification
For each test case you should output the product of A and B in one line, with the same format as the input. Notice that there must be NO extra space at the end of each line. Please be accurate up to 1 decimal place.
Sample Input
2 1 2.4 0 3.2
2 2 1.5 1 0.5
Sample Output
3 3 3.6 2 6.0 1 1.6
Program
1 

1010 Radix(25)
Description
Given a pair of positive integers, for example, 6 and 110, can this equation 6 = 110 be true? The answer is yes, if 6 is a decimal number and 110 is a binary number.
Now for any pair of positive integers N1 and N2, your task is to find the radix of one number while that of the other is given.
Input Specification
Each input file contains one test case. Each case occupies a line which contains 4 positive integers:
N1 N2 tag radix
Here N1 and N2 each has no more than 10 digits. A digit is less than its radix and is chosen from the set { 09, az } where 09 represent the decimal numbers 09, and az represent the decimal numbers 1035. The last number radix is the radix of N1 if tag is 1, or of N2 if tag is 2.
Output Specification
For each test case, print in one line the radix of the other number so that the equation N1 = N2 is true. If the equation is impossible, print Impossible. If the solution is not unique, output the smallest possible radix.
Sample Input 1
6 110 1 10
Sample Output 1
2
Sample Input 2
1 ab 1 2
Sample Output 2
Impossible
Program
1  /* 
1011 World Cup Betting(20)
Description
With the 2010 FIFA World Cup running, football fans the world over were becoming increasingly excited as the best players from the best teams doing battles for the World Cup trophy in South Africa. Similarly, football betting fans were putting their money where their mouths were, by laying all manner of World Cup bets.
Chinese Football Lottery provided a “Triple Winning” game. The rule of winning was simple: first select any three of the games. Then for each selected game, bet on one of the three possible results – namely W for win, T for tie, and L for lose. There was an odd assigned to each result. The winner’s odd would be the product of the three odds times 65%.
For example, 3 games’ odds are given as the following:
W T L
1.1 2.5 1.7
1.2 3.1 1.6
4.1 1.2 1.1
To obtain the maximum profit, one must buy W for the 3rd game, T for the 2nd game, and T for the 1st game. If each bet takes 2 yuans, then the maximum profit would be (4.1×3.1×2.5×65%−1)×2=39.31 yuans (accurate up to 2 decimal places).
Input Specification
Each input file contains one test case. Each case contains the betting information of 3 games. Each game occupies a line with three distinct odds corresponding to W, T and L.
Output Specification
For each test case, print in one line the best bet of each game, and the maximum profit accurate up to 2 decimal places. The characters and the number must be separated by one space.
Sample Input
1.1 2.5 1.7
1.2 3.1 1.6
4.1 1.2 1.1
Sample Output
T T W 39.31
Program
1 

1012 The Best Rank(25)
Description
To evaluate the performance of our first year CS majored students, we consider their grades of three courses only: C  C Programming Language, M  Mathematics (Calculus or Linear Algrbra), and E  English. At the mean time, we encourage students by emphasizing on their best ranks – that is, among the four ranks with respect to the three courses and the average grade, we print the best rank for each student.
For example, The grades of C, M, E and A  Average of 4 students are given as the following:
StudentID C M E A
310101 98 85 88 90
310102 70 95 88 84
310103 82 87 94 88
310104 91 91 91 91
Then the best ranks for all the students are No.1 since the 1st one has done the best in C Programming Language, while the 2nd one in Mathematics, the 3rd one in English, and the last one in average.
Input Specification
Each input file contains one test case. Each case starts with a line containing 2 numbers N and M (≤2000), which are the total number of students, and the number of students who would check their ranks, respectively. Then N lines follow, each contains a student ID which is a string of 6 digits, followed by the three integer grades (in the range of [0, 100]) of that student in the order of C, M and E. Then there are M lines, each containing a student ID.
Output Specification
For each of the M students, print in one line the best rank for him/her, and the symbol of the corresponding rank, separated by a space.
The priorities of the ranking methods are ordered as A > C > M > E. Hence if there are two or more ways for a student to obtain the same best rank, output the one with the highest priority.
If a student is not on the grading list, simply output N/A.
Sample Input
5 6
310101 98 85 88
310102 70 95 88
310103 82 87 94
310104 91 91 91
310105 85 90 90
310101
310102
310103
310104
310105
999999
Sample Output
1 C
1 M
1 E
1 A
3 A
N/A
Program
1 

1013 Battle Over Cities(25)
Description
It is vitally important to have all the cities connected by highways in a war. If a city is occupied by the enemy, all the highways from/toward that city are closed. We must know immediately if we need to repair any other highways to keep the rest of the cities connected. Given the map of cities which have all the remaining highways marked, you are supposed to tell the number of highways need to be repaired, quickly.
For example, if we have 3 cities and 2 highways connecting city1city2 and city1city3. Then if city1 is occupied by the enemy, we must have 1 highway repaired, that is the highway city2city3.
Input Specification
Each input file contains one test case. Each case starts with a line containing 3 numbers N (<1000), M and K, which are the total number of cities, the number of remaining highways, and the number of cities to be checked, respectively. Then M lines follow, each describes a highway by 2 integers, which are the numbers of the cities the highway connects. The cities are numbered from 1 to N. Finally there is a line containing K numbers, which represent the cities we concern.
Output Specification
For each of the K cities, output in a line the number of highways need to be repaired if that city is lost.
Sample Input
3 2 3
1 2
1 3
1 2 3
Sample Output
1
0
0
Program
1 

1 

1014 Waiting in Line(30)
Description
Suppose a bank has N windows open for service. There is a yellow line in front of the windows which devides the waiting area into two parts. The rules for the customers to wait in line are:
The space inside the yellow line in front of each window is enough to contain a line with M customers. Hence when all the N lines are full, all the customers after (and including) the (NM+1)st one will have to wait in a line behind the yellow line.
Each customer will choose the shortest line to wait in when crossing the yellow line. If there are two or more lines with the same length, the customer will always choose the window with the smallest number.
$Customer_i$ will take $T_i$ minutes to have his/her transaction processed.The first N customers are assumed to be served at 8:00am.
Now given the processing time of each customer, you are supposed to tell the exact time at which a customer has his/her business done.
For example, suppose that a bank has 2 windows and each window may have 2 custmers waiting inside the yellow line. There are 5 customers waiting with transactions taking 1, 2, 6, 4 and 3 minutes, respectively. At 08:00 in the morning, customer1 is served at window1 while customer2 is served at window2. Customer3 will wait in front of window1 and customer4 will wait in front of window2. Customer5 will wait behind the yellow line.
At 08:01, customer1 is done and customer5 enters the line in front of window1 since that line seems shorter now. Customer2 will leave at 08:02, customer4 at 08:06, customer3 at 08:07, and finally customer5 at 08:10.
Input Specification
Each input file contains one test case. Each case starts with a line containing 4 positive integers: N (≤20, number of windows), M (≤10, the maximum capacity of each line inside the yellow line), K (≤1000, number of customers), and Q (≤1000, number of customer queries).
The next line contains K positive integers, which are the processing time of the K customers.
The last line contains Q positive integers, which represent the customers who are asking about the time they can have their transactions done. The customers are numbered from 1 to K.
Output Specification
For each of the Q customers, print in one line the time at which his/her transaction is finished, in the format HH:MM where HH is in [08, 17] and MM is in [00, 59]. Note that since the bank is closed everyday after 17:00, for those customers who cannot be served before 17:00, you must output Sorry instead.
Sample Input
2 2 7 5
1 2 6 4 3 534 2
3 4 5 6 7
Sample Output
08:07
08:06
08:10
17:00
Sorry
Program
1 

1015 Reversible Primes(20)
Description
A reversible prime in any number system is a prime whose “reverse” in that number system is also a prime. For example in the decimal system 73 is a reversible prime because its reverse 37 is also a prime.
Now given any two positive integers N (<$10^{5}$) and D (1<D≤10), you are supposed to tell if N is a reversible prime with radix D.
Input Specification
The input file consists of several test cases. Each case occupies a line which contains two integers N and D. The input is finished by a negative N.
Output Specification
For each test case, print in one line Yes if N is a reversible prime with radix D, or No if not.
Sample Input
73 10
23 2
23 10
2
Sample Output
Yes
Yes
No
Program
1 

1016 Phone Bills(25)
Description
A longdistance telephone company charges its customers by the following rules:
Making a longdistance call costs a certain amount per minute, depending on the time of day when the call is made. When a customer starts connecting a longdistance call, the time will be recorded, and so will be the time when the customer hangs up the phone. Every calendar month, a bill is sent to the customer for each minute called (at a rate determined by the time of day). Your job is to prepare the bills for each month, given a set of phone call records.
Input Specification
Each input file contains one test case. Each case has two parts: the rate structure, and the phone call records.
The rate structure consists of a line with 24 nonnegative integers denoting the toll (cents/minute) from 00:00  01:00, the toll from 01:00  02:00, and so on for each hour in the day.
The next line contains a positive number N (≤1000), followed by N lines of records. Each phone call record consists of the name of the customer (string of up to 20 characters without space), the time and date (mm:dd:hh:mm), and the word online or offline.
For each test case, all dates will be within a single month. Each online record is paired with the chronologically next record for the same customer provided it is an offline record. Any online records that are not paired with an offline record are ignored, as are offline records not paired with an online record. It is guaranteed that at least one call is well paired in the input. You may assume that no two records for the same customer have the same time. Times are recorded using a 24hour clock.
Output Specification
For each test case, you must print a phone bill for each customer.
Bills must be printed in alphabetical order of customers’ names. For each customer, first print in a line the name of the customer and the month of the bill in the format shown by the sample. Then for each time period of a call, print in one line the beginning and ending time and date (dd:hh:mm), the lasting time (in minute) and the charge of the call. The calls must be listed in chronological order. Finally, print the total charge for the month in the format shown by the sample.
Sample Input
1  10 10 10 10 10 10 20 20 20 15 15 15 15 15 15 15 20 30 20 15 15 10 10 10 
Sample Output
1  CYJJ 01 
Program
1 

1017 Queueing at Bank(25)
Description
Suppose a bank has K windows open for service. There is a yellow line in front of the windows which devides the waiting area into two parts. All the customers have to wait in line behind the yellow line, until it is his/her turn to be served and there is a window available. It is assumed that no window can be occupied by a single customer for more than 1 hour.
Now given the arriving time T and the processing time P of each customer, you are supposed to tell the average waiting time of all the customers.
Input Specification
Each input file contains one test case. For each case, the first line contains 2 numbers: N ($≤10^{4}$)  the total number of customers, and K (≤100)  the number of windows. Then N lines follow, each contains 2 times: HH:MM:SS  the arriving time, and P  the processing time in minutes of a customer. Here HH is in the range [00, 23], MM and SS are both in [00, 59]. It is assumed that no two customers arrives at the same time.
Notice that the bank opens from 08:00 to 17:00. Anyone arrives early will have to wait in line till 08:00, and anyone comes too late (at or after 17:00:01) will not be served nor counted into the average.
Output Specification
For each test case, print in one line the average waiting time of all the customers, in minutes and accurate up to 1 decimal place.
Sample Input
7 3
07:55:00 16
17:00:01 2
07:59:59 15
08:01:00 60
08:00:00 30
08:00:02 2
08:03:00 10
Sample Output
8.2
Program
1 

1018 Public Bike Management(30)
Description
There is a public bike service in Hangzhou City which provides great convenience to the tourists from all over the world. One may rent a bike at any station and return it to any other stations in the city.
The Public Bike Management Center (PBMC) keeps monitoring the realtime capacity of all the stations. A station is said to be in perfect condition if it is exactly halffull. If a station is full or empty, PBMC will collect or send bikes to adjust the condition of that station to perfect. And more, all the stations on the way will be adjusted as well.
When a problem station is reported, PBMC will always choose the shortest path to reach that station. If there are more than one shortest path, the one that requires the least number of bikes sent from PBMC will be chosen.
The above figure illustrates an example. The stations are represented by vertices and the roads correspond to the edges. The number on an edge is the time taken to reach one end station from another. The number written inside a vertex $S$ is the current number of bikes stored at $S$. Given that the maximum capacity of each station is 10. To solve the problem at $S_{3}$, we have 2 different shortest paths: PBMC > $S_{1}$ > $S_{3}$. In this case, 4 bikes must be sent from PBMC, because we can collect 1 bike from $S_{1}$ and then take 5 bikes to $S_{3}$, so that both stations will be in perfect conditions.
PBMC > $S_{2}$ > $S_{3}$. This path requires the same time as path 1, but only 3 bikes sent from PBMC and hence is the one that will be chosen.
Input Specification
Each input file contains one test case. For each case, the first line contains 4 numbers: $C_{max}$(≤100), always an even number, is the maximum capacity of each station; $N$ (≤500), the total number of stations; $S_{p}$, the index of the problem station (the stations are numbered from 1 to N, and PBMC is represented by the vertex 0); and $M$, the number of roads. The second line contains $N$ nonnegative numbers $C_{i}$ (i=1,⋯,N) where each $C_{i}$ is the current number of bikes at Si respectively. Then $M$ lines follow, each contains 3 numbers: $S_{i}$, $S_{j}$, and $T_{ij}$ which describe the time $T_{ij}$ taken to move betwen stations $_{i}$ and $S_{j}$. All the numbers in a line are separated by a space.
Output Specification
For each test case, print your results in one line. First output the number of bikes that PBMC must send. Then after one space, output the path in the format: 0−>$S_{1}$ −>⋯−>$S_{p}$. Finally after another space, output the number of bikes that we must take back to PBMC after the condition of $S{p}$ is adjusted to perfect.
Note that if such a path is not unique, output the one that requires minimum number of bikes that we must take back to PBMC. The judge’s data guarantee that such a path is unique.
Sample Input
10 3 3 5
6 7 0
0 1 1
0 2 1
0 3 3
1 3 1
2 3 1
Sample Output
3 0>2>3 0
Program
1  //有个测试点没过，气死我了！ 
1019 General Palindromic Number(20)
Description
A number that will be the same when it is written forwards or backwards is known as a Palindromic Number. For example, 1234321 is a palindromic number. All single digit numbers are palindromic numbers.
Although palindromic numbers are most often considered in the decimal system, the concept of palindromicity can be applied to the natural numbers in any numeral system. Consider a number N>0 in base b≥2, where it is written in standard notation with k+1 digits ai as $\sum_{i=0}^k\left(a_ib^i\right)$. Here, as usual, 0≤ai<b for all i and ak is nonzero. Then N is palindromic if and only if $a_i=a_{k−i}$ for all i. Zero is written 0 in any base and is also palindromic by definition.
Given any positive decimal integer N and a base b, you are supposed to tell if N is a palindromic number in base b.
Input Specification
Each input file contains one test case. Each case consists of two positive numbers N and b, where $0<N≤10^9$is the decimal number and $2≤b≤10^9$is the base. The numbers are separated by a space.
Output Specification
For each test case, first print in one line Yes if N is a palindromic number in base b, or No if not. Then in the next line, print N as the number in base b in the form “$a_k,a_{k−1},…,a_0$”. Notice that there must be no extra space at the end of output.
Sample Input 1
27 2
Sample Output 1
Yes
1 1 0 1 1
Sample Input 2
121 5
Sample Output 2
No
4 4 1
Programs
1 

1020 Tree Traversals(25)
Description
Suppose that all the keys in a binary tree are distinct positive integers. Given the postorder and inorder traversal sequences, you are supposed to output the level order traversal sequence of the corresponding binary tree.
Input Specification
Each input file contains one test case. For each case, the first line gives a positive integer N (≤30), the total number of nodes in the binary tree. The second line gives the postorder sequence and the third line gives the inorder sequence. All the numbers in a line are separated by a space.
Output Specification
For each test case, print in one line the level order traversal sequence of the corresponding binary tree. All the numbers in a line must be separated by exactly one space, and there must be no extra space at the end of the line.
Sample Input
7
2 3 1 5 7 6 4
1 2 3 4 5 6 7
Sample Output
4 1 6 3 5 7 2
Program
1 

1021 Deepest Root(25)
Description
A graph which is connected and acyclic can be considered a tree. The height of the tree depends on the selected root. Now you are supposed to find the root that results in a highest tree. Such a root is called the deepest root.
Input Specification
Each input file contains one test case. For each case, the first line contains a positive integer N ($≤10^{4}$) which is the number of nodes, and hence the nodes are numbered from 1 to N. Then N−1 lines follow, each describes an edge by given the two adjacent nodes’ numbers.
Output Specification
For each test case, print each of the deepest roots in a line. If such a root is not unique, print them in increasing order of their numbers. In case that the given graph is not a tree, print Error: K components where K is the number of connected components in the graph.
Sample Input 1
5
1 2
1 3
1 4
2 5
Sample Output 1
3
4
5
Sample Input 2
5
1 3
1 4
2 5
3 4
Sample Output 2
Error: 2 components
Program
1 

1022 Digital Library(30)
Description
A Digital Library contains millions of books, stored according to their titles, authors, key words of their abstracts, publishers, and published years. Each book is assigned an unique 7digit number as its ID. Given any query from a reader, you are supposed to output the resulting books, sorted in increasing order of their ID’s.
Input Specification
Each input file contains one test case. For each case, the first line contains a positive integer N (≤10^4) which is the total number of books. Then N blocks follow, each contains the information of a book in 6 lines:
Line #1: the 7digit ID number;
Line #2: the book title – a string of no more than 80 characters;
Line #3: the author – a string of no more than 80 characters;
Line #4: the key words – each word is a string of no more than 10 characters without any white space, and the keywords are separated by exactly one space;
Line #5: the publisher – a string of no more than 80 characters;
Line #6: the published year – a 4digit number which is in the range [1000, 3000].
It is assumed that each book belongs to one author only, and contains no more than 5 key words; there are no more than 1000 distinct key words in total; and there are no more than 1000 distinct publishers.
After the book information, there is a line containing a positive integer M (≤1000) which is the number of user’s search queries. Then M lines follow, each in one of the formats shown below:
1: a book title
2: name of an author
3: a key word
4: name of a publisher
5: a 4digit number representing the year
Output Specification
For each query, first print the original query in a line, then output the resulting book ID’s in increasing order, each occupying a line. If no book is found, print Not Found instead.
Sample Input
3
1111111
The Testing Book
Yue Chen
test code debug sort keywords
ZUCS Print
2011
3333333
Another Testing Book
Yue Chen
test code sort keywords
ZUCS Print2
2012
2222222
The Testing Book
CYLL
keywords debug book
ZUCS Print2
2011
6
1: The Testing Book
2: Yue Chen
3: keywords
4: ZUCS Print
5: 2011
3: blablabla
Sample Output
1: The Testing Book
1111111
2222222
2: Yue Chen
1111111
3333333
3: keywords
1111111
2222222
3333333
4: ZUCS Print
1111111
5: 2011
1111111
2222222
3: blablabla
Not Found
Program
1 

1023 Have Fun with Numbers(20)
Description
Notice that the number 123456789 is a 9digit number consisting exactly the numbers from 1 to 9, with no duplication. Double it we will obtain 246913578, which happens to be another 9digit number consisting exactly the numbers from 1 to 9, only in a different permutation. Check to see the result if we double it again!
Now you are suppose to check if there are more numbers with this property. That is, double a given number with k digits, you are to tell if the resulting number consists of only a permutation of the digits in the original number.
Input Specification
Each input contains one test case. Each case contains one positive integer with no more than 20 digits.
Output Specification
For each test case, first print in a line “Yes” if doubling the input number gives a number that consists of only a permutation of the digits in the original number, or “No” if not. Then in the next line, print the doubled number.
Sample Input
1234567899
Sample Output
Yes
2469135798
Program
1 

1024 Palindromic Number(25)
Description
A number that will be the same when it is written forwards or backwards is known as a Palindromic Number. For example, 1234321 is a palindromic number. All single digit numbers are palindromic numbers.
Nonpalindromic numbers can be paired with palindromic ones via a series of operations. First, the nonpalindromic number is reversed and the result is added to the original number. If the result is not a palindromic number, this is repeated until it gives a palindromic number. For example, if we start from 67, we can obtain a palindromic number in 2 steps: 67 + 76 = 143, and 143 + 341 = 484.
Given any positive integer N, you are supposed to find its paired palindromic number and the number of steps taken to find it.
Input Specification
Each input file contains one test case. Each case consists of two positive numbers N and K, where N ($≤10^{10}$) is the initial numer and K (≤100) is the maximum number of steps. The numbers are separated by a space.
Output Specification
For each test case, output two numbers, one in each line. The first number is the paired palindromic number of N, and the second number is the number of steps taken to find the palindromic number. If the palindromic number is not found after K steps, just output the number obtained at the Kth step and K instead.
Sample Input 1
67 3
Sample Output 1
484
2
Sample Input 2
69 3
Sample Output 2
1353
3
Program
1 

1025. PAT Ranking (25)
Programming Ability Test (PAT) is organized by the College of Computer Science and Technology of Zhejiang University. Each test is supposed to run simultaneously in several places, and the ranklists will be merged immediately after the test. Now it is your job to write a program to correctly merge all the ranklists and generate the final rank.
Input Specification
Each input file contains one test case. For each case, the first line contains a positive number N (<=100), the number of test locations. Then N ranklists follow, each starts with a line containing a positive integer K (<=300), the number of testees, and then K lines containing the registration number (a 13digit number) and the total score of each testee. All the numbers in a line are separated by a space.
Output Specification
For each test case, first print in one line the total number of testees. Then print the final ranklist in the following format:
registration_number final_rank location_number local_rank
The locations are numbered from 1 to N. The output must be sorted in nondecreasing order of the final ranks. The testees with the same score must have the same rank, and the output must be sorted in nondecreasing order of their registration numbers.
Sample Input
2
5
1234567890001 95
1234567890005 100
1234567890003 95
1234567890002 77
1234567890004 85
4
1234567890013 65
1234567890011 25
1234567890014 100
1234567890012 85
Sample Output
9
1234567890005 1 1 1
1234567890014 1 2 1
1234567890001 3 1 2
1234567890003 3 1 2
1234567890004 5 1 4
1234567890012 5 2 2
1234567890002 7 1 5
1234567890013 8 2 3
1234567890011 9 2 4
Program
1 

1 

1027 Colors in Mars(20)
Description
People in Mars represent the colors in their computers in a similar way as the Earth people. That is, a color is represented by a 6digit number, where the first 2 digits are for Red, the middle 2 digits for Green, and the last 2 digits for Blue. The only difference is that they use radix 13 (09 and AC) instead of 16. Now given a color in three decimal numbers (each between 0 and 168), you are supposed to output their Mars RGB values.
Input Specification
Each input file contains one test case which occupies a line containing the three decimal color values.
Output Specification
For each test case you should output the Mars RGB value in the following format: first output #, then followed by a 6digit number where all the English characters must be uppercased. If a single color is only 1digit long, you must print a 0 to its left.
Sample Input
15 43 71
Sample Output
#123456
Program
1 

1028 List Sorting(25)
Description
Excel can sort records according to any column. Now you are supposed to imitate this function.
Input Specification
Each input file contains one test case. For each case, the first line contains two integers $N$ $\left(≤10^5\right)$ and $C$, where $N$ is the number of records and $C$ is the column that you are supposed to sort the records with. Then N lines follow, each contains a record of a student. A student’s record consists of his or her distinct ID (a 6digit number), name (a string with no more than 8 characters without space), and grade (an integer between 0 and 100, inclusive).
Output Specification
For each test case, output the sorting result in N lines. That is, if $C$ = 1 then the records must be sorted in increasing order according to ID’s; if $C$ = 2 then the records must be sorted in nondecreasing order according to names; and if $C$ = 3 then the records must be sorted in nondecreasing order according to grades. If there are several students who have the same name or grade, they must be sorted according to their ID’s in increasing order.
Sample Input 1
3 1
000007 James 85
000010 Amy 90
000001 Zoe 60
Sample Output 1
000001 Zoe 60
000007 James 85
000010 Amy 90
Sample Input 2
4 2
000007 James 85
000010 Amy 90
000001 Zoe 60
000002 James 98
Sample Output 2
000010 Amy 90
000002 James 98
000007 James 85
000001 Zoe 60
Sample Input 3
4 3
000007 James 85
000010 Amy 90
000001 Zoe 60
000002 James 90
Sample Output 3
000001 Zoe 60
000007 James 85
000002 James 90
000010 Amy 90
Program
1 

1029 Median(25)
Description
Given an increasing sequence S of N integers, the median is the number at the middle position. For example, the median of S1 = { 11, 12, 13, 14 } is 12, and the median of S2 = { 9, 10, 15, 16, 17 } is 15. The median of two sequences is defined to be the median of the nondecreasing sequence which contains all the elements of both sequences. For example, the median of S1 and S2 is 13.
Given two increasing sequences of integers, you are asked to find their median.
Input Specification
Each input file contains one test case. Each case occupies 2 lines, each gives the information of a sequence. For each sequence, the first positive integer N ($≤2×10^5$) is the size of that sequence. Then N integers follow, separated by a space. It is guaranteed that all the integers are in the range of long int.
Output Specification
For each test case you should output the median of the two given sequences in a line.
Sample Input
4 11 12 13 14
5 9 10 15 16 17
Sample Output
13
Program
1 

1030 Travel Plan (30)
A traveler’s map gives the distances between cities along the highways, together with the cost of each highway. Now you are supposed to write a program to help a traveler to decide the shortest path between his/her starting city and the destination. If such a shortest path is not unique, you are supposed to output the one with the minimum cost, which is guaranteed to be unique.
Input Specification
Each input file contains one test case. Each case starts with a line containing 4 positive integers N, M, S, and D, where N (≤500) is the number of cities (and hence the cities are numbered from 0 to N−1); M is the number of highways; S and D are the starting and the destination cities, respectively. Then M lines follow, each provides the information of a highway, in the format:
City1 City2 Distance Cost
where the numbers are all integers no more than 500, and are separated by a space.
Output Specification
For each test case, print in one line the cities along the shortest path from the starting point to the destination, followed by the total distance and the total cost of the path. The numbers must be separated by a space and there must be no extra space at the end of output.
Sample Input
4 5 0 3
0 1 1 20
1 3 2 30
0 3 4 10
0 2 2 20
2 3 1 20
Sample Output
0 2 3 3 40
Program
1  //Dijkstra+堆 
1  //Dijkstra+DFS 
1031 Hello World for U(20)
Description
Given any string of N (≥5) characters, you are asked to form the characters into the shape of U. For example, helloworld can be printed as:
1  h d 
That is, the characters must be printed in the original order, starting topdown from the left vertical line with n1characters, then left to right along the bottom line with n2 characters, and finally bottomup along the vertical line with n3 characters. And more, we would like U to be as squared as possible – that is, it must be satisfied that $n_1=n_3=max\lbrace k  k\leq 2 for all 3\leq n_2\leq N\rbrace$ with $n_1+n_2+n_3−2=N$.
Input Specification
Each input file contains one test case. Each case contains one string with no less than 5 and no more than 80 characters in a line. The string contains no white space.
Output Specification
For each test case, print the input string in the shape of U as specified in the description.
Sample Input
helloworld!
Sample Output
1  h ! 
Program
1 

1032 Sharing(25)
Description
To store English words, one method is to use linked lists and store a word letter by letter. To save some space, we may let the words share the same sublist if they share the same suffix. For example, loading and being are stored as showed in Figure 1.
You are supposed to find the starting position of the common suffix (e.g. the position of i in Figure 1).
Input Specification
Each input file contains one test case. For each case, the first line contains two addresses of nodes and a positive N (≤10^5), where the two addresses are the addresses of the first nodes of the two words, and N is the total number of nodes. The address of a node is a 5digit positive integer, and NULL is represented by −1.
Then N lines follow, each describes a node in the format:
Address Data Next
whereAddress is the position of the node, Data is the letter contained by this node which is an English letter chosen from { az, AZ }, and Next is the position of the next node.
Output Specification
For each case, simply output the 5digit starting position of the common suffix. If the two words have no common suffix, output 1 instead.
Sample Input 1
11111 22222 9
67890 i 00002
00010 a 12345
00003 g 1
12345 D 67890
00002 n 00003
22222 B 23456
11111 L 00001
23456 e 67890
00001 o 00010
Sample Output 1
67890
Sample Input 2
00001 00002 4
00001 a 10001
10001 s 1
00002 a 10002
10002 t 1
Sample Output 2
1
Program
1  //呵呵，看了下网上答案，和书上标答，第一次找到的相同的就是答案了 
1 

1033 To Fill or Not to Fill(25)
Description
With highways available, driving a car from Hangzhou to any other city is easy. But since the tank capacity of a car is limited, we have to find gas stations on the way from time to time. Different gas station may give different price. You are asked to carefully design the cheapest route to go.
Input Specification
Each input file contains one test case. For each case, the first line contains 4 positive numbers: Cmax(≤ 100), the maximum capacity of the tank; D (≤30000), the distance between Hangzhou and the destination city; Davg(≤20), the average distance per unit gas that the car can run; and N (≤ 500), the total number of gas stations. Then N lines follow, each contains a pair of nonnegative numbers: Pi, the unit gas price, and Di(≤D), the distance between this station and Hangzhou, for i=1,⋯,N. All the numbers in a line are separated by a space.
Output Specification
For each test case, print the cheapest price in a line, accurate up to 2 decimal places. It is assumed that the tank is empty at the beginning. If it is impossible to reach the destination, print The maximum travel distance = X where X is the maximum possible distance the car can run, accurate up to 2 decimal places.
Sample Input 1
50 1300 12 8
6.00 1250
7.00 600
7.00 150
7.10 0
7.20 200
7.50 400
7.30 1000
6.85 300
Sample Output 1
749.17
Sample Input 2
50 1300 12 2
7.10 0
7.00 600
Sample Output 2
The maximum travel distance = 1200.00
Program
1 

1034 Head of a Gang(30)
Description
One way that the police finds the head of a gang is to check people’s phone calls. If there is a phone call between A and B, we say that A and B is related. The weight of a relation is defined to be the total time length of all the phone calls made between the two persons. A “Gang” is a cluster of more than 2 persons who are related to each other with total relation weight being greater than a given threthold K. In each gang, the one with maximum total weight is the head. Now given a list of phone calls, you are supposed to find the gangs and the heads.
Input Specification
Each input file contains one test case. For each case, the first line contains two positive numbers N and K (both less than or equal to 1000), the number of phone calls and the weight threthold, respectively. Then N lines follow, each in the following format:
Name1 Name2 Time
where Name1 and Name2 are the names of people at the two ends of the call, and Time is the length of the call. A name is a string of three capital letters chosen from AZ. A time length is a positive integer which is no more than 1000 minutes.
Output Specification
For each test case, first print in a line the total number of gangs. Then for each gang, print in a line the name of the head and the total number of the members. It is guaranteed that the head is unique for each gang. The output must be sorted according to the alphabetical order of the names of the heads.
Sample Input 1
8 59
AAA BBB 10
BBB AAA 20
AAA CCC 40
DDD EEE 5
EEE DDD 70
FFF GGG 30
GGG HHH 20
HHH FFF 10
Sample Output 1
2
AAA 3
GGG 3
Sample Input 2
8 70
AAA BBB 10
BBB AAA 20
AAA CCC 40
DDD EEE 5
EEE DDD 70
FFF GGG 30
GGG HHH 20
HHH FFF 10
Sample Output 2
0
Program
1  //图DFS！ 
1  //并查集 
1 

1035 Password(20)
Description
To prepare for PAT, the judge sometimes has to generate random passwords for the users. The problem is that there are always some confusing passwords since it is hard to distinguish 1 (one) from l (L in lowercase), or 0 (zero) from O (o in uppercase). One solution is to replace 1 (one) by @, 0 (zero) by %, l by L, and O by o. Now it is your job to write a program to check the accounts generated by the judge, and to help the juge modify the confusing passwords.
Input Specification
Each input file contains one test case. Each case contains a positive integer N (≤1000), followed by N lines of accounts. Each account consists of a user name and a password, both are strings of no more than 10 characters with no space.
Output Specification
For each test case, first print the number M of accounts that have been modified, then print in the following M lines the modified accounts info, that is, the user names and the corresponding modified passwords. The accounts must be printed in the same order as they are read in. If no account is modified, print in one line There are N accounts and no account is modified where N is the total number of accounts. However, if N is one, you must print There is 1 account and no account is modified instead.
Sample Input 1
3
Team000002 Rlsp0dfa
Team000003 perfectpwd
Team000001 R1spOdfa
Sample Output 1
2
Team000002 RLsp%dfa
Team000001 R@spodfa
Sample Input 2
1
team110 abcdefg332
Sample Output 2
There is 1 account and no account is modified
Sample Input 3
2
team110 abcdefg222
team220 abcdefg333
Sample Output 3
There are 2 accounts and no account is modified
Program
1 

1036 Boys vs Girls(25)
Description
This time you are asked to tell the difference between the lowest grade of all the male students and the highest grade of all the female students.
Input Specification
Each input file contains one test case. Each case contains a positive integer N, followed by N lines of student information. Each line contains a student’s name, gender, ID and grade, separated by a space, where name and ID are strings of no more than 10 characters with no space, gender is either F (female) or M (male), and grade is an integer between 0 and 100. It is guaranteed that all the grades are distinct.
Output Specification
For each test case, output in 3 lines. The first line gives the name and ID of the female student with the highest grade, and the second line gives that of the male student with the lowest grade. The third line gives the difference $grade_F$−$grade_M$. If one such kind of student is missing, output Absent
in the corresponding line, and output NA
in the third line instead.
Sample Input 1
3
Joe M Math990112 89
Mike M CS991301 100
Mary F EE990830 95
Sample Output 1
Mary EE990830
Joe Math990112
6
Sample Input 2
1
Jean M AA980920 60
Sample Output 2
Absent
Jean AA980920
NA
Program
1 

1037 Magic Coupon(25)
Description
The magic shop in Mars is offering some magic coupons. Each coupon has an integer N printed on it, meaning that when you use this coupon with a product, you may get N times the value of that product back! What is more, the shop also offers some bonus product for free. However, if you apply a coupon with a positive N to this bonus product, you will have to pay the shop N times the value of the bonus product… but hey, magically, they have some coupons with negative N’s!
For example, given a set of coupons { 1 2 4 −1 }, and a set of product values { 7 6 −2 −3 } (in Mars dollars M$) where a negative value corresponds to a bonus product. You can apply coupon 3 (with N being 4) to product 1 (with value M$7) to get M$28 back; coupon 2 to product 2 to get M$12 back; and coupon 4 to product 4 to get M$3 back. On the other hand, if you apply coupon 3 to product 4, you will have to pay M$12 to the shop.
Each coupon and each product may be selected at most once. Your task is to get as much money back as possible.
Input Specification
Each input file contains one test case. For each case, the first line contains the number of coupons $N_C$, followed by a line with NCcoupon integers. Then the next line contains the number of products NP, followed by a line with NP product values. Here $1≤N_C,N_P≤10^5$, and it is guaranteed that all the numbers will not exceed 230.
Output Specification
For each test case, simply print in a line the maximum amount of money you can get back.
Sample Input
4
1 2 4 1
4
7 6 2 3
Sample Output
43
Program
1 

1038 Recover the Smallest Number(30)
Description
Given a collection of number segments, you are supposed to recover the smallest number from them. For example, given { 32, 321, 3214, 0229, 87 }, we can recover many numbers such like 323213214022987 or 022932873213214 with respect to different orders of combinations of these segments, and the smallest number is 022932132143287.
Input Specification
Each input file contains one test case. Each case gives a positive integer N ($≤10^4$) followed by N number segments. Each segment contains a nonnegative integer of no more than 8 digits. All the numbers in a line are separated by a space.
Output Specification
For each test case, print the smallest number in one line. Notice that the first digit must not be zero.
Sample Input
5 32 321 3214 0229 87
Sample Output
22932132143287
Program
1 

1039 Course List for Student(25)
Description
Zhejiang University has 40000 students and provides 2500 courses. Now given the student name lists of all the courses, you are supposed to output the registered course list for each student who comes for a query.
Input Specification
Each input file contains one test case. For each case, the first line contains 2 positive integers: N (≤40,000), the number of students who look for their course lists, and K (≤2,500), the total number of courses. Then the student name lists are given for the courses (numbered from 1 to K) in the following format: for each course i, first the course index i and the number of registered students Ni(≤200) are given in a line. Then in the next line, Ni student names are given. A student name consists of 3 capital English letters plus a onedigit number. Finally the last line contains the N names of students who come for a query. All the names and numbers in a line are separated by a space.
Output Specification
For each test case, print your results in N lines. Each line corresponds to one student, in the following format: first print the student’s name, then the total number of registered courses of that student, and finally the indices of the courses in increasing order. The query results must be printed in the same order as input. All the data in a line must be separated by a space, with no extra space at the end of the line.
Sample Input
11 5
4 7
BOB5 DON2 FRA8 JAY9 KAT3 LOR6 ZOE1
1 4
ANN0 BOB5 JAY9 LOR6
2 7
ANN0 BOB5 FRA8 JAY9 JOE4 KAT3 LOR6
3 1
BOB5
5 9
AMY7 ANN0 BOB5 DON2 FRA8 JAY9 KAT3 LOR6 ZOE1
ZOE1 ANN0 BOB5 JOE4 JAY9 FRA8 DON2 AMY7 KAT3 LOR6 NON9
Sample Output
ZOE1 2 4 5
ANN0 3 1 2 5
BOB5 5 1 2 3 4 5
JOE4 1 2
JAY9 4 1 2 4 5
FRA8 3 2 4 5
DON2 2 4 5
AMY7 1 5
KAT3 3 2 4 5
LOR6 4 1 2 4 5
NON9 0
Program
1  //最后一个测试点超时了o(╥﹏╥)o 
1 

1040 Longest Symmetric String(25)
Description
Given a string, you are supposed to output the length of the longest symmetric substring. For example, given Is PAT&TAP symmetric?, the longest symmetric substring is s PAT&TAP s, hence you must output 11.
Input Specification
Each input file contains one test case which gives a nonempty string of length no more than 1000.
Output Specification
For each test case, simply print the maximum length in a line.
Sample Input
Is PAT&TAP symmetric?
Sample Output
11
Program
1 

1041 Be Unique(20)
Description
Being unique is so important to people on Mars that even their lottery is designed in a unique way. The rule of winning is simple: one bets on a number chosen from $[1,10^4]$. The first one who bets on a unique number wins. For example, if there are 7 people betting on { 5 31 5 88 67 88 17 }, then the second one who bets on 31 wins.
Input Specification
Each input file contains one test case. Each case contains a line which begins with a positive integer N ($≤10^5$) and then followed by N bets. The numbers are separated by a space.
Output Specification
For each test case, print the winning number in a line. If there is no winner, print None instead.
Sample Input 1
7 5 31 5 88 67 88 17
Sample Output 1
31
Sample Input 2
5 888 666 666 888 888
Sample Output 2
None
Program
1 

1042 Shuffling Machine(20)
Description
Shuffling is a Program used to randomize a deck of playing cards. Because standard shuffling techniques are seen as weak, and in order to avoid “inside jobs” where employees collaborate with gamblers by performing inadequate shuffles, many casinos employ automatic shuffling machines. Your task is to simulate a shuffling machine.
The machine shuffles a deck of 54 cards according to a given random order and repeats for a given number of times. It is assumed that the initial status of a card deck is in the following order:
S1, S2, …, S13,
H1, H2, …, H13,
C1, C2, …, C13,
D1, D2, …, D13,
J1, J2
where “S” stands for “Spade”, “H” for “Heart”, “C” for “Club”, “D” for “Diamond”, and “J” for “Joker”. A given order is a permutation of distinct integers in [1, 54]. If the number at the ith position is j, it means to move the card from position i to position j. For example, suppose we only have 5 cards: S3, H5, C1, D13 and J2. Given a shuffling order {4, 2, 5, 3, 1}, the result will be: J2, H5, D13, S3, C1. If we are to repeat the shuffling again, the result will be: C1, H5, S3, J2, D13.
Input Specification
Each input file contains one test case. For each case, the first line contains a positive integer K (≤20) which is the number of repeat times. Then the next line contains the given order. All the numbers in a line are separated by a space.
Output Specification
For each test case, print the shuffling results in one line. All the cards are separated by a space, and there must be no extra space at the end of the line.
Sample Input
2
36 52 37 38 3 39 40 53 54 41 11 12 13 42 43 44 2 4 23 24 25 26 27 6 7 8 48 49 50 51 9 10 14 15 16 5 17 18 19 1 20 21 22 28 29 30 31 32 33 34 35 45 46 47
Sample Output
S7 C11 C10 C12 S1 H7 H8 H9 D8 D9 S11 S12 S13 D10 D11 D12 S3 S4 S6 S10 H1 H2 C13 D2 D3 D4 H6 H3 D13 J1 J2 C1 C2 C3 C4 D1 S5 H5 H11 H12 C6 C7 C8 C9 S2 S8 S9 H10 D5 D6 D7 H4 H13 C5
Programs
1 

1043 Is It a Binary Search Tree(25)
Description
A Binary Search Tree (BST) is recursively defined as a binary tree which has the following properties:
 The left subtree of a node contains only nodes with keys less than the node’s key.
 The right subtree of a node contains only nodes with keys greater than or equal to the node’s key.
 Both the left and right subtrees must also be binary search trees.
If we swap the left and right subtrees of every node, then the resulting tree is called the Mirror Image of a BST.
Now given a sequence of integer keys, you are supposed to tell if it is the preorder traversal sequence of a BST or the mirror image of a BST.
Input Specification
Each input file contains one test case. For each case, the first line contains a positive integer N (≤1000). Then N integer keys are given in the next line. All the numbers in a line are separated by a space.
Output Specification
For each test case, first print in a line YES if the sequence is the preorder traversal sequence of a BST or the mirror image of a BST, or NO if not. Then if the answer is YES, print in the next line the postorder traversal sequence of that tree. All the numbers in a line must be separated by a space, and there must be no extra space at the end of the line.
Sample Input 1
7
8 6 5 7 10 8 11
Sample Output 1
YES
5 7 6 8 11 10 8
Sample Input 2
7
8 10 11 8 6 7 5
Sample Output 2
YES
11 8 10 7 5 6 8
Sample Input 3
7
8 6 8 5 10 9 11
Sample Output 3
NO
Program
1 

1044 Shopping in Mars(25)
Description
Shopping in Mars is quite a different experience. The Mars people pay by chained diamonds. Each diamond has a value (in Mars dollars M$). When making the payment, the chain can be cut at any position for only once and some of the diamonds are taken off the chain one by one. Once a diamond is off the chain, it cannot be taken back. For example, if we have a chain of 8 diamonds with values M$3, 2, 1, 5, 4, 6, 8, 7, and we must pay M$15. We may have 3 options:
Cut the chain between 4 and 6, and take off the diamonds from the position 1 to 5 (with values 3+2+1+5+4=15).
Cut before 5 or after 6, and take off the diamonds from the position 4 to 6 (with values 5+4+6=15).
Cut before 8, and take off the diamonds from the position 7 to 8 (with values 8+7=15).
Now given the chain of diamond values and the amount that a customer has to pay, you are supposed to list all the paying options for the customer.
If it is impossible to pay the exact amount, you must suggest solutions with minimum lost.
Input Specification
Each input file contains one test case. For each case, the first line contains 2 numbers: N ($≤10^5$), the total number of diamonds on the chain, and M ($≤10^8$), the amount that the customer has to pay. Then the next line contains N positive numbers D1⋯DN(Di≤103 for all i=1,⋯,N) which are the values of the diamonds. All the numbers in a line are separated by a space.
Output Specification
For each test case, print ij in a line for each pair of i ≤ j such that Di + … + Dj = M. Note that if there are more than one solution, all the solutions must be printed in increasing order of i.
If there is no solution, output ij for pairs of i ≤ j such that Di + … + Dj >M with (Di + … + Dj−M) minimized. Again all the solutions must be printed in increasing order of i.
It is guaranteed that the total value of diamonds is sufficient to pay the given amount.
Sample Input 1
16 15
3 2 1 5 4 6 8 7 16 10 15 11 9 12 14 13
Sample Output 1
15
46
78
1111
Sample Input 2
5 13
2 4 5 7 9
Sample Output 2
24
45
Program
1 

1045 Favorite Color Stripe(30)
Description
Eva is trying to make her own color stripe out of a given one. She would like to keep only her favorite colors in her favorite order by cutting off those unwanted pieces and sewing the remaining parts together to form her favorite color stripe.
It is said that a normal human eye can distinguish about less than 200 different colors, so Eva’s favorite colors are limited. However the original stripe could be very long, and Eva would like to have the remaining favorite stripe with the maximum length. So she needs your help to find her the best result.
Note that the solution might not be unique, but you only have to tell her the maximum length. For example, given a stripe of colors {2 2 4 1 5 5 6 3 1 1 5 6}. If Eva’s favorite colors are given in her favorite order as {2 3 1 5 6}, then she has 4 possible best solutions {2 2 1 1 1 5 6}, {2 2 1 5 5 5 6}, {2 2 1 5 5 6 6}, and {2 2 3 1 1 5 6}.
Input Specification
Each input file contains one test case. For each case, the first line contains a positive integer N (≤200) which is the total number of colors involved (and hence the colors are numbered from 1 to N). Then the next line starts with a positive integer M (≤200) followed by M Eva’s favorite color numbers given in her favorite order. Finally the third line starts with a positive integer L ($≤10^{4}$) which is the length of the given stripe, followed by L colors on the stripe. All the numbers in a line a separated by a space.
Output Specification
For each test case, simply print in a line the maximum length of Eva’s favorite stripe.
Sample Input
6
5 2 3 1 5 6
12 2 2 4 1 5 5 6 3 1 1 5 6
Sample Output
7
Program
1 

1046 Shortest Distance(20)
Description
The task is really simple: given N exits on a highway which forms a simple cycle, you are supposed to tell the shortest distance between any pair of exits.
Input Specification
Each input file contains one test case. For each case, the first line contains an integer N (in $[3,10^5]$), followed by N integer distances $D_1 D_2 ⋯ D_N$, where Diis the distance between the ith and the (i+1)st exits, and DN is between the Nth and the 1st exits. All the numbers in a line are separated by a space. The second line gives a positive integer M ($≤10^4$), with M lines follow, each contains a pair of exit numbers, provided that the exits are numbered from 1 to N. It is guaranteed that the total round trip distance is no more than $10^7$.
Output Specification
For each test case, print your results in M lines, each contains the shortest distance between the corresponding given pair of exits.
Sample Input
5 1 2 4 14 9
3
1 3
2 5
4 1
Sample Output
3
10
7
Program
1 

1047 Student List for Course(25)
Description
Zhejiang University has 40,000 students and provides 2,500 courses. Now given the registered course list of each student, you are supposed to output the student name lists of all the courses.
Input Specification
Each input file contains one test case. For each case, the first line contains 2 numbers: N (≤40,000), the total number of students, and K (≤2,500), the total number of courses. Then N lines follow, each contains a student’s name (3 capital English letters plus a onedigit number), a positive number C (≤20) which is the number of courses that this student has registered, and then followed by C course numbers. For the sake of simplicity, the courses are numbered from 1 to K.
Output Specification
For each test case, print the student name lists of all the courses in increasing order of the course numbers. For each course, first print in one line the course number and the number of registered students, separated by a space. Then output the students’ names in alphabetical order. Each name occupies a line.
Sample Input
10 5
ZOE1 2 4 5
ANN0 3 5 2 1
BOB5 5 3 4 2 1 5
JOE4 1 2
JAY9 4 1 2 5 4
FRA8 3 4 2 5
DON2 2 4 5
AMY7 1 5
KAT3 3 5 4 2
LOR6 4 2 4 1 5
Sample Output
1 4
ANN0
BOB5
JAY9
LOR6
2 7
ANN0
BOB5
FRA8
JAY9
JOE4
KAT3
LOR6
3 1
BOB5
4 7
BOB5
DON2
FRA8
JAY9
KAT3
LOR6
ZOE1
5 9
AMY7
ANN0
BOB5
DON2
FRA8
JAY9
KAT3
LOR6
ZOE1
Program
1  //下次遇到超时，直接把输入输出全换成scanf和printf 
1048 Find Coins(25)
Description
Eva loves to collect coins from all over the universe, including some other planets like Mars. One day she visited a universal shopping mall which could accept all kinds of coins as payments. However, there was a special requirement of the payment: for each bill, she could only use exactly two coins to pay the exact amount. Since she has as many as $10^5$ coins with her, she definitely needs your help. You are supposed to tell her, for any given amount of money, whether or not she can find two coins to pay for it.
Input Specification
Each input file contains one test case. For each case, the first line contains 2 positive numbers: N ($≤10^5$, the total number of coins) and M ($≤10^3$, the amount of money Eva has to pay). The second line contains N face values of the coins, which are all positive numbers no more than 500. All the numbers in a line are separated by a space.
Output Specification
For each test case, print in one line the two face values $V_1$ and $V_2$ (separated by a space) such that $V_1+V_2=M$ and $V_1≤V_2$. If such a solution is not unique, output the one with the smallest $V_1$. If there is no solution, output No Solution instead.
Sample Input 1
8 15
1 2 8 7 2 4 11 15
Sample Output 1
4 11
Sample Input 2
7 14
1 8 7 2 4 11 15
Sample Output 2
No Solution
Program
1 

1049 Counting Ones(30)
Description
The task is simple: given any positive integer N, you are supposed to count the total number of 1’s in the decimal form of the integers from 1 to N. For example, given N being 12, there are five 1’s in 1, 10, 11, and 12.
Input Specification
Each input file contains one test case which gives the positive N ($≤2^{30}$).
Output Specification
For each test case, print the number of 1’s in one line.
Sample Input
12
Sample Output
5
Program
1 

1050 String Subtraction(20)
Description
Given two strings $S_1$ and $S_2$, $S=S_−S_2$ is defined to be the remaining string after taking all the characters in $S_2$ from $S_1$. Your task is simply to calculate $S_1−S_2$ for any given strings. However, it might not be that simple to do it fast.
Input Specification
Each input file contains one test case. Each case consists of two lines which gives $S_1$ and $S_2$, respectively. The string lengths of both strings are no more than $10^4$. It is guaranteed that all the characters are visible $ASCII$ codes and white space, and a new line character signals the end of a string.
Output Specification
For each test case, print $S_1−S_2$ in one line.
Sample Input
They are students.
aeiou
Sample Output
Thy r stdnts.
Program
1 

1051 Pop Sequence(25)
Description
Given a stack which can keep M numbers at most. Push N numbers in the order of 1, 2, 3, …, N and pop randomly. You are supposed to tell if a given sequence of numbers is a possible pop sequence of the stack. For example, if M is 5 and N is 7, we can obtain 1, 2, 3, 4, 5, 6, 7 from the stack, but not 3, 2, 1, 7, 5, 6, 4.
Input Specification
Each input file contains one test case. For each case, the first line contains 3 numbers (all no more than 1000): M (the maximum capacity of the stack), N (the length of push sequence), and K (the number of pop sequences to be checked). Then K lines follow, each contains a pop sequence of N numbers. All the numbers in a line are separated by a space.
Output Specification
For each pop sequence, print in one line “YES” if it is indeed a possible pop sequence of the stack, or “NO” if not.
Sample Input
5 7 5
1 2 3 4 5 6 7
3 2 1 7 5 6 4
7 6 5 4 3 2 1
5 6 4 3 7 2 1
1 7 6 5 4 3 2
Sample Output
YES
NO
NO
YES
NO
Program
1 

1052 Linked List Sorting(25)
Description
A linked list consists of a series of structures, which are not necessarily adjacent in memory. We assume that each structure contains an integer key and a Next pointer to the next structure. Now given a linked list, you are supposed to sort the structures according to their key values in increasing order.
Input Specification
Each input file contains one test case. For each case, the first line contains a positive N ($<10^{5}$) and an address of the head node, where N is the total number of nodes in memory and the address of a node is a 5digit positive integer. NULL is represented by −1.
Then N lines follow, each describes a node in the format:Address Key Next
where Address
is the address of the node in memory, Key
is an integer in $[−10^{5},10^{5}]$, and Next
is the address of the next node. It is guaranteed that all the keys are distinct and there is no cycle in the linked list starting from the head node.
Output Specification
For each test case, the output format is the same as that of the input, where N is the total number of nodes in the list and all the nodes must be sorted order.
Sample Input
5 00001
11111 100 1
00001 0 22222
33333 100000 11111
12345 1 33333
22222 1000 12345
Sample Output
5 12345
12345 1 00001
00001 0 11111
11111 100 22222
22222 1000 33333
33333 100000 1
Program
1 

1053 Path of Equal Weight(30)
Description
Given a nonempty tree with root $R$, and with weight $W_{i}$ assigned to each tree node $T_{i}$. The weight of a path from $R$ to $L$ is defined to be the sum of the weights of all the nodes along the path from $R$ to any leaf node $L$.
Now given any weighted tree, you are supposed to find all the paths with their weights equal to a given number. For example, let’s consider the tree showed in the following figure: for each node, the upper number is the node $ID$ which is a twodigit number, and the lower number is the weight of that node. Suppose that the given number is 24, then there exists 4 different paths which have the same given weight: {10 5 2 7}, {10 4 10}, {10 3 3 6 2} and {10 3 3 6 2}, which correspond to the red edges in the figure.
Input Specification
Each input file contains one test case. Each case starts with a line containing $0<N≤100$, the number of nodes in a tree, $M (<N)$, the number of nonleaf nodes, and $0<S<2^{30}$, the given weight number. The next line contains N positive numbers where $W_{i}(<1000)$ corresponds to the tree node $T_{i}$. Then $M$ lines follow, each in the format:ID K ID[1] ID[2] ... ID[K]
where $ID$ is a twodigit number representing a given nonleaf node, $K$ is the number of its children, followed by a sequence of twodigit ID’s of its children. For the sake of simplicity, let us fix the root ID to be 00.
Output Specification
For each test case, print all the paths with weight $S$ in nonincreasing order. Each path occupies a line with printed weights from the root to the leaf in order. All the numbers must be separated by a space with no extra space at the end of the line.
Note: sequence ${A_{1},A_{2},⋯,A_{n}}$ is said to be greater than sequence {B1,B2,⋯,Bm} if there exists $1≤k<min{n,m}$ such that $A_{i}=B_{i} for i=1,⋯,k$, and $Ak+1>Bk+1$.
Sample Input
20 9 24
10 2 4 3 5 10 2 18 9 7 2 2 1 3 12 1 8 6 2 2
00 4 01 02 03 04
02 1 05
04 2 06 07
03 3 11 12 13
06 1 09
07 2 08 10
16 1 15
13 3 14 16 17
17 2 18 19
Sample Output
10 5 2 7
10 4 10
10 3 3 6 2
10 3 3 6 2
Program
1 

1054 The Dominant Color(20)
Description
Behind the scenes in the computer’s memory, color is always talked about as a series of 24 bits of information for each pixel. In an image, the color with the largest proportional area is called the dominant color. A strictly dominant color takes more than half of the total area. Now given an image of resolution M by N (for example, 800×600), you are supposed to point out the strictly dominant color.
Input Specification
Each input file contains one test case. For each case, the first line contains 2 positive numbers: M (≤800) and N (≤600) which are the resolutions of the image. Then N lines follow, each contains M digital colors in the range $[0,2^{24})$. It is guaranteed that the strictly dominant color exists for each input image. All the numbers in a line are separated by a space.
Output Specification
For each test case, simply print the dominant color in a line.
Sample Input
5 3
0 0 255 16777215 24
24 24 0 0 24
24 0 24 24 24
Sample Output
24
Program
1 

1055 The World’s Richest(25)
Description
Forbes magazine publishes every year its list of billionaires based on the annual ranking of the world’s wealthiest people. Now you are supposed to simulate this job, but concentrate only on the people in a certain range of ages. That is, given the net worths of N people, you must find the M richest people in a given range of their ages.
Input Specification
Each input file contains one test case. For each case, the first line contains 2 positive integers: N $(≤10^5)$  the total number of people, and K $(≤10^3)$  the number of queries. Then N lines follow, each contains the name (string of no more than 8 characters without space), age (integer in (0, 200]), and the net worth (integer in $[−10^6,10^6]$) of a person. Finally there are K lines of queries, each contains three positive integers: M (≤100)  the maximum number of outputs, and [Amin, Amax]
which are the range of ages. All the numbers in a line are separated by a space.
Output Specification
For each query, first print in a line Case #X:
where X
is the query number starting from 1. Then output the M richest people with their ages in the range [Amin
, Amax
]. Each person’s information occupies a line, in the formatName Age Net_Worth
The outputs must be in nonincreasing order of the net worths. In case there are equal worths, it must be in nondecreasing order of the ages. If both worths and ages are the same, then the output must be in nondecreasing alphabetical order of the names. It is guaranteed that there is no two persons share all the same of the three pieces of information. In case no one is found, output None.
Sample Input
1  12 4 
Sample Output
1  Case #1: 
Program
1 

1056 Mice and Rice(25)
Description
Mice and Rice is the name of a programming contest in which each programmer must write a piece of code to control the movements of a mouse in a given map. The goal of each mouse is to eat as much rice as possible in order to become a FatMouse.
First the playing order is randomly decided for Np programmers. Then every NG programmers are grouped in a match. The fattest mouse in a group wins and enters the next turn. All the losers in this turn are ranked the same. Every NG winners are then grouped in the next match until a final winner is determined.
For the sake of simplicity, assume that the weight of each mouse is fixed once the programmer submits his/her code. Given the weights of all the mice and the initial playing order, you are supposed to output the ranks for the programmers.
Input Specification
Each input file contains one test case. For each case, the first line contains 2 positive integers: NP and NG (≤1000), the number of programmers and the maximum number of mice in a group, respectively. If there are less than NG mice at the end of the player’s list, then all the mice left will be put into the last group. The second line contains NP distinct nonnegative numbers Wi (i=0,⋯,NP−1) where each Wi
is the weight of the ith mouse respectively. The third line gives the initial playing order which is a permutation of 0,⋯,NP−1(assume that the programmers are numbered from 0 to NP−1). All the numbers in a line are separated by a space.
Output Specification
For each test case, print the final ranks in a line. The ith number is the rank of the ith programmer, and all the numbers must be separated by a space, with no extra space at the end of the line.
Sample Input
11 3
25 18 0 46 37 3 19 22 57 56 10
6 0 8 7 10 5 9 1 4 2 3
Sample Output
5 5 5 2 5 5 5 3 1 3 5
Program
1 

1057 Stack(30)
Description
Stack is one of the most fundamental data structures, which is based on the principle of Last In First Out (LIFO). The basic operations include Push (inserting an element onto the top position) and Pop (deleting the top element). Now you are supposed to implement a stack with an extra operation: PeekMedian – return the median value of all the elements in the stack. With N elements, the median value is defined to be the (N/2)th smallest element if N is even, or ((N+1)/2)th if N is odd.
Input Specification
Each input file contains one test case. For each case, the first line contains a positive integer N ($≤10^{5}$). Then N lines follow, each contains a command in one of the following 3 formats:
Push key
Pop
PeekMedian
where key is a positive integer no more than $10^{5}$.
Output Specification
For each Push command, insert key into the stack and output nothing. For each Pop or PeekMedian command, print in a line the corresponding returned value. If the command is invalid, print Invalid instead.
Sample Input
17
Pop
PeekMedian
Push 3
PeekMedian
Push 2
PeekMedian
Push 1
PeekMedian
Pop
Pop
Push 5
Push 4
PeekMedian
Pop
Pop
Pop
Pop
Sample Output
Invalid
Invalid
3
2
2
1
2
4
4
5
3
Invalid
Program
1 

1 

1058 A+B in Hogwarts(20)
Description
If you are a fan of Harry Potter, you would know the world of magic has its own currency system – as Hagrid explained it to Harry, “Seventeen silver Sickles to a Galleon and twentynine Knuts to a Sickle, it’s easy enough.” Your job is to write a program to compute A+B where A and B are given in the standard form of Galleon.Sickle.Knut (Galleon is an integer in $[0,10^7]$, Sickle is an integer in $[0, 17)$, and Knut is an integer in $[0, 29)$).
Input Specification
Each input file contains one test case which occupies a line with A and B in the standard form, separated by one space.
Output Specification
For each test case you should output the sum of A and B in one line, with the same format as the input.
Sample Input
3.2.1 10.16.27
Sample Output
14.1.28
Program
1 

1059 Prime Factors(25)
Description
Given any positive integer N, you are supposed to find all of its prime factors, and write them in the format $N = p_1^{k\1}×p_2^{k_2}×⋯×p_m^{_km}$.
Input Specification
Each input file contains one test case which gives a positive integer N in the range of long int.
Output Specification
Factor N in the format N = p1^k1*p2^k2*…*pm^km
, where pi’s are prime factors of N in increasing order, and the exponent ki is the number of pi – hence when there is only one pi, ki is 1 and must NOT be printed out.
Sample Input
97532468
Sample Output
97532468=2^2*11*17*101*1291
Program
1 

1060 Are They Equal (25)
Description
If a machine can save only 3 significant digits, the float numbers 12300 and 12358.9 are considered equal since they are both saved as $0.123×10^{5}$ with simple chopping. Now given the number of significant digits on a machine and two float numbers, you are supposed to tell if they are treated equal in that machine.
Input Specification
Each input file contains one test case which gives three numbers N, A and B, where N (<100) is the number of significant digits, and A and B are the two float numbers to be compared. Each float number is nonnegative, no greater than $10^{100}$, and that its total digit number is less than 100.
Output Specification
For each test case, print in a line YES if the two numbers are treated equal, and then the number in the standard form 0.d[1]...d[N]*10^k
(d[1]
>0 unless the number is 0); or NO if they are not treated equal, and then the two numbers in their standard form. All the terms must be separated by a space, with no extra space at the end of a line.
Note: Simple chopping is assumed without rounding.
Sample Input 1
3 12300 12358.9
Sample Output 1YES 0.123*10^5
Sample Input 2
3 120 128
Sample Output 2NO 0.120*10^3 0.128*10^3
Program
1 

1061 Dating(20)
Description
Sherlock Holmes received a note with some strange strings: Let’s date! 3485djDkxh4hhGE 2984akDfkkkkggEdsb s&hgsfdk d&Hyscvnm. It took him only a minute to figure out that those strange strings are actually referring to the coded time Thursday 14:04 – since the first common capital English letter (case sensitive) shared by the first two strings is the 4th capital letter D, representing the 4th day in a week; the second common character is the 5th capital letter E, representing the 14th hour (hence the hours from 0 to 23 in a day are represented by the numbers from 0 to 9 and the capital letters from A to N, respectively); and the English letter shared by the last two strings is s at the 4th position, representing the 4th minute. Now given two pairs of strings, you are supposed to help Sherlock decode the dating time.
Input Specification**
Each input file contains one test case. Each case gives 4 nonempty strings of no more than 60 characters without white space in 4 lines.
**Output Specification
For each test case, print the decoded time in one line, in the format DAY HH:MM, where DAY is a 3character abbreviation for the days in a week – that is, MON for Monday, TUE for Tuesday, WED for Wednesday, THU for Thursday, FRI for Friday, SAT for Saturday, and SUN for Sunday. It is guaranteed that the result is unique for each case.
Sample Input
3485djDkxh4hhGE
2984akDfkkkkggEdsb
s&hgsfdk
d&Hyscvnm
Sample Output
THU 14:04
Program
1 

1062 Talent and Virtue(25)
Description
About 900 years ago, a Chinese philosopher Sima Guang wrote a history book in which he talked about people’s talent and virtue. According to his theory, a man being outstanding in both talent and virtue must be a “sage（圣人）”; being less excellent but with one’s virtue outweighs talent can be called a “nobleman（君子）”; being good in neither is a “fool man（愚人）”; yet a fool man is better than a “small man（小人）” who prefers talent than virtue.
Now given the grades of talent and virtue of a group of people, you are supposed to rank them according to Sima Guang’s theory.
Input Specification
Each input file contains one test case. Each case first gives 3 positive integers in a line: $N (≤10^{5})$, the total number of people to be ranked; $L (≥60)$, the lower bound of the qualified grades – that is, only the ones whose grades of talent and virtue are both not below this line will be ranked; and $H (<100)$, the higher line of qualification – that is, those with both grades not below this line are considered as the “sages”, and will be ranked in nonincreasing order according to their total grades. Those with talent grades below H but virtue grades not are cosidered as the “noblemen”, and are also ranked in nonincreasing order according to their total grades, but they are listed after the “sages”. Those with both grades below H, but with virtue not lower than talent are considered as the “fool men”. They are ranked in the same way but after the “noblemen”. The rest of people whose grades both pass the L line are ranked after the “fool men”.
Then N lines follow, each gives the information of a person in the format:ID_Number Virtue_Grade Talent_Grade
where ID_Number is an 8digit number, and both grades are integers in $[0, 100]$. All the numbers are separated by a space.
Output Specification
The first line of output must give $M (≤N)$, the total number of people that are actually ranked. Then $M$ lines follow, each gives the information of a person in the same format as the input, according to the ranking rules. If there is a tie of the total grade, they must be ranked with respect to their virtue grades in nonincreasing order. If there is still a tie, then output in increasing order of their ID’s.
Sample Input
14 60 80
10000001 64 90
10000002 90 60
10000011 85 80
10000003 85 80
10000004 80 85
10000005 82 77
10000006 83 76
10000007 90 78
10000008 75 79
10000009 59 90
10000010 88 45
10000012 80 100
10000013 90 99
10000014 66 60
Sample Output
12
10000013 90 99
10000012 80 100
10000003 85 80
10000011 85 80
10000004 80 85
10000007 90 78
10000006 83 76
10000005 82 77
10000002 90 60
10000014 66 60
10000008 75 79
10000001 64 90
Program
1 

1063 Set Similarity(25)
Description
Given two sets of integers, the similarity of the sets is defined to be $N_c/N_t×100%$, where Nc is the number of distinct common numbers shared by the two sets, and Nt is the total number of distinct numbers in the two sets. Your job is to calculate the similarity of any given pair of sets.
Input Specification
Each input file contains one test case. Each case first gives a positive integer N (≤50) which is the total number of sets. Then N lines follow, each gives a set with a positive M ($≤10^{4}$) and followed by M integers in the range [0,10^{9}]. After the input of sets, a positive integer K (≤2000) is given, followed by K lines of queries. Each query gives a pair of set numbers (the sets are numbered from 1 to N). All the numbers in a line are separated by a space.
Output Specification
For each query, print in one line the similarity of the sets, in the percentage form accurate up to 1 decimal place.
Sample Input
3
3 99 87 101
4 87 101 5 87
7 99 101 18 5 135 18 99
2
1 2
1 3
Sample Output
50.0%
33.3%
Program
1 

1064 Complete Binary Search Tree(30)
Description
A Binary Search Tree (BST) is recursively defined as a binary tree which has the following properties:
 The left subtree of a node contains only nodes with keys less than the node’s key.
 The right subtree of a node contains only nodes with keys greater than or equal to the node’s key.
 Both the left and right subtrees must also be binary search trees.
A Complete Binary Tree (CBT) is a tree that is completely filled, with the possible exception of the bottom level, which is filled from left to right.
Now given a sequence of distinct nonnegative integer keys, a unique BST can be constructed if it is required that the tree must also be a CBT. You are supposed to output the level order traversal sequence of this BST.
Input Specification
Each input file contains one test case. For each case, the first line contains a positive integer N (≤1000). Then N distinct nonnegative integer keys are given in the next line. All the numbers in a line are separated by a space and are no greater than 2000.
Output Specification
For each test case, print in one line the level order traversal sequence of the corresponding complete binary search tree. All the numbers in a line must be separated by a space, and there must be no extra space at the end of the line.
Sample Input
10
1 2 3 4 5 6 7 8 9 0
Sample Output
6 3 8 1 5 7 9 0 2 4
Program
1  /* 
1065 A+B and C(64bit) (20)
Description
Given three integers A, B and C in $[−2^{63},2^{63})$, you are supposed to tell whether A+B>C.
Input Specification
The first line of the input gives the positive number of test cases, T (≤10). Then T test cases follow, each consists of a single line containing three integers A, B and C, separated by single spaces.
Output Specification
For each test case, output in one line Case #X: true if A+B>C, or Case #X: false otherwise, where X is the case number (starting from 1).
Sample Input
3
1 2 3
2 3 4
9223372036854775807 9223372036854775808 0
Sample Output
Case #1: false
Case #2: true
Case #3: false
Program
1 

1066 Root of AVL Tree(25)
Description
An AVL tree is a selfbalancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. Figures 14 illustrate the rotation rules.
)
)
Now given a sequence of insertions, you are supposed to tell the root of the resulting AVL tree.
Input Specification
Each input file contains one test case. For each case, the first line contains a positive integer N (≤20) which is the total number of keys to be inserted. Then N distinct integer keys are given in the next line. All the numbers in a line are separated by a space.
Output Specification
For each test case, print the root of the resulting AVL tree in one line.
Sample Input 1
5
88 70 61 96 120
Sample Output 1
70
Sample Input 2
7
88 70 61 96 120 90 65
Sample Output 2
88
Program
1 

1067 Sort with Swap(0, i)(25)
Description
Given any permutation of the numbers {0, 1, 2,…, N−1}, it is easy to sort them in increasing order. But what if Swap(0, *) is the ONLY operation that is allowed to use? For example, to sort {4, 0, 2, 1, 3} we may apply the swap operations in the following way:
Swap(0, 1) => {4, 1, 2, 0, 3}
Swap(0, 3) => {4, 1, 2, 3, 0}
Swap(0, 4) => {0, 1, 2, 3, 4}
Now you are asked to find the minimum number of swaps need to sort the given permutation of the first N nonnegative integers.
Input Specification
Each input file contains one test case, which gives a positive N ($≤10^5$) followed by a permutation sequence of {0, 1, …, N−1}. All the numbers in a line are separated by a space.
Output Specification
For each case, simply print in a line the minimum number of swaps need to sort the given permutation.
Sample Inpu
10
3 5 7 2 6 4 9 0 8 1
Sample Output
9
Program
1 

1068 Find More Coins(30)
Description
Eva loves to collect coins from all over the universe, including some other planets like Mars. One day she visited a universal shopping mall which could accept all kinds of coins as payments. However, there was a special requirement of the payment: for each bill, she must pay the exact amount. Since she has as many as $10^{4}$ coins with her, she definitely needs your help. You are supposed to tell her, for any given amount of money, whether or not she can find some coins to pay for it.
Input Specification
Each input file contains one test case. For each case, the first line contains 2 positive numbers: N ($≤10^{4}$), the total number of coins) and M ($≤10^{2}$), the amount of money Eva has to pay). The second line contains N face values of the coins, which are all positive numbers. All the numbers in a line are separated by a space.
Output Specification
For each test case, print in one line the face values $V1≤V2≤⋯≤Vk$ such that$ V1+V2+⋯+Vk=M$. All the numbers must be separated by a space, and there must be no extra space at the end of the line. If such a solution is not unique, output the smallest sequence. If there is no solution, output “No Solution” instead.
Note: sequence ${A[1], A[2], …}$ is said to be “smaller” than sequence ${B[1], B[2], …}$ if there exists k≥1 such that $A[i]=B[i]$ for all $i<k$, and $A[k] < B[k]$.
Sample Input 1
8 9
5 9 8 7 2 3 4 1
Sample Output 1
1 3 5
Sample Input 2
4 8
7 2 4 3
Sample Output 2
No Solution
Program
1 

1069 The Black Hole of Numbers(20)
Description
For any 4digit integer except the ones with all the digits being the same, if we sort the digits in nonincreasing order first, and then in nondecreasing order, a new number can be obtained by taking the second number from the first one. Repeat in this manner we will soon end up at the number 6174 – the black hole of 4digit numbers. This number is named Kaprekar Constant.
For example, start from 6767, we’ll get:
7766  6677 = 1089
9810  0189 = 9621
9621  1269 = 8352
8532  2358 = 6174
7641  1467 = 6174
… …
Given any 4digit number, you are supposed to illustrate the way it gets into the black hole.
Input Specification
Each input file contains one test case which gives a positive integer N in the range $(0,10^4)$.
Output Specification
If all the 4 digits of N are the same, print in one line the equation N  N = 0000. Else print each step of calculation in a line until 6174 comes out as the difference. All the numbers must be printed as 4digit numbers.
Sample Input 1
6767
Sample Output 1
7766  6677 = 1089
9810  0189 = 9621
9621  1269 = 8352
8532  2358 = 6174
Sample Input 2
2222
Sample Output 2
2222  2222 = 0000
Program
1 

1070 Mooncake(25)
Description
Mooncake is a Chinese bakery product traditionally eaten during the MidAutumn Festival. Many types of fillings and crusts can be found in traditional mooncakes according to the region’s culture. Now given the inventory amounts and the prices of all kinds of the mooncakes, together with the maximum total demand of the market, you are supposed to tell the maximum profit that can be made.
Note: partial inventory storage can be taken. The sample shows the following situation: given three kinds of mooncakes with inventory amounts being 180, 150, and 100 thousand tons, and the prices being 7.5, 7.2, and 4.5 billion yuans. If the market demand can be at most 200 thousand tons, the best we can do is to sell 150 thousand tons of the second kind of mooncake, and 50 thousand tons of the third kind. Hence the total profit is 7.2 + 4.5/2 = 9.45 (billion yuans).
Input Specification
Each input file contains one test case. For each case, the first line contains 2 positive integers N (≤1000), the number of different kinds of mooncakes, and D (≤500 thousand tons), the maximum total demand of the market. Then the second line gives the positive inventory amounts (in thousand tons), and the third line gives the positive prices (in billion yuans) of N kinds of mooncakes. All the numbers in a line are separated by a space.
Output Specification
For each test case, print the maximum profit (in billion yuans) in one line, accurate up to 2 decimal places.
Sample Input
3 200
180 150 100
7.5 7.2 4.5
Sample Output
9.45
Program
1 

1071 Speech Patterns(25)
Description
People often have a preference among synonyms of the same word. For example, some may prefer “the police”, while others may prefer “the cops”. Analyzing such patterns can help to narrow down a speaker’s identity, which is useful when validating, for example, whether it’s still the same person behind an online avatar.
Now given a paragraph of text sampled from someone’s speech, can you find the person’s most commonly used word?
Input Specification
Each input file contains one test case. For each case, there is one line of text no more than 1048576 characters in length, terminated by a carriage return \n. The input contains at least one alphanumerical character, i.e., one character from the set [09 AZ az].
Output Specification
For each test case, print in one line the most commonly occurring word in the input text, followed by a space and the number of times it has occurred in the input. If there are more than one such words, print the lexicographically smallest one. The word should be printed in all lower case. Here a “word” is defined as a continuous sequence of alphanumerical characters separated by nonalphanumerical characters or the line beginning/end.
Note that words are case insensitive.
Sample Input
Can1: “Can a can can a can? It can!”
Sample Output
can 5
Program
1 

1072 Gas Station(30)
Description
A gas station has to be built at such a location that the minimum distance between the station and any of the residential housing is as far away as possible. However it must guarantee that all the houses are in its service range.
Now given the map of the city and several candidate locations for the gas station, you are supposed to give the best recommendation. If there are more than one solution, output the one with the smallest average distance to all the houses. If such a solution is still not unique, output the one with the smallest index number.
Input Specification
Each input file contains one test case. For each case, the first line contains 4 positive integers: N $(≤10^{3})$, the total number of houses; M (≤10), the total number of the candidate locations for the gas stations; K $(≤10^{4})$, the number of roads connecting the houses and the gas stations; and $D_{S}$, the maximum service range of the gas station. It is hence assumed that all the houses are numbered from 1 to N, and all the candidate locations are numbered from G1 to GM.
Then K lines follow, each describes a road in the formatP1 P2 Dist
where P1 and P2 are the two ends of a road which can be either house numbers or gas station numbers, and Dist is the integer length of the road.
Output Specification
For each test case, print in the first line the index number of the best location. In the next line, print the minimum and the average distances between the solution and all the houses. The numbers in a line must be separated by a space and be accurate up to 1 decimal place. If the solution does not exist, simply output No Solution.
Sample Input 1
4 3 11 5
1 2 2
1 4 2
1 G1 4
1 G2 3
2 3 2
2 G2 1
3 4 2
3 G3 2
4 G1 3
G2 G1 1
G3 G2 2
Sample Output 1
G1
2.0 3.3(3.2, 事例错了，但是题目OJ判题是对的)
Sample Input 2
2 1 2 10
1 G1 9
2 G1 20
Sample Output 2
No Solution
Program
1  //注意：各个候选站点也是通往对应居住点的路线！ 
1073 Scientific Notation(20)
Description
Scientific notation is the way that scientists easily handle very large numbers or very small numbers. The notation matches the regular expression [+][19].[09]+E[+][09]+ which means that the integer portion has exactly one digit, there is at least one digit in the fractional portion, and the number and its exponent’s signs are always provided even when they are positive.
Now given a real number A in scientific notation, you are supposed to print A in the conventional notation while keeping all the significant figures.
Input Specification
Each input contains one test case. For each case, there is one line containing the real number A in scientific notation. The number is no more than 9999 bytes in length and the exponent’s absolute value is no more than 9999.
Output Specification
For each test case, print in one line the input number A in the conventional notation, with all the significant figures kept, including trailing zeros.
Sample Input 1
+1.23400E03
Sample Output 1
0.00123400
Sample Input 2
1.2E+10
Sample Output 2
12000000000
Program
1 

1074 Reversing Linked List(25)
Description
Given a constant K and a singly linked list L, you are supposed to reverse the links of every K elements on L. For example, given L being 1→2→3→4→5→6, if K=3, then you must output 3→2→1→6→5→4; if K=4, you must output 4→3→2→1→5→6.
Input Specification
Each input file contains one test case. For each case, the first line contains the address of the first node, a positive N ($≤10^5$) which is the total number of nodes, and a positive K (≤N) which is the length of the sublist to be reversed. The address of a node is a 5digit nonnegative integer, and NULL is represented by 1.
Then N lines follow, each describes a node in the format:Address Data Next
where Address
is the position of the node, Data
is an integer, and Next
is the position of the next node.
Output Specification
For each case, output the resulting ordered linked list. Each node occupies a line, and is printed in the same format as in the input.
Sample Input
00100 6 4
00000 4 99999
00100 1 12309
68237 6 1
33218 3 00000
99999 5 68237
12309 2 33218
Sample Output
00000 4 33218
33218 3 12309
12309 2 00100
00100 1 99999
99999 5 68237
68237 6 1
Program
1 

1075 PAT Judge(25)
Description
The ranklist of PAT is generated from the status list, which shows the scores of the submissions. This time you are supposed to generate the ranklist for PAT.
Input Specification
Each input file contains one test case. For each case, the first line contains 3 positive integers, N ($≤10^4$), the total number of users, K (≤5), the total number of problems, and M ($≤10^5$), the total number of submissions. It is then assumed that the user id’s are 5digit numbers from 00001 to N, and the problem id’s are from 1 to K. The next line contains K positive integers p[i] (i=1, …, K), where p[i] corresponds to the full mark of the ith problem. Then M lines follow, each gives the information of a submission in the following format:user_id problem_id partial_score_obtained
where partial_score_obtained is either −1 if the submission cannot even pass the compiler, or is an integer in the range [0, p[problem_id]]. All the numbers in a line are separated by a space.
Output Specification
For each test case, you are supposed to output the ranklist in the following format:
`rank user_id total_score s[1] … s[K]``
where rank is calculated according to the total_score, and all the users with the same total_score obtain the same rank; and s[i] is the partial score obtained for the ith problem. If a user has never submitted a solution for a problem, then ““ must be printed at the corresponding position. If a user has submitted several solutions to solve one problem, then the highest score will be counted.
The ranklist must be printed in nondecreasing order of the ranks. For those who have the same rank, users must be sorted in nonincreasing order according to the number of perfectly solved problems. And if there is still a tie, then they must be printed in increasing order of their id’s. For those who has never submitted any solution that can pass the compiler, or has never submitted any solution, they must NOT be shown on the ranklist. It is guaranteed that at least one user can be shown on the ranklist.
Sample Input
7 4 20
20 25 25 30
00002 2 12
00007 4 17
00005 1 19
00007 2 25
00005 1 20
00002 2 2
00005 1 15
00001 1 18
00004 3 25
00002 2 25
00005 3 22
00006 4 1
00001 2 18
00002 1 20
00004 1 15
00002 4 18
00001 3 4
00001 4 2
00005 2 1
00004 2 0
Sample Output
1 00002 63 20 25  18
2 00005 42 20 0 22 
2 00007 42  25  17
2 00001 42 18 18 4 2
5 00004 40 15 0 25 
Program
1 

1076 Forwards on Weibo(30)
Description
Weibo is known as the Chinese version of Twitter. One user on Weibo may have many followers, and may follow many other users as well. Hence a social network is formed with followers relations. When a user makes a post on Weibo, all his/her followers can view and forward his/her post, which can then be forwarded again by their followers. Now given a social network, you are supposed to calculate the maximum potential amount of forwards for any specific user, assuming that only L levels of indirect followers are counted.
Input Specification
Each input file contains one test case. For each case, the first line contains 2 positive integers: N (≤1000), the number of users; and L (≤6), the number of levels of indirect followers that are counted. Hence it is assumed that all the users are numbered from 1 to N. Then N lines follow, each in the format:
M[i] user_list[i]
where M[i] (≤100) is the total number of people that user[i] follows; and user_list[i] is a list of the M[i] users that followed by user[i]. It is guaranteed that no one can follow oneself. All the numbers are separated by a space.
Then finally a positive K is given, followed by K UserID’s for query.
Output Specification
For each UserID, you are supposed to print in one line the maximum potential amount of forwards this user can trigger, assuming that everyone who can view the initial post will forward it once, and that only L levels of indirect followers are counted.
Sample Input
7 3
3 2 3 4
0
2 5 6
2 3 1
2 3 4
1 4
1 5
2 2 6
Sample Output
4
5
Program
1 

1077 Kuchiguse(20)
Description
The Japanese language is notorious for its sentence ending particles. Personal preference of such particles can be considered as a reflection of the speaker’s personality. Such a preference is called “Kuchiguse” and is often exaggerated artistically in Anime and Manga. For example, the artificial sentence ending particle “nyan~” is often used as a stereotype for characters with a catlike personality:
 Itai nyan~ (It hurts, nyan~)
 Ninjin wa iyada nyan~ (I hate carrots, nyan~)
Now given a few lines spoken by the same character, can you find her Kuchiguse?
Input Specification
Each input file contains one test case. For each case, the first line is an integer N (2≤N≤100). Following are N file lines of 0256 (inclusive) characters in length, each representing a character’s spoken line. The spoken lines are case sensitive.
Output Specification
For each test case, print in one line the kuchiguse of the character, i.e., the longest common suffix of all N lines. If there is no such suffix, write nai.
Sample Input 1
3
Itai nyan
Ninjin wa iyadanyan~
uhhh nyan~
Sample Output 1
nyan~
Sample Input 2
3
Itai!
Ninjinnwaiyada T_T
T_T
Sample Output 2
nai
Program
1 

1078 Hashing(25)
Description
The task of this problem is simple: insert a sequence of distinct positive integers into a hash table, and output the positions of the input numbers. The hash function is defined to be H(key)=key%TSize where TSize is the maximum size of the hash table. Quadratic probing (with positive increments only) is used to solve the collisions.
Note that the table size is better to be prime. If the maximum size given by the user is not prime, you must redefine the table size to be the smallest prime number which is larger than the size given by the user.
Input Specification
Each input file contains one test case. For each case, the first line contains two positive numbers: MSize ($≤10^{4}$) and N (≤MSize) which are the userdefined table size and the number of input numbers, respectively. Then N distinct positive integers are given in the next line. All the numbers in a line are separated by a space.
Output Specification
For each test case, print the corresponding positions (index starts from 0) of the input numbers in one line. All the numbers in a line are separated by a space, and there must be no extra space at the end of the line. In case it is impossible to insert the number, print ““ instead.
Sample Input
4 4
10 6 4 15
Sample Output
0 1 4 
Program
1 

1079 Total Sales of Supply Chain(25)
Description
A supply chain is a network of retailers（零售商）, distributors（经销商）, and suppliers（供应商）– everyone involved in moving a product from supplier to customer.
Starting from one root supplier, everyone on the chain buys products from one’s supplier in a price P and sell or distribute them in a price that is r% higher than P. Only the retailers will face the customers. It is assumed that each member in the supply chain has exactly one supplier except the root supplier, and there is no supply cycle.
Now given a supply chain, you are supposed to tell the total sales from all the retailers.
Input Specification
Each input file contains one test case. For each case, the first line contains three positive numbers: N ($≤10^{5}$), the total number of the members in the supply chain (and hence their ID’s are numbered from 0 to N−1, and the root supplier’s ID is 0); P, the unit price given by the root supplier; and r, the percentage rate of price increment for each distributor or retailer. Then N lines follow, each describes a distributor or retailer in the following format:
`Ki ID[1] ID[2] … ID[Ki]``
where in the ith line, Ki is the total number of distributors or retailers who receive products from supplier i, and is then followed by the ID’s of these distributors or retailers. Kj being 0 means that the jth member is a retailer, then instead the total amount of the product will be given after Kj. All the numbers in a line are separated by a space.
Output Specification
For each test case, print in one line the total sales we can expect from all the retailers, accurate up to 1 decimal place. It is guaranteed that the number will not exceed $10^{10}$.
Sample Input
10 1.80 1.00
3 2 3 5
1 9
1 4
1 7
0 7
2 6 1
1 8
0 9
0 4
0 3
Sample Output
42.4
Program
1 

1080 Graduate Admission(30)
Description
It is said that in 2011, there are about 100 graduate schools ready to proceed over 40,000 applications in Zhejiang Province. It would help a lot if you could write a program to automate the admission Program.
Each applicant will have to provide two grades: the national entrance exam grade $G_E$, and the interview grade $G_I$. The final grade of an applicant is $(G_E+G_I)/2$. The admission rules are:
 The applicants are ranked according to their final grades, and will be admitted one by one from the top of the rank list.
 If there is a tied final grade, the applicants will be ranked according to their national entrance exam grade $G_E$. If still tied, their ranks must be the same.
 Each applicant may have K choices and the admission will be done according to his/her choices: if according to the rank list, it is one’s turn to be admitted; and if the quota of one’s most preferred shcool is not exceeded, then one will be admitted to this school, or one’s other choices will be considered one by one in order. If one gets rejected by all of preferred schools, then this unfortunate applicant will be rejected.
 If there is a tied rank, and if the corresponding applicants are applying to the same school, then that school must admit all the applicants with the same rank, even if its quota will be exceeded.
Input Specification
Each input file contains one test case.
Each case starts with a line containing three positive integers: N (≤40,000), the total number of applicants; M (≤100), the total number of graduate schools; and K (≤5), the number of choices an applicant may have.
In the next line, separated by a space, there are M positive integers. The ith integer is the quota of the ith graduate school respectively.
Then N lines follow, each contains 2+K integers separated by a space. The first 2 integers are the applicant’s $G_E$ and $G_I$
, respectively. The next K integers represent the preferred schools. For the sake of simplicity, we assume that the schools are numbered from 0 to M−1, and the applicants are numbered from 0 to N−1.
Output Specification
For each test case you should output the admission results for all the graduate schools. The results of each school must occupy a line, which contains the applicants’ numbers that school admits. The numbers must be in increasing order and be separated by a space. There must be no extra space at the end of each line. If no applicant is admitted by a school, you must output an empty line correspondingly.
Sample Input
11 6 3
2 1 2 2 2 3
100 100 0 1 2
60 60 2 3 5
100 90 0 3 4
90 100 1 2 0
90 90 5 1 3
80 90 1 0 2
80 80 0 1 2
80 80 0 1 2
80 70 1 3 2
70 80 1 2 3
100 100 0 2 4
Sample Output
1  0 10 
Program
1 

1081 Rational Sum(20)
Description
Given N rational numbers in the form numerator/denominator, you are supposed to calculate their sum.
Input Specification
Each input file contains one test case. Each case starts with a positive integer N (≤100), followed in the next line N rational numbers a1/b1 a2/b2 … where all the numerators and denominators are in the range of long int. If there is a negative number, then the sign must appear in front of the numerator.
Output Specification
For each test case, output the sum in the simplest form integer numerator/denominator where integer is the integer part of the sum, numerator < denominator, and the numerator and the denominator have no common factor. You must output only the fractional part if the integer part is 0.
Sample Input 1
5
2/5 4/15 1/30 2/60 8/3
Sample Output 1
3 1/3
Sample Input 2
2
4/3 2/3
Sample Output 2
2
Sample Input 3
3
1/3 1/6 1/8
Sample Output 3
7/24
Program
1 

1082 Read Number in Chinese(25)
Description
Given an integer with no more than 9 digits, you are supposed to read it in the traditional Chinese way. Output Fu
first if it is negative. For example, 123456789 is read as Fu yi Yi er Qian san Bai si Shi wu Wan liu Qian qi Bai ba Shi jiu
. Note: zero (ling
) must be handled correctly according to the Chinese tradition. For example, 100800 is yi Shi Wan ling ba Bai
.
Input Specification
Each input file contains one test case, which gives an integer with no more than 9 digits.
Output Specification
For each test case, print in a line the Chinese way of reading the number. The characters are separated by a space and there must be no extra space at the end of the line.
Sample Input 1
123456789
Sample Output 1
Fu yi Yi er Qian san Bai si Shi wu Wan liu Qian qi Bai ba Shi jiu
Sample Input 2
100800
Sample Output 2
yi Shi Wan ling ba Bai
Program
1  //注意样例 
1083 List Grades(25)
Description
Given a list of N student records with name, ID and grade. You are supposed to sort the records with respect to the grade in nonincreasing order, and output those student records of which the grades are in a given interval.
Input Specification
Each input file contains one test case. Each case is given in the following format:
N
name[1] ID[1] grade[1]
name[2] ID[2] grade[2]
… …
name[N] ID[N] grade[N]
grade1 grade2
where name[i] and ID[i] are strings of no more than 10 characters with no space, grade[i] is an integer in [0, 100], grade1 and grade2 are the boundaries of the grade’s interval. It is guaranteed that all the grades are distinct.
Output Specification
For each test case you should output the student records of which the grades are in the given interval [grade1, grade2] and are in nonincreasing order. Each student record occupies a line with the student’s name and ID, separated by one space. If there is no student’s grade in that interval, output NONE instead.
Sample Input 1
4
Tom CS000001 59
Joe Math990112 89
Mike CS991301 100
Mary EE990830 95
60 100
Sample Output 1
Mike CS991301
Mary EE990830
Joe Math990112
Sample Input 2
2
Jean AA980920 60
Ann CS01 80
90 95
Sample Output 2
NONE
Program
1 

1084 Broken Keyboard(20)
Description
On a broken keyboard, some of the keys are worn out. So when you type some sentences, the characters corresponding to those keys will not appear on screen.
Now given a string that you are supposed to type, and the string that you actually type out, please list those keys which are for sure worn out.
Input Specification
Each input file contains one test case. For each case, the 1st line contains the original string, and the 2nd line contains the typedout string. Each string contains no more than 80 characters which are either English letters [AZ] (case insensitive), digital numbers [09], or _ (representing the space). It is guaranteed that both strings are nonempty.
Output Specification
For each test case, print in one line the keys that are worn out, in the order of being detected. The English letters must be capitalized. Each worn out key must be printed once only. It is guaranteed that there is at least one worn out key.
Sample Input
1  7_This_is_a_test 
Sample Output
1  7TI 
Program
1 

1085 Perfect Sequence(25)
Description
Given a sequence of positive integers and another positive integer p. The sequence is said to be a perfect sequence if M≤m×p where M and m are the maximum and minimum numbers in the sequence, respectively.
Now given a sequence and a parameter p, you are supposed to find from the sequence as many numbers as possible to form a perfect subsequence.
Input Specification
Each input file contains one test case. For each case, the first line contains two positive integers N and p, where N ($≤10^5$) is the number of integers in the sequence, and p$(\leq 10^9)$ is the parameter. In the second line there are N positive integers, each is no greater than $10^9$.
Output Specification
For each test case, print in one line the maximum number of integers that can be chosen to form a perfect subsequence.
Sample Input
10 8
2 3 20 4 5 1 6 7 8 9
Sample Output
8
Program
1 

1 

1 

1086 Tree Traversals Again(25)
Description
An inorder binary tree traversal can be implemented in a nonrecursive way with a stack. For example, suppose that when a 6node binary tree (with the keys numbered from 1 to 6) is traversed, the stack operations are: push(1); push(2); push(3); pop(); pop(); push(4); pop(); pop(); push(5); push(6); pop(); pop(). Then a unique binary tree (shown in Figure 1) can be generated from this sequence of operations. Your task is to give the postorder traversal sequence of this tree.
Figure 1
Input Specification
Each input file contains one test case. For each case, the first line contains a positive integer N (≤30) which is the total number of nodes in a tree (and hence the nodes are numbered from 1 to N). Then 2N lines follow, each describes a stack operation in the format: “Push X” where X is the index of the node being pushed onto the stack; or “Pop” meaning to pop one node from the stack.
Output Specification
For each test case, print the postorder traversal sequence of the corresponding tree in one line. A solution is guaranteed to exist. All the numbers must be separated by exactly one space, and there must be no extra space at the end of the line.
Sample Input
6
Push 1
Push 2
Push 3
Pop
Pop
Push 4
Pop
Pop
Push 5
Push 6
Pop
Pop
Sample Output
3 4 2 6 5 1
Program
1 

1087 All Roads Lead to Rome(30)
Description
Indeed there are many different tourist routes from our city to Rome. You are supposed to find your clients the route with the least cost while gaining the most happiness.
Input Specification
Each input file contains one test case. For each case, the first line contains 2 positive integers N (2≤N≤200), the number of cities, and K, the total number of routes between pairs of cities; followed by the name of the starting city. The next N−1 lines each gives the name of a city and an integer that represents the happiness one can gain from that city, except the starting city. Then K lines follow, each describes a route between two cities in the format City1 City2 Cost. Here the name of a city is a string of 3 capital English letters, and the destination is always ROM which represents Rome.
Output Specification
For each test case, we are supposed to find the route with the least cost. If such a route is not unique, the one with the maximum happiness will be recommanded. If such a route is still not unique, then we output the one with the maximum average happiness – it is guaranteed by the judge that such a solution exists and is unique.
Hence in the first line of output, you must print 4 numbers: the number of different routes with the least cost, the cost, the happiness, and the average happiness (take the integer part only) of the recommanded route. Then in the next line, you are supposed to print the route in the format City1>City2>...>ROM
.
Sample Input
6 7 HZH
ROM 100
PKN 40
GDN 55
PRS 95
BLN 80
ROM GDN 1
BLN ROM 1
HZH PKN 1
PRS ROM 2
BLN HZH 2
PKN GDN 1
HZH PRS 1
Sample Output
3 3 195 97
HZH>PRS>ROM
Program
1 

1088 Rational Arithmetic(20)
Description
For two rational numbers, your task is to implement the basic arithmetics, that is, to calculate their sum, difference, product and quotient.
Input Specification
Each input file contains one test case, which gives in one line the two rational numbers in the format a1/b1 a2/b2. The numerators and the denominators are all in the range of long int. If there is a negative sign, it must appear only in front of the numerator. The denominators are guaranteed to be nonzero numbers.
Output Specification
For each test case, print in 4 lines the sum, difference, product and quotient of the two rational numbers, respectively. The format of each line is number1 operator number2 = result. Notice that all the rational numbers must be in their simplest form k a/b, where k is the integer part, and a/b is the simplest fraction part. If the number is negative, it must be included in a pair of parentheses. If the denominator in the division is zero, output Inf as the result. It is guaranteed that all the output integers are in the range of long int.
Sample Input 1
2/3 4/2
Sample Output 1
2/3 + (2) = (1 1/3)
2/3  (2) = 2 2/3
2/3 * (2) = (1 1/3)
2/3 / (2) = (1/3)
Sample Input 2
5/3 0/6
Sample Output 2
1 2/3 + 0 = 1 2/3
1 2/3  0 = 1 2/3
1 2/3 * 0 = 0
1 2/3 / 0 = Inf
Program
1 

1089 Insert or Merge(25)
Description
According to Wikipedia:
Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. Each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain.
Merge sort works as follows: Divide the unsorted list into N sublists, each containing 1 element (a list of 1 element is considered sorted). Then repeatedly merge two adjacent sublists to produce new sorted sublists until there is only 1 sublist remaining.
Now given the initial sequence of integers, together with a sequence which is a result of several iterations of some sorting method, can you tell which sorting method we are using?
Input Specification
Each input file contains one test case. For each case, the first line gives a positive integer N (≤100). Then in the next line, N integers are given as the initial sequence. The last line contains the partially sorted sequence of the N numbers. It is assumed that the target sequence is always ascending. All the numbers in a line are separated by a space.
Output Specification
For each test case, print in the first line either “Insertion Sort” or “Merge Sort” to indicate the method used to obtain the partial result. Then run this method for one more iteration and output in the second line the resuling sequence. It is guaranteed that the answer is unique for each test case. All the numbers in a line must be separated by a space, and there must be no extra space at the end of the line.
Sample Input 1
10
3 1 2 8 7 5 9 4 6 0
1 2 3 7 8 5 9 4 6 0
Sample Output 1
Insertion Sort
1 2 3 5 7 8 9 4 6 0
Sample Input 2
10
3 1 2 8 7 5 9 4 0 6
1 3 2 8 5 7 4 9 0 6
Sample Output 2
Merge Sort
1 2 3 8 4 5 7 9 0 6
Program
1 

1090 Highest Price in Supply Chain(25)
Description
A supply chain is a network of retailers（零售商）, distributors（经销商）, and suppliers（供应商）– everyone involved in moving a product from supplier to customer.
Starting from one root supplier, everyone on the chain buys products from one’s supplier in a price P and sell or distribute them in a price that is r% higher than P. It is assumed that each member in the supply chain has exactly one supplier except the root supplier, and there is no supply cycle.
Now given a supply chain, you are supposed to tell the highest price we can expect from some retailers.
Input Specification
Each input file contains one test case. For each case, The first line contains three positive numbers: N ($≤10^5$), the total number of the members in the supply chain (and hence they are numbered from 0 to N−1); P, the price given by the root supplier; and r, the percentage rate of price increment for each distributor or retailer. Then the next line contains N numbers, each number $S_{i}$ is the index of the supplier for the ith member. $S_{root}$ for the root supplier is defined to be −1. All the numbers in a line are separated by a space.
Output Specification
For each test case, print in one line the highest price we can expect from some retailers, accurate up to 2 decimal places, and the number of retailers that sell at the highest price. There must be one space between the two numbers. It is guaranteed that the price will not exceed $10^{10}$.
Sample Input
9 1.80 1.00
1 5 4 4 1 4 5 3 6
Sample Output
1.85 2
Program
1 

1091 Acute Stroke(30)
Description
One important factor to identify acute stroke (急性脑卒中) is the volume of the stroke core. Given the results of image analysis in which the core regions are identified in each MRI slice, your job is to calculate the volume of the stroke core.
Input Specification
Each input file contains one test case. For each case, the first line contains 4 positive integers: M, N, L and T, where M and N are the sizes of each slice (i.e. pixels of a slice are in an M×N matrix, and the maximum resolution is 1286 by 128); L (≤60) is the number of slices of a brain; and T is the integer threshold (i.e. if the volume of a connected core is less than T, then that core must not be counted).
Then L slices are given. Each slice is represented by an M×N matrix of 0’s and 1’s, where 1 represents a pixel of stroke, and 0 means normal. Since the thickness of a slice is a constant, we only have to count the number of 1’s to obtain the volume. However, there might be several separated core regions in a brain, and only those with their volumes no less than T are counted. Two pixels are connected and hence belong to the same region if they share a common side, as shown by Figure 1 where all the 6 red pixels are connected to the blue one.
Figure 1
Output Specification
For each case, output in a line the total volume of the stroke core.
Sample Input
3 4 5 2
1 1 1 1
1 1 1 1
1 1 1 1
0 0 1 1
0 0 1 1
0 0 1 1
1 0 1 1
0 1 0 0
0 0 0 0
1 0 1 1
0 0 0 0
0 0 0 0
0 0 0 1
0 0 0 1
1 0 0 0
Sample Output
26
Program
1 

1092 To Buy or Not to Buy(20)
Description
Eva would like to make a string of beads with her favorite colors so she went to a small shop to buy some beads. There were many colorful strings of beads. However the owner of the shop would only sell the strings in whole pieces. Hence Eva must check whether a string in the shop contains all the beads she needs. She now comes to you for help: if the answer is Yes, please tell her the number of extra beads she has to buy; or if the answer is No, please tell her the number of beads missing from the string.
For the sake of simplicity, let’s use the characters in the ranges [09], [az], and [AZ] to represent the colors. For example, the 3rd string in Figure 1 is the one that Eva would like to make. Then the 1st string is okay since it contains all the necessary beads with 8 extra ones; yet the 2nd one is not since there is no black bead and one less red bead.
1  ppRYYGrrYBR2258 
Figure 1
Input Specification
Each input file contains one test case. Each case gives in two lines the strings of no more than 1000 beads which belong to the shop owner and Eva, respectively.
Output Specification
For each test case, print your answer in one line. If the answer is Yes, then also output the number of extra beads Eva has to buy; or if the answer is No, then also output the number of beads missing from the string. There must be exactly 1 space between the answer and the number.
Sample Input 1
ppRYYGrrYBR2258
YrR8RrY
Sample Output 1
Yes 8
Sample Input 2
ppRYYGrrYB225
YrR8RrY
Sample Output 2
No 2
Program
1 

1093 Count PAT’s(25)
Description
The string APPAPT contains two PAT’s as substrings. The first one is formed by the 2nd, the 4th, and the 6th characters, and the second one is formed by the 3rd, the 4th, and the 6th characters.
Now given any string, you are supposed to tell the number of PAT’s contained in the string.
Input Specification
Each input file contains one test case. For each case, there is only one line giving a string of no more than $10^5$ characters containing only P, A, or T.
Output Specification
For each test case, print in one line the number of PAT’s contained in the string. Since the result may be a huge number, you only have to output the result moded by 1000000007.
Sample Input
APPAPT
Sample Output
2
Program
1 

1094 The Largest Generation(25)
Description
A family hierarchy is usually presented by a pedigree tree where all the nodes on the same level belong to the same generation. Your task is to find the generation with the largest population.
Input Specification
Each input file contains one test case. Each case starts with two positive integers N (<100) which is the total number of family members in the tree (and hence assume that all the members are numbered from 01 to N), and M (<N) which is the number of family members who have children. Then M lines follow, each contains the information of a family member in the following format:ID K ID[1] ID[2] ... ID[K]
where ID is a twodigit number representing a family member, K (>0) is the number of his/her children, followed by a sequence of twodigit ID’s of his/her children. For the sake of simplicity, let us fix the root ID to be 01. All the numbers in a line are separated by a space.
Output Specification
For each test case, print in one line the largest population number and the level of the corresponding generation. It is assumed that such a generation is unique, and the root level is defined to be 1.
Sample Input
23 13
21 1 23
01 4 03 02 04 05
03 3 06 07 08
06 2 12 13
13 1 21
08 2 15 16
02 2 09 10
11 2 19 20
17 1 22
05 1 11
07 1 14
09 1 17
10 1 18
Sample Output
9 4
Program
1 

1095 Cars on Campus(30)
Description
Zhejiang University has 8 campuses and a lot of gates. From each gate we can collect the in/out times and the plate numbers of the cars crossing the gate. Now with all the information available, you are supposed to tell, at any specific time point, the number of cars parking on campus, and at the end of the day find the cars that have parked for the longest time period.
Input Specification
Each input file contains one test case. Each case starts with two positive integers N ($≤10^4$), the number of records, and K ($≤8×10^4$) the number of queries. Then N lines follow, each gives a record in the format:plate_number hh:mm:ss status
where plate_number is a string of 7 English capital letters or 1digit numbers; hh:mm:ss represents the time point in a day by hour:minute:second, with the earliest time being 00:00:00 and the latest 23:59:59; and status is either in or out.
Note that all times will be within a single day. Each in record is paired with the chronologically next record for the same car provided it is an out record. Any in records that are not paired with an out record are ignored, as are out records not paired with an in record. It is guaranteed that at least one car is well paired in the input, and no car is both in and out at the same moment. Times are recorded using a 24hour clock.
Then K lines of queries follow, each gives a time point in the format hh:mm:ss. Note: the queries are given in ascending order of the times.
Output Specification
For each query, output in a line the total number of cars parking on campus. The last line of output is supposed to give the plate number of the car that has parked for the longest time period, and the corresponding time length. If such a car is not unique, then output all of their plate numbers in a line in alphabetical order, separated by a space.
Sample Input
16 7
JH007BD 18:00:01 in
ZD00001 11:30:08 out
DB8888A 13:00:00 out
ZA3Q625 23:59:50 out
ZA133CH 10:23:00 in
ZD00001 04:09:59 in
JH007BD 05:09:59 in
ZA3Q625 11:42:01 out
JH007BD 05:10:33 in
ZA3Q625 06:30:50 in
JH007BD 12:23:42 out
ZA3Q625 23:55:00 in
JH007BD 12:24:23 out
ZA133CH 17:11:22 out
JH007BD 18:07:01 out
DB8888A 06:30:50 in
05:10:00
06:30:50
11:00:00
12:23:42
14:00:00
18:00:00
23:59:00
Sample Output
1
4
5
2
1
0
1
JH007BD ZD00001 07:20:09
Program
1 

1096 Consecutive Factors(20)
Description
Among all the factors of a positive integer N, there may exist several consecutive numbers. For example, 630 can be factored as 3×5×6×7, where 5, 6, and 7 are the three consecutive numbers. Now given any positive N, you are supposed to find the maximum number of consecutive factors, and list the smallest sequence of the consecutive factors.
Input Specification
Each input file contains one test case, which gives the integer N ($1<N<2^{31}$).
Output Specification
For each test case, print in the first line the maximum number of consecutive factors. Then in the second line, print the smallest sequence of the consecutive factors in the format factor[1]*factor[2]*…*factor[k], where the factors are listed in increasing order, and 1 is NOT included.
Sample Input
630
Sample Output
3
567
Program
1  //2*3*4*5*7连续积，而不是只要整除就以为可以，否则变成了2*3*4*5*6*7*8 
1097 Deduplication on a Linked List(25)
Description
Given a singly linked list L with integer keys, you are supposed to remove the nodes with duplicated absolute values of the keys. That is, for each value K, only the first node of which the value or absolute value of its key equals K will be kept. At the mean time, all the removed nodes must be kept in a separate list. For example, given L being 21→15→15→7→15
, you must output 21→15→7
, and the removed list 15→15
.
Input Specification
Each input file contains one test case. For each case, the first line contains the address of the first node, and a positive N ($≤10^{5}$) which is the total number of nodes. The address of a node is a 5digit nonnegative integer, and NULL is represented by −1.
Then N lines follow, each describes a node in the format:
Address Key Next
where Address is the position of the node, Key is an integer of which absolute value is no more than $10^{4}$, and Next is the position of the next node.
Output Specification
For each case, output the resulting linked list first, then the removed list. Each node occupies a line, and is printed in the same format as in the input.
Sample Input
00100 5
99999 7 87654
23854 15 00000
87654 15 1
00000 15 99999
00100 21 23854
Sample Output
00100 21 23854
23854 15 99999
99999 7 1
00000 15 87654
87654 15 1
Program
1 

1098 Insertion or Heap Sort(25)
Description
According to Wikipedia:
Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. Each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain.
Heap sort divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element and moving that to the sorted region. it involves the use of a heap data structure rather than a lineartime search to find the maximum.
Now given the initial sequence of integers, together with a sequence which is a result of several iterations of some sorting method, can you tell which sorting method we are using?
Input Specification
Each input file contains one test case. For each case, the first line gives a positive integer N (≤100). Then in the next line, N integers are given as the initial sequence. The last line contains the partially sorted sequence of the N numbers. It is assumed that the target sequence is always ascending. All the numbers in a line are separated by a space.
Output Specification
For each test case, print in the first line either “Insertion Sort” or “Heap Sort” to indicate the method used to obtain the partial result. Then run this method for one more iteration and output in the second line the resulting sequence. It is guaranteed that the answer is unique for each test case. All the numbers in a line must be separated by a space, and there must be no extra space at the end of the line.
Sample Input 1
10
3 1 2 8 7 5 9 4 6 0
1 2 3 7 8 5 9 4 6 0
Sample Output 1
Insertion Sort
1 2 3 5 7 8 9 4 6 0
Sample Input 2
10
3 1 2 8 7 5 9 4 6 0
6 4 5 1 0 3 2 7 8 9
Sample Output 2
Heap Sort
5 4 3 1 0 2 6 7 8 9
Program
1 

1099 Build A Binary Search Tree(30)
Description
A Binary Search Tree (BST) is recursively defined as a binary tree which has the following properties:
The left subtree of a node contains only nodes with keys less than the node’s key.
The right subtree of a node contains only nodes with keys greater than or equal to the node’s key.
Both the left and right subtrees must also be binary search trees.
Given the structure of a binary tree and a sequence of distinct integer keys, there is only one way to fill these keys into the tree so that the resulting tree satisfies the definition of a BST. You are supposed to output the level order traversal sequence of that tree. The sample is illustrated by Figure 1 and 2.
Input Specification
Each input file contains one test case. For each case, the first line gives a positive integer N (≤100) which is the total number of nodes in the tree. The next N lines each contains the left and the right children of a node in the format left_index right_index, provided that the nodes are numbered from 0 to N−1, and 0 is always the root. If one child is missing, then −1 will represent the NULL child pointer. Finally N distinct integer keys are given in the last line.
Output Specification
For each test case, print in one line the level order traversal sequence of that tree. All the numbers must be separated by a space, with no extra space at the end of the line.
Sample Input
9
1 6
2 3
1 1
1 4
5 1
1 1
7 1
1 8
1 1
73 45 11 58 82 25 67 38 42
Sample Output
58 25 82 11 38 67 45 73 42
Program
1 

1100 Mars Numbers(20)
Description
People on Mars count their numbers with base 13:
Zero on Earth is called “tret” on Mars.
The numbers 1 to 12 on Earth is called “jan, feb, mar, apr, may, jun, jly, aug, sep, oct, nov, dec” on Mars, respectively.
For the next higher digit, Mars people name the 12 numbers as “tam, hel, maa, huh, tou, kes, hei, elo, syy, lok, mer, jou”, respectively.
For examples, the number 29 on Earth is called “hel mar” on Mars; and “elo nov” on Mars corresponds to 115 on Earth. In order to help communication between people from these two planets, you are supposed to write a program for mutual translation between Earth and Mars number systems.
Input Specification
Each input file contains one test case. For each case, the first line contains a positive integer N (<100). Then N lines follow, each contains a number in [0, 169), given either in the form of an Earth number, or that of Mars.
Output Specification
For each number, print in a line the corresponding number in the other language.
Sample Input
4
29
5
elo nov
tam
Sample Output
hel mar
may
115
13
Program
1 

1101 Quick Sort(25)
Description
There is a classical process named partition in the famous quick sort algorithm. In this process we typically choose one element as the pivot. Then the elements less than the pivot are moved to its left and those larger than the pivot to its right. Given N distinct positive integers after a run of partition, could you tell how many elements could be the selected pivot for this partition?
For example, given N=5 and the numbers 1, 3, 2, 4, and 5. We have:
 1 could be the pivot since there is no element to its left and all the elements to its right are larger than it;
 3 must not be the pivot since although all the elements to its left are smaller, the number 2 to its right is less than it as well;
 2 must not be the pivot since although all the elements to its right are larger, the number 3 to its left is larger than it as well;
 and for the similar reason, 4 and 5 could also be the pivot.
Hence in total there are 3 pivot candidates.
Input Specification
Each input file contains one test case. For each case, the first line gives a positive integer N ($≤10^5$). Then the next line contains N distinct positive integers no larger than $10^9$. The numbers in a line are separated by spaces.
Output Specification
For each test case, output in the first line the number of pivot candidates. Then in the next line print these candidates in increasing order. There must be exactly 1 space between two adjacent numbers, and no extra space at the end of each line.
Sample Input
5
1 3 2 4 5
Sample Output
3
1 4 5
Program
1 

1102 Invert a Binary Tree(25)
Description
The following is from Max Howell @twitter:Google: 90% of our engineers use the software you wrote (Homebrew), but you can't invert a binary tree on a whiteboard so fuck off.`` Now it's your turn to prove that YOU CAN invert a binary tree! **Input Specification** Each input file contains one test case. For each case, the first line gives a positive integer N (≤10) which is the total number of nodes in the tree
–and hence the nodes are numbered from 0 to N−1. Then N lines follow, each corresponds to a node from 0 to N−1, and gives the indices of the left and right children of the node. If the child does not exist, a
`` will be put at the position. Any pair of children are separated by a space.
Output Specification
For each test case, print in the first line the levelorder, and then in the second line the inorder traversal sequences of the inverted tree. There must be exactly one space between any adjacent numbers, and no extra space at the end of the line.
Sample Input
1  8 
Sample Output
3 7 2 6 4 0 5 1
6 5 7 4 3 2 0 1
Program
1 

1103 Integer Factorization(30)
Description
The K−P factorization of a positive integer N is to write N as the sum of the Pth power of K positive integers. You are supposed to write a program to find the K−P factorization of N for any positive integers N, K and P.
Input Specification
Each input file contains one test case which gives in a line the three positive integers N (≤400), K (≤N) and P ($1<P≤7$). The numbers in a line are separated by a space.
Output Specification
For each case, if the solution exists, output in the format:N = n[1]^P + ... n[K]^P
where n[i] (i = 1, ..., K)
is the ith factor. All the factors must be printed in nonincreasing order.
Note: the solution may not be unique. For example, the 52 factorization of 169 has 9 solutions, such as 12^2+4^2+2^2+2^2+1^2
, or 11^2+6^2+2^2+2^2+2^2
, or more. You must output the one with the maximum sum of the factors. If there is a tie, the largest factor sequence must be chosen – sequence $\lbrace a_{1},a_{2},⋯,a_{K}\rbrace$ is said to be larger than $\lbrace b_{1},b_{2},⋯,b_{K}\rbrace$if there exists 1≤L≤K such that $a_{i}=b_{i}$ for $i<L$ and $a_{L}>b_{L}$.
If there is no solution, simple output Impossible.
Sample Input 1
169 5 2
Sample Output 1
169 = 6^2 + 6^2 + 6^2 + 6^2 + 5^2
Sample Input 2
169 167 3
Sample Output 2
Impossible
Program
1 

1104 Sum of Number Segments(20)
Description
Given a sequence of positive numbers, a segment is defined to be a consecutive subsequence. For example, given the sequence { 0.1, 0.2, 0.3, 0.4 }, we have 10 segments: (0.1) (0.1, 0.2) (0.1, 0.2, 0.3) (0.1, 0.2, 0.3, 0.4) (0.2) (0.2, 0.3) (0.2, 0.3, 0.4) (0.3) (0.3, 0.4) and (0.4).
Now given a sequence, you are supposed to find the sum of all the numbers in all the segments. For the previous example, the sum of all the 10 segments is 0.1 + 0.3 + 0.6 + 1.0 + 0.2 + 0.5 + 0.9 + 0.3 + 0.7 + 0.4 = 5.0.
Input Specification
Each input file contains one test case. For each case, the first line gives a positive integer N, the size of the sequence which is no more than $10^5$. The next line contains N positive numbers in the sequence, each no more than 1.0, separated by a space.
Output Specification
For each test case, print in one line the sum of all the numbers in all the segments, accurate up to 2 decimal places.
Sample Input
4
0.1 0.2 0.3 0.4
Sample Output
5.00
Program
1 

1105 Spiral Matrix(25)
Description
This time your job is to fill a sequence of N positive integers into a spiral matrix in nonincreasing order. A spiral matrix is filled in from the first element at the upperleft corner, then move in a clockwise spiral. The matrix has m rows and n columns, where m and n satisfy the following: m×n must be equal to N; m≥n; and m−n is the minimum of all the possible values.
Input Specification
Each input file contains one test case. For each case, the first line gives a positive integer N. Then the next line contains N positive integers to be filled into the spiral matrix. All the numbers are no more than $10^{4}$. The numbers in a line are separated by spaces.
Output Specification
For each test case, output the resulting matrix in m lines, each contains n numbers. There must be exactly 1 space between two adjacent numbers, and no extra space at the end of each line.
Sample Input
12
37 76 20 98 76 42 53 95 60 81 58 93
Sample Output
98 95 93
42 37 81
53 20 76
58 60 76
Program
1 

1106 Lowest Price in Supply Chain(25)
Description
A supply chain is a network of retailers（零售商）, distributors（经销商）, and suppliers（供应商）– everyone involved in moving a product from supplier to customer.
Starting from one root supplier, everyone on the chain buys products from one’s supplier in a price P and sell or distribute them in a price that is r% higher than P. Only the retailers will face the customers. It is assumed that each member in the supply chain has exactly one supplier except the root supplier, and there is no supply cycle.
Now given a supply chain, you are supposed to tell the lowest price a customer can expect from some retailers.
Input Specification
Each input file contains one test case. For each case, The first line contains three positive numbers: N ($≤10^{5}$), the total number of the members in the supply chain (and hence their ID’s are numbered from 0 to N−1, and the root supplier’s ID is 0); P, the price given by the root supplier; and r, the percentage rate of price increment for each distributor or retailer. Then N lines follow, each describes a distributor or retailer in the following format:Ki ID[1] ID[2] ... ID[Ki]
where in the ith line, Ki is the total number of distributors or retailers who receive products from supplier i, and is then followed by the ID’s of these distributors or retailers. Kj being 0 means that the jth member is a retailer. All the numbers in a line are separated by a space.
Output Specification
For each test case, print in one line the lowest price we can expect from some retailers, accurate up to 4 decimal places, and the number of retailers that sell at the lowest price. There must be one space between the two numbers. It is guaranteed that the all the prices will not exceed $10^10$.
Sample Input
10 1.80 1.00
3 2 3 5
1 9
1 4
1 7
0
2 6 1
1 8
0
0
0
Sample Output
1.8362 2
Program
1 

1107 Social Clusters(30)
Description
When register on a social network, you are always asked to specify your hobbies in order to find some potential friends with the same hobbies. A social cluster is a set of people who have some of their hobbies in common. You are supposed to find all the clusters.
Input Specification
Each input file contains one test case. For each test case, the first line contains a positive integer N (≤1000), the total number of people in a social network. Hence the people are numbered from 1 to N. Then N lines follow, each gives the hobby list of a person in the format:Ki: hi[1] hi[2] ... hi[Ki]
where Ki(>0) is the number of hobbies, and hi[j] is the index of the jth hobby, which is an integer in [1, 1000].
Output Specification
For each case, print in one line the total number of clusters in the network. Then in the second line, print the numbers of people in the clusters in nonincreasing order. The numbers must be separated by exactly one space, and there must be no extra space at the end of the line.
Sample Input
8
3: 2 7 10
1: 4
2: 5 3
1: 4
1: 3
1: 4
4: 6 8 1 5
1: 4
Sample Output
3
4 3 1
Program
1 
