辽宁省acm竞赛赛题

Dinner

Description

Little A is one member of ACM team. He had just won the gold in World Final. To celebrate, he decided to invite all to have one meal. As bowl, knife and other tableware is not enough in the kitchen, Little A goes to take backup tableware in warehouse. There are many boxes in warehouse, one box contains only one thing, and each box is marked by the name of things inside it. For example, if \"basketball\" is written on the box, which means the box contains only basketball. With these marks, Little A wants to find out the tableware easily. So, the problem for you is to help him, find out all the tableware from all boxes in the warehouse.

Input

There are many test cases. Each case contains one line, and one integer N at the first, N indicates that there are N boxes in the warehouse. Then N strings follow, each string is one name written on the box.

Output

For each test of the input, output all the name of tableware.

Sample Input

3 basketball fork chopsticks

2 bowl letter

Sample Output

fork chopsticks

bowl

HINT：

The tableware only contains: bowl, knife, fork and chopsticks.

You are my brother

Description

Little A gets to know a new friend, Little B, recently. One day, they realize that they are family 500 years ago. Now, Little A wants to know whether Little B is his elder, younger or brother.

Input

There are multiple test cases.

For each test case, the first line has a single integer, n (n<=1000). The next n lines have two integers a and b (1<=a,b<=2000) each, indicating b is the father of a. One person has exactly one father, of course. Little A is numbered 1 and Little B is numbered 2.

Proceed to the end of file.

Output

For each test case, if Little B is Little A’s younger, print “You are my younger”. Otherwise, if Little B is Little A’s elder, print “You are my elder”. Otherwise, print “You are my brother”. The output for each test case occupied

exactly one line.

Sample Input

5

1 3

2 4

3 5

4 6

5 6

6

1 3

2 4

3 5

4 6

5 7

6 7

Sample Output

You are my elder

You are my brother

Time

Description

Digital clock use 4 digits to express time, each digit is described by 3*3 characters (including”|”,”_”and” “).now given the current time, please tell us how can it be expressed by the digital clock.

Input

There are several test cases.

Each case contains 4 integers in a line, separated by space.

Proceed to the end of file.

Output

For each test case, output the time expressed by the digital clock such as Sample Output.

Sample Input

1 2 5 6

2 3 4 2

Sample Output

_ _ _

| _||_ |_

||_ _||_|

_ _ _

_| _||_| _|

|_ _| ||_

HINT：

The digits showed by the digital clock are as follows:

_ _ _ _ _ _ _ _

| _| _||_||_ |_ ||_||_|| |

||_ _| | _||_| ||_| _||_|

SPY

Description

The National Intelligence Council of X Nation receives a piece of credible information that Nation Y will send spies to steal Nation X’s confidential paper. So the commander of The National Intelligence Council take measures immediately, he will investigate people who will come into Nation X. At the same time, there are two List in the Commander’s hand, one is full of spies that Nation Y will send to Nation X, and the other one is full of spies that Nation X has sent to Nation Y before. There may be some overlaps of the two list. Because the spy may act two roles at the same time, which means that he may be the one that is sent from Nation X to Nation Y, we just call this type a “dual-spy”. So Nation Y may send “dual_spy” back to Nation X, and it is obvious now that it is good for Nation X, because “dual_spy” may bring back Nation Y’s confidential paper without worrying to be detention by Nation Y’s frontier So the commander decides to seize those that are sent by Nation Y, and let the ordinary people and the “dual_spy” in at the same time .So can you decide a list that should be caught by the Commander?

A:the list contains that will come to the Nation X’s frontier.

B:the list contains spies that will be sent by Nation Y.

C:the list contains spies that were sent to Nation Y before.

Input

There are several test cases.

Each test case contains four parts, the first part contains 3 positive integers A, B, C(0The second part contains A strings, the name list of that will come into the frontier.

The second part contains B strings, the name list of that are sent by Nation Y.

The second part contains C strings, the name list of the “dual_spy”.

There will be a blank line after each test case.

There won’t be any repetitive names in a single list, if repetitive names appear in two lists, they mean the same people.

Output

Output the list that the commander should caught (in the appearance order of the lists B).if no one should be caught, then , you should output “No enemy spy”.

Sample Input

8 4 3

Zhao Qian Sun Li Zhou Wu Zheng Wang

Zhao Qian Sun Li

Zhao Zhou Zheng

2 2 2

Zhao Qian

Zhao Qian

Zhao Qian

Sample Output

Qian Sun Li

No enemy spy

Intermediary

Description：

It is widely known that any two strangers can get to know each other through at most six other people. Now let’s prove this.

In the country Intermediary Conducts Personal Communications (ICPC), there are up to n (2<=n<=100) ordinary people conveniently numbered from 0 to n-1. They don’t know each other, or, in other words, they are strangers. The only way they can communicate with each other is through the government, which, in fact, is an intermediary agency. The government consists of up to m (1<=m<=9) employees conveniently numbered from 0 to m-1. Suppose employee z can introduce person x to person y at a cost of d dollars. If this is the first time in a day that employee z introduce one person to another, he will only require d dollars. For the second time, he will require d dollars plus extra e dollars as his tip. For the third time and more, he will require d dollars plus extra f dollars. He is not dared to require any more than that since the strange country is somewhat democratic. And if person x is able to communicate with person t and person t is able to communicate with person y, then person t is always willing to transfer messages from person x to person y, at no charge. Of course, the intermediary fees are all

paid by person x. Notice that employee z being able to introduce person x to person y doesn’t mean he can introduce person y to person x.

Now person 0 has to send a message to person n-1 in one day. If all employees have just started to work, what is the minimum cost for person 0?

Input：

For each test case, the first line contains three integers, n, m and q, where q is the number of intermediary relationships and q is at most 10,000. The second line has m integers, each indicating the value e of every employee, in the range [0, 100]. The third line has m integers too, each indicating the value f of every employee, in the range [e, 200]. The next q lines each contains four integers, x, y, z and d, indicating that employee z can introduce person x to person y requiring d dollars, where 1<=d<=200. There is a blank line after each test case.

Proceed to the end of file.

Output：

For each test case, print one integer on a single line, giving the minimum cost. If it is impossible, print -1.

Sample Input：

3 2 2

1 1

2 2

0 1 0 1

1 2 1 2

5 1 4

1

2

0 1 0 1

1 2 0 1

2 3 0 1

3 4 0 1

Sample Output：

3

9

English Game

Description

This English game is a simple English words connection game.

The rules are as follows: there are N English words in a dictionary, and every word has its own weight v. There is a weight if the corresponding word is used. Now there is a target string X. You have to pick some words in the dictionary, and then connect them to form X. At the same time, the sum weight of the words you picked must be the biggest.

Input

There are several test cases. For each test, N (1<=n<=1000) and X (the length of x is not bigger than 10000) are given at first. Then N rows follow. Each row contains a word wi (the length is not bigger than 30) and the weight of it. Every word is composed of lowercases. No two words in the dictionary are the same.

Output

For each test case, output the biggest sum weight, if you could not form the string X, output -1.

Sample Input

1 aaaa

a 2

3 aaa

a 2

aa 5

aaa 6

4 abc

a 1

bc 2

ab 4

c 1

3 abcd

ab 10

bc 20

cd 30

3 abcd

cd 100

abc 1000

bcd 10000

Sample Output

8

7

5

40

-1

Friends number

Description

Paula and Tai are couple. There are many stories between them. The day Paula left by airplane, Tai send one message to telephone 2200284, then, everything is changing… (The story in “the snow queen”).

After a long time, Tai tells Paula, the number 220 and 284 is a couple of friends number, as they are special, all divisors of 220’s sum is 284, and all divisors of 284’s sum is 220. Can you find out there are how many couples of friends number less than 10,000. Then, how about 100,000, 200,000 and so on.

The task for you is to find out there are how many couples of friends number in given closed interval [a,b].

Input

There are several cases.

Each test case contains two positive integers a, b(1<= a <= b <=5,000,000).

Proceed to the end of file.

Output

For each test case, output the number of couples in the given range. The output of one test case occupied exactly one line.

Sample Input

1 100

1 1000

Sample Output

0

1

HINT：

6 is a number whose sum of all divisors is 6. 6 is not a friend number, these number is called Perfect Number.

Happiness Hotel

Description

The life of Little A is good, and, he managed to get enough money to run a hotel. The best for him is that he need not go to work outside, just wait for the money to go into his pocket. Little A wants everything to be perfect, he has a wonderful plan that he will keep one most beautiful reception whose size is 1(m)(which means the reception is 1 square meter). There are other k rooms that

2have the same area, and the area is x^2(m), x is an integer; Little A wants his hotel

2to be a square. Little A is a good thinker, but not a good maker. As his poor performance on math, he cannot calculate the least area needed to build such a hotel of his will. Now, this task belongs to you, solve this problem to make Little A’s dream of Happy Hotel come true. Please be careful, the whole area should only contain k rooms, and the reception, there should not be any vacant place.

Input

There are several test cases.

Each case contains only one integer k(1<=k<=1000) ,the number of rooms the hotel should have in one line.

Proceed to the end of file.

Output

Output one integer d, means the hotel’s area is d^2(If there is no answer, output “no solution”) .The output of one test case occupied exactly one line.

Sample Input

1

2

3

Sample Output

no solution

3

2

New RDSP Mode

Description

Little A has became fascinated with the game Dota recently, but he is not a good player. In all the modes, the rdsp Mode is popular on online, in this mode, little A always loses games if he gets strange heroes, because, the heroes are distributed randomly.

Little A wants to win the game, so he cracks the code of the rdsp mode with his talent on programming. The following description is about the rdsp mode:

There are N heroes in the game, and they all have a unique number between 1 and N. At the beginning of game, all heroes will be sorted by the number in ascending order. So, all heroes form a sequence One.

These heroes will be operated by the following stages M times:

1.Get out the heroes in odd position of sequence One to form a new sequence Two;

2.Let the remaining heroes in even position to form a new sequence Three;

3.Add the sequence Two to the back of sequence Three to form a new

sequence One.

After M times' operation, the X heroes in the front of new sequence One will be chosen to be Little A's heroes. The problem for you is to tell little A the numbers of his heroes.

Input

There are several test cases.

Each case contains three integers N (1<=N<1,000,000), M

(1<=M<100,000,000), X(1<=X<=20).

Proceed to the end of file.

Output

For each test case, output X integers indicate the number of heroes. There is a space between two numbers. The output of one test case occupied exactly one line.

Sample Input

5 1 2

5 2 2

Sample Output

2 4

4 3

HINT：

In case two: N=5,M=2,X=2,the initial sequence One is 1,2,3,4,5.After the first operation, the sequence One is 2,4,1,3,5. After the second operation, the sequence One is 4,3,2,1,5.So,output 4 3.