Problem.docx

2015“赛氪杯”HUST-ACM程序设计竞赛

复赛

A     Permutation Reconstruction

Time Limit: 8000/4000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Description

Consider a permutation a = ⟨a1, a2, . . . an⟩ of numbers from 1 to n. Let us denote as a/i the permutation of n − 1 numbers obtained from a by removing a number i and decreasing all numbers greater than i by one. For example, if a = ⟨1, 3, 5, 2, 6, 4⟩ then a/2 = ⟨1, 2, 4, 5, 3⟩. You are given a/1, a/2, . . . , a/n in some arbitrary order. You must restore the original permutation a.

Input

The first line is one integer T indicates the number of the test cases. (T <=10).

For every case, the first line of contains n — the order of the initial permutation (5 ≤ n ≤ 300). The following n lines contain n − 1 numbers each and specify a/i for all i in some order.

Output

For every test case, output “Case #id:” in a single line, then output n integer numbers — the permutation a. It is guaranteed that such permutation exists.

Sample Input

1

6

1 3 5 2 4

1 3 4 2 5

1 2 4 5 3

2 4 1 5 3

1 4 2 5 3

1 3 2 5 4 

Sample Output

Case #1:

1 3 5 2 6 4

B     Tickets

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Description

The new movie “Furious 7” has just been released! There are 2n people in a line and they want to buy tickets. n of them has 100 ruble bill, another n of them has 50 ruble bill. A ticket costs 50 ruble bill. Now clq is selling the tickets, he has no money initially and he can only sell a ticket to one people at one time. He wants to know how many ways he can sell all the tickets. (Two ways are considered different if there exists a time that clq sells a ticket to different people)

Input

The first line is one integer T indicates the number of the test cases. (T<=1000)

For every case, the first line contains integer 2n, indicates the number of people.(2n<=2000)

Output

For every test case, output “Case #id: ” first, then output the number of ways clq can sell the tickets. Since the answer may be large, output the answer mod 1000000007;

Sample Input

2

2

4

Sample Output

Case #1: 1

Case #2: 8

Hint

In case 2, suppose that 1~2 has 50 ruble bill, 3~4 has 100 ruble bill. There are 8 ways for clq to sell tickets:

1 2 3 4

1 2 4 3

2 1 3 4

2 1 4 3

1 3 2 4

2 3 1 4

1 4 2 3

2 4 1 3

C     Move the books

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Description

Because our new library was built. there are many books to move from the

old one to the new one. Because there are so many books, every book has a weight.

and some of them are so heavy.So the administrator need many volunteers to help him.

When someone move one book, he costs the same energy.The administrator wants to sort

the books from the light to the heavy. Xiaoming is one of volunteers, and he is a lazy people.He

wants to costs the minimum energy. But he can't not find a way. So it's the time to show your

talent.Help him and tell him the minimum energy he must costs.

You can move the book as long as you like.

Input

The first line of input contains only one integer, T, the number of test cases. Following T blocks, each block describe one test case.

Each test case there is one integer n (1 <= n <= 100 )denoting the number of books.

The next line contains n integers a1,a2,...an (1 <= ai <= 10000)denoting the weight of books.

Output

For each test case output one integer denoting the minimum energy Xiaoming must costs.

Sample Input

2

5

2 2 5 3 4

2

1 5

Sample Output

5

0

Hint

In test 1, you can move the books weighted 3 and 4 before 5, which costs 7 energy or you can move

the books weighted 5 to the last, which costs 5 energy.5 is the minimum.

In test 2,the books are already sorted.

D     PHP is the best language in the world

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Description

In a well-known ACM team, most people often use C,C++.However some people also use PHP.

They think PHP is the best language in the world.So they often argue with some people.

And the coach have no ways but to split the whole team into two teams.

The coach wants to split the teams in such ways that everyone should belong to

only one team.Everyone in one team should not argue with other

people in his team. And the coach do not want one team to be very big.

So the size of teams should be as close as possible.And also each team should not be empty.

Input

The first line of input contains only one integer, T, the number of test cases. Following T blocks, each block describe one test case.

Then The first line contains two integer number N (2 ≤ N ≤ 100) - the total number of

persons to divide into teams, M(1 <= M <= 10000) - the number of relationships.

Then followed by M lines.Each line contains two integer i, j which means person i and person j will

not argue with each other.

Output

For each test case, if you can divide it into two teams, output one line denoting the smaller size of one team.

Otherwise output "No solution"

Sample Input

3

3 2

1 2

2 3

3 0

4 5

1 2

1 3

1 4

2 3

Sample Output

1

2

No solution

Hint

In test 1, you can divide person 1 and person 2 into team 1, person 3 to team 2.So answer is 1.

In test 2, you can get that 1, 2, 3 will argue with each other.So there is no way to divide them

into two teams.

In test 3, you can divide person 1,4 into team 1, person 2,3 into team 2.So answer is 2.

E     Tree

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Description

Now we consider a tree rooted at node 1. The distance between adjacent node is 1.

Initially, all of the nodes are inactivated. Each node has a radius Ri, once a node i is activated, all of the nodes with distance no more than Ri will be activated.

Now you are required to set one of the nodes activated to make other nodes activated.The question is, what’s the maximum number of nodes can be activated for a time.

Input

The first line has a number T(T<=10), indicating the number of test cases.

For each test cast, the first line is a number N(1<=N<=50000), the number of nodes in the tree.

The second line comes with N numbers R1, R2, R3 …, RN, describing the radius of node 1 to

node N.(0<=Ri<=50000)

The third line comes with N-1 numbers p2, p3, p4 …, pN, describing the father nodes of node 2 to

node N. Node 1 is the root and will have no father.

Output

Output your answer on a single line for each case.

Sample Input

1

6

0 2 0 1 0 2

1 2 2 4 5

Sample Output

6

Source

Laz

F      The trees of HUST

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Description

As we all know that there are so many trees in HUST, so it is usually called the forest university. They were planted by teachers and students of HUST led by the president Zhu Jiusi.Though the weather of Wuhan in summer is very hot, the temperature of HUST is lower than outside.

One day,Lily were thinking a problem, image that all trees is in a line,the height of trees is different,she want to know that if she ignore some contiguous trees(these trees have to be consecutive) what the numbers is in the longest increasing sequence of consecutive trees.

For example, if the heights of trees were, respectively, 5, 3, 4, 9, 2, 8, 6, 7, 1, then by demolishing trees of heights 9, 2, and 8, the longest increasing sequence of consecutive trees is 3, 4, 6, 7.

Input

The input contains several test cases. The first line of the input contains a positive integer T≤25, denoting the number of test cases. Then T test cases follow, each conforming to the format described below. The input instance consists of two lines. The first one contains one positive integer n≤2*10^5 denoting the number of trees. The second line contains n positive integers not larger than 10^9 separated by single spaces being the heights of the trees.

Output

For each test case print the test case number as “Case #C: H” in one line where C is the test case number, where H is the length of a longest increasing sequence of consecutive trees, achievable by demolishing some consecutive trees or no trees at all.

Sample Input

2

9

5 3 4 9 2 8 6 7 1

7

1 2 3 10 4 5 6

Sample Output

Case #1: 4

Case #2: 6

Source

Wzb

G     String match

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Description

The definition of string match is as descripted below.

There are two strings A and B.If we can find a function F which changes every letter x to F(x) to make string A can be transformed to B, We call A can match B. (Noted that, the letter in every position in string can be changed exactly once.For example, considering the ith position in the string, if we change {A[i] = x} to {A[i] = F(x)}, we can’t change {A[i] = F(x)} to {A[i] = F(F(x))} any more.) Furthermore,if for each x != y, F(x) != F(y),we call it strict match,otherwise,we call it week match.

Input

the first line is a integer T(T<=10)，indicating the number of cases, the next T line are string A and B，for each case，A and B is in the same length less then 100 and consist of lowercase letters.

OutPut

for each test case,print a line,print "not match","strict match","weak match" in the corresponding situation.

Sample Input

4

abb bcc

xyyyyy zzzzzz

zzzzzz xyyyyy

abab xxyy

Sample Output

strict match

weak match

not match

not match

Source

Seven

H     Hardness

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Description

There is a building with m floors. YY has n glass beads of the same hardness,he defines the hardness of the glass bead as follow: if he throws the bead in kth floor, the bead doesn’ t break.But it does break when he throws it in the k+1th floor then the hardness is k,In particular,if it doesn’t break when he throws it in m th floor,the hardness is m,

he wants to measure the hardness of the glass bead,but if a bead is broken, we can't use it again.He wants know the least times he needs to throw even in the worst case

Input

the first line is a integer T(T<=10)，indicating the number of cases, the next T line are m and n (1<=m,n<=500)

OutPut

for each test case,print the answer in a line.

Sample Input

3

10 1

136 2

14 3

Sample Output

10

16

4

Source

Seven

I       ePig

Time Limit: 16000/8000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Description

Andrew and Ann are developing the new P2P software network ePig. The network is intended to be used for sharing files. In this problem you will have to simulate the operation of the network when distributing one large file. Let there be n clients numbered from 1 to n. Initially the whole file is provided by client 1. All other clients wish to get this file. The file is split into k chunks numbered from 1 to k. The transfer consists of a series of rounds. Each round takes one minute and the bandwidth of the connection of each client is enough to transform one chunk to the client and transform one chunk away from the client (simultaneously). After a client gets some chunk it starts to provide it to other clients. Before a round each client decides which chunk it will request. The client will request the chunk that is provided by the smallest number of clients (except those chunks that it already has). If there are several such chunks, it selects the one which has the smaller number. After that the clients make chunk requests. Each client selects the client which has the chunk that it decided to request, if there are several such clients, the client which provides the smallest number of chunks is selected. If there are still several possible variants, the client which has the smallest number is selected. Each client considers all requests and satisfies one of them. The request satisfied by client X is the one which comes from the most valued client. The value of the client is the number of chunks it allowed X to be downloaded from him in the past. If there are several equally valued clients, X gives the chunk to the one which has the smallest number of chunks available. If there are still several possible variants, the chunk is provided to the client which has the smallest number. After the requests that will be satisfied are selected the round begins. The clients whose requests were rejected do not download anything this round, all other clients download the chunk they requested. After that the new round starts. Given n and k, you have to find for each client, what is the number of rounds before it gets the whole file.

Input

There are several test cases. First line is an integer T (T <= 10)indicates the number of test cases.

For each test case, the first line contains n and k (2 ≤ n ≤ 100, 1 ≤ k ≤ 200).

Output

For each case, output n − 1 numbers separated by a blank— for each client except the first one print the number of rounds before it gets the whole file. Each case should occupy exactly one line.

SampleInput

1

3 2

Output

3 3

Hint

The file distribution will proceed as follows. At the first round clients 2 and 3 will request chunk 1 from client 1. Request from client 2 will be satisfied. After that clients 2 and 3 will request chunk 2 from client 1. Client 3 will be satisfied. On the third round client 2 will request chunk 2 from client 3 and client 3 will request chunk 1 from client 2, both requests will be satisfied, and both will have the whole file.

J      Yet another game

Time Limit: 8000/4000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Description

You are playing the following simple game with a friend:

The first player picks a positive integer X.

The second player gives a list of k distinct positive integers Y1,…,Yk such that (Y1+1)(Y2+1)⋯(Yk+1)=X, and gets k points.

Write a program that plays the second player.

Input

There are several test cases. First line is an integer T (T <= 100)indicates the number of test cases.

Each case consists of a single integer X satisfying 10^3≤X≤10^15, giving the number picked by the first player.

Output

Write a single integer k, giving the number of points obtained by the second player, assuming she plays as good as possible.

Sample Input

1

1099511627776

Sample Output

8

K     Sequence

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Description

you have a sequence X of length n,and each element is zero in the begin. you can play 2 operation on the sequence：

1.    give you 4 integer l,r,x,y（0<=l<=r<n） At first,generate another sequence A that satisfy A[0]=x.A[1]=y,A[i]=A[i-1]+A[i-2],then you should add A[i] to X[l+i] for 0<=i<=r-l;

2.    give you 2 integer l,r ,ask the result of X[l]+X[l+1]+…+X[r]

Input

There are several test cases. First line is an integer T (T <= 5)indicates the number of test cases.

For each test case,the first is two integer n,m,means the length of the sequence and the number of operations,the following m line are operations, the first number t is the type of the operation, the other numbers are described above.

1<=n,m,x,y<=1000000

Output

For each second type operation ,output the ans in a line, because it is too large, you just need output the ans mod 1000000007

Sample Input

1

5 4

10 4 1 1

2 0 4

1 1 3 2 5

2 1 4

Sample Output

12

25

Hint

After the first operation ,X is 1,1,2,3,5, so the sum is 12.

Ather the third operaton X is 1,3,7,10,5,so X[1]+X[2]+X[3]+X[4]=25

Source

Seven