当前位置:首页 >> >> ACM简单练习题

ACM简单练习题


Description

在第二次世界大战中,一个飞行员由于飞机没油了被强迫降落,飞机降落的地点是固定在坐标系中的(0,0)点。
但是敌人在地面上修筑了一些多边形的包围区。如果飞行员降落在包围区外,他就是安全的。
当飞行员降落在包围区内,那么他必须要知道一种密码口令,才能通过包围区。飞行员不可能降落在多边形的边上。
这种密码是给出两个不同的质数p,q;密码就是不能用px+qy形式表示的正整数的个数,其中x,y大于等于0的整数。
比如p=3,q=5,则有四个正正整数1,2,4,7不能用其表示,因此密码口令为4。

Input

输入有多组测试数据,每组数据的第一行是一个数n
(3<=n<=16),表示包围区的顶点的个数。
当n=0时表示输入结束。接下来有n行,每行有两个实数
用来表示顶点的坐标,顶点时按照顺时针或逆时针来给出的
。再接下来的一行是p q。


Output

首先输出测试数据的编号,
第二行输出飞行员是否在包围区内,
如果在包围区内第三行输出密码口令。


Sample Input

4
-1.0 -1.0
2.0 -1.0
2.0 2.0
-1.0 2.0
3 5
5
-2.5 -2.5
10.5 -2.5
10.5 -1.5
-1.5 -1.5
-2.5 20.5
2 7
0


Sample Output

Pilot 1
The pilot is in danger!
The secret number is 4.

Pilot 2
The pilot is safe.


Description

A the softmind's mind,a valid date format should be formed by the forms below:

MM-DD-YYYY
DD-MMM-YYYY
MM/DD/YYYY
YYYY/MM/DD
YYYY/MMM/DD

that the "DD"、"MM" and "YYYY" is three integers ,indicate day、month and year of a date. The "MMM" indicate the month in another way , the string of "MMM" only can be one of {"Jan","Feb","Mar","Apr","May","June","July","Aug","Sept","Oct","Nov","Dec"}.

Of course a day should be no more than 31 , a month should be no more than 12 ,a year should be greater than 1000 ,and another condition you should be consided.

One day ,softmind is very depressed, so he thought that the various of date format let he in confusion, so he need a uniform date format , so the problem comes ,please help him , to convert a valid date to the softmind's standard date format , if the data is not right ,please point out that .

Input

There are several test cases. In each tese case one line contains a string of date .

Output

If the date in the input is valid ,please convert it into standard one then output it ,if it's invalid ,output "Invalid " .
The standard format of the date is: MM-DD-YYYY .

Sample Input

04-16-2008
04-Mar-2008
Mar-06-2008

Sample Output

04-16-2008
03-04-2008
Invalid

Source

Author: softmind





Description

给你两个数a和b,你的任务是计算出1在a和b之间出现的次数,比如说,如果a=1024,b=1032,那么a和b之间的数就是:

1024 1025 1026 1027 1028 1029 1030 1031 1032

则有10个1出现在这些数中。

Input

输入不会超过500行。每一行有两个数a和b,a和b的范围是0 < a, b < 100000000。输入两个0时程序结束,两个0不作为输入样例。

Output

对于每一对输入的a和b,输出一个数,代表1出现的个数。

Sample Input


1 10
44 497
346 542
1199 1748
1496 1403
1004 503
1714 190
1317 854
1976 494
1001 1960
0 0

Sample Output

2
185
40
666
113
105
1133
512
1375
1256



Description

小A家里有很多长度不一样的木棍,有一天他很无聊,只能摆弄这些木棒来解闷了。小A的数学学得很好,所以他想在这些木棒中挑出3根来组成一个直角三角形,
当然,他有可能有很多种选法,所以他还想挑出一个面积最大的。

Input

输入有多组,每组输入包括2行,第一行输入一个n(0<=n<=100),表示小A有n根木棍,接着一行有n个整数(<=1000),表示木棍的长度(长度从小到大给出)。

Output

输出面积最大的直角三角形的面积,且保留3位小数,如果不能组成,输出“My Good!”

Sample Input

4
1 2 3 4
5
2 3 4 5 6
6
3 4 5 6 8 10
2
1 1

Sample Output

My Good!
6.000
24.000
My Good!




Description

所谓的八数码问题,就是在一个3*3的矩阵中,放着1~8以及一个x,这样的九个字符,通过移动x,最后使的矩阵变成如下图的状态:

1 2 3
4 5 6
7 8 x

问题就是给你一中状态,问你通过移动中间的x是否能到达上图的状态,如果能输出x所走的路径,不能就输出“unsolvable”。

Input

输入包括多组测试数据,每组输入占一行,每行9个字符,表示矩阵中从左到右、从上到下的方格里的信息。
输入到文件结束。


Output

对于每组数据,输出一行,表示x所经过的路径。
u:上 d:下 l:左 r:右


Sample Input

2 3 4 1 5 x 7 6 8


Sample Output

ullddrurdllurdruldr




Description

C国的对头A国要进行军事演练,C国的国王想知道A国的工兵的动态,A国有n个工兵营,A国他们经常变换每个工兵营内的工兵数,C国的国王想知道A国他们一段工兵营内的人数。

Input

首先输入T,表示有T组数据。
每组第一行一个正整数1<=N<=50000,表示敌人有N个工兵营地,接下来是N个正整数,第i个数ai表示第i个工兵营内起初有的工兵数( 1<=ai<=50 )。
接下来每行有一条命令,命令有4种形式:
(1) Add i j ,i和j为正整数,表示第i个营地增加j个人(j不超过30);
(2) Sub i j ,i和j为正整数,表示第j个营地减少j个人(j不超过30) ;
(3) Query i j ,i和j为正整数,i<=j,表示询问第i到第j个营地的总人数;
(4) End 表示结束,这条命令在每组数据最后出现;
每组数据最多有40000条命令

Output

对第i组数据,首先输出“Case i:”和回车,对于每个Query询问,输出一个整数并回车,表示询问的段中的总人数,最多不超过1000000.

Sample Input

1
10
1 2 3 4 5 6 7 8 9 10
Query 1 3
Add 3 6
Query 2 7
Sub 10 2
Add 6 3
Query 3 10
End


Sample Output

Case 1:
6
33
59




Description

水是生命之源,这些大家都知道。所以但凡有水的地方都会有人。而且一般靠近江河湖海的地方人也特别的多。

人工湖是一个美丽壮阔的湖,在湖的四周分布着若干个城市。由于水路并不发达,所以这些城市的交通一般都是靠陆路。每个城市只和靠其左右的两个城市建有公路。即,我们可以这么想象:湖是一个圆,在圆上分布着N个城市,编号为1~N,编号为i的城市只和编号i%N+1,(i-2+N)%N+1两个城市有公路相连。当然路是双向的。由于城市之间的距离很远,有的路段常年不能得到很好的维护,所以可能有两个相邻之间的城市的公路会坏掉,当然这条公路就不能走了。但是这两个城市会在某个时候派出“工程队“去把坏的路修好。由于路况很难预测,所以YY市长会向你询问某两个城市的人民是否可以互相到达彼此的城市。

Input

第一行有两个数2<=N<=100000,1<=M<=100000,分别代表城市的数目和询问的次数接下来有M行,每行有一个标志数f和两个相邻城市的编号x,y。

当f=0,如果x,y之间的公路是好的,则x,y之间的公路会坏掉。如果是坏的,则x,y之间的公路将被修好。

当f=1,那就代表YY市长要开始询问了,那么后面你将回答x,y之间是否可以互相可达。

输入到文件结束。

Output

对于每一个询问,如果x,y互相可达则输出YES,否则输出NO。每个输出占一行。

Sample Input

5 10
1 2 5
0 4 5
1 4 5
0 2 3
1 3 4
1 1 3
0 1 2
0 2 3
1 2 4
1 2 5

Sample Output

YES
YES
YES
NO
YES
NO

Source

zxb







Description

The jewelry game is an interesting game. this game is run in a box of 13*6. While playing the game, it is given jewelrys with color red, blue, yellow, orange, green and purple. When any color of jewelry is 3 or more than 3 in direction of vertical, horizontal and diagonal these jewelry can be eliminated.

The game's screenshoot:


Now given a status of current, and a group of new stone, please tell that when the stones finally reach the buttom, what's the status of the game?

Input

The first line contain a integer n, indicate there will be n test case.

Each test case contain a table of character s whit 13 rows and 6 column, character B means jewelry of color blue , and R means a red one, O means a orange one, Y means a yellow one, G means a green one, P means a purple one. character W means there is no jewelry in this position.

Then followed 3 lines, each line contains a character, all this three line indicate the new coming jewelrys.

Finally is a integer m (1<=m<=6), indicate the position of new coming jewelrys.

Output

To each test case, output the state of the game when the new comming jewelrys reachd the buttom.

Sample Input

1
WWWWWW
WWWWWW
WWWWWW
WWWWWW
WWWWWW
WWWWWW
WWWWWW
WWWWWW
WWWWWW
WWWWWW
BBWWWW
BBWWWW
OOWWWW
B
B
Y
3

Sample Output

WWWWWW
WWWWWW
WWWWWW
WWWWWW
WWWWWW
WWWWWW
WWWWWW
WWWWWW
WWWWWW
WWWWWW
WWWWWW
WWWWWW
OOYWWW

Source

Author: zsong





Description

Wang Haiyang is a strong and optimistic Chinese youngster. Although born and brought up in the northern inland city Harbin, he has deep love and yearns for the boundless oceans. After graduation, he came to a coastal city and got a job in a marine transportation company. There, he held a position as a navigator in a freighter and began his new life.

The cargo vessel, Wang Haiyang worked on, sails among 6 ports between which exist 9 routes. At the first sight of his navigation chart, the 6 ports and 9 routes on it reminded him of Graph Theory that he studied in class at university. In the way that Leonhard Euler solved The Seven Bridges of Knoigsberg, Wang Haiyang regarded the navigation chart as a graph of Graph Theory. He considered the 6 ports as 6 nodes and 9 routes as 9 edges of the graph. The graph is illustrated as below.

According to Graph Theory, the number of edges related to a node is defined as Degree number of this node.

Wang Haiyang looked at the graph and thought, If arranged, the Degree numbers of all nodes of graph G can form such a sequence: 4, 4, 3,3,2,2, which is called the degree sequence of the graph. Of course, the degree sequence of any simple graph (according to Graph Theory, a graph without any parallel edge or ring is a simple graph) is a non-negative integer sequence?

Wang Haiyang is a thoughtful person and tends to think deeply over any scientific problem that grabs his interest. So as usual, he also gave this problem further thought, As we know, any a simple graph always corresponds with a non-negative integer sequence. But whether a non-negative integer sequence always corresponds with the degree sequence of a simple graph? That is, if given a non-negative integer sequence, are we sure that we can draw a simple graph according to it.?

Let's put forward such a definition: provided that a non-negative integer sequence is the degree sequence of a graph without any parallel edge or ring, that is, a simple graph, the sequence is draw-possible, otherwise, non-draw-possible. Now the problem faced with Wang Haiyang is how to test whether a non-negative integer sequence is draw-possible or not. Since Wang Haiyang hasn't studied Algorithm Design course, it is difficult for him to solve such a problem. Can you help him?

Input

The first line of input contains an integer T, indicates the number of test cases. In each case, there are n+1 numbers; first is an integer n (n<1000), which indicates there are n integers in the sequence; then follow n integers, which indicate the numbers of the degree sequence.

Output

For each case, the answer should be "yes"or "no" indicating this case is "draw-possible" or "non-draw-possible"

Sample Input

2
6 4 4 3 3 2 2
4 2 1 1 1

Sample Output

yes
no




Description

Tom gets up late today. In order to go to work faster, Tom asks you to calculate a best path for him. Tom takes the car to go to corp., and he will not stop until the traffic light is red when he arrives at the crossing. What's the minimum time Tom will take? You can suppose that the value of Tom's speed is 1,and all the traffic lights are red when Tom sets out to go to corp. The time of the traffic light being red is the same as the time of the traffic light being green, and all traffic lights have only these two colors. The places of Tom' home and corp. have no traffic lights.

Input

The first line of input contains a integer N (0<N<100) indicating the number of test cases. The first line of one test case contains a integer M (0<M<100), followed by M lines, and each line contains the data like "a b 20 10". It shows that Tom can reach b from a, and the distance between a and b is 20,and the time of the traffic light at b being red(or being green) is 10.The last line of one test case contains the names of Tom's home and corp. All names consist of one lower-case letter.

Output

Print the minimum time Tom takes in one line for one test case.

Sample Input

1
4
t a 20 10
t b 10 9
b a 10 11
a c 20 0
t c


Sample Output

40


Description

There are N(1<=N<=50000)students stand in a queue.We assume that every can only see the students that are in front of him and taller than him

.


For example, there are 6 students standing in a queue with height of
4 3 1 2 5 2,begining from the front student. In this example, student 3's height is 1, and he can see 2 persons. Student 6,
although many students in front are taller than him, but he can only see the student with height of 5.

Now, given the number of students in a queue, and the height of each, can you find the student that can see most persons.

Input

Input contains multiple test cases. The first line is a integer T, the number of cases.The first line of each case is a integer N, the number of students.The second line of each case contains the heights of students from front to back.

Output

For each test case, print a line with a integer M, representing the maximum number of students can someone can see.

Sample Input

2
6
4 3 1 2 5 2
3
2 2 2


Sample Output

2
0


Description

Give you a expression,you can add some parenthesis to maximize result.Example as following:
1 + 2 * 3
Its result is 7 in the example.But you can add a parenthesis like (1 + 2) * 3,then the result is 9,and so it is the maximization of the example.
You job is to find the maximizaton of a expression. To simplify this problem,you can assume that expression contains only operator + and *,
but note that integers may be negative.

Input

Input contains multiple test cases.Each case begin with a integer N(2<=N<=100), the number of integers of a expression.Then follows the expression.Integers and operator spearate with a single whitespace.

Output

For each case print a single line with the maximized value of the expression.

Sample Input

4
1 + 2 * 3 + -1

Sample Output

8





Description

Cc is a lovely monkey. It likes to play the game "catching plates".

The game is as follows.

There are n pegs in a line numbered from 1 to n. Cc stands on the first peg at the beginning. It is rather hard for Cc to jump from peg i to peg i+1(i+1<=n) or peg i-1(i-1>=1), which takes him exactly one second. He can jump at most t times. And he will only jump at the beginning of one second.There is a clown at the other end. He has m plates in hand. He will throw a plate to one peg every second. The clown will throw the plate exactly to the peg. The plates will get broken if they hit the pegs. Cc can catch the plate if only he stands on the peg the plate is thrown to. For simplicity, the process of throwing and catching don't take any time at all. Suppose the clown will throw a plate to the 9th peg at the 9th second, if Cc stands on peg 9 at the 8th second and stands still for a second, or if Cc stand on peg 8 at the 8th second and jumps to peg 9, or if Cc stand on peg 10 at the 8th second and jumps to peg 9, he can catch the plate.

There is a positive integer on each plate, indicating the bananas Cc can get if he catch that plate. Cc will know the way the clown throw the plates in advance. Now he wants to get as many bananas as possible.

Input

For each test case,the first line contains three integers n, m and t(1<=n<=100,1<=m<=100,0<=t<=100), indicating the number of the pegs, the number of the plates and the maximum number Cc can jump.The next m lines gives ai and bi each, which means the clown will throw a plate with number bi on it to peg ai at the ith second.

Process to the end of file.

Output

For each test case, first print a line saying "Scenario #k", where k is the number of the test case.Then, print the maximum number Cc can get, one per line.Print a blank line after each test case, even after the last one.

Sample Input

4 4 2
2 10
3 15
1 10
1 8
4 4 4
2 10
3 15
1 10
1 8
2 2 1
1 1
2 1

Sample Output

Scenario #1
28

Scenario #2
33

Scenario #3
2

Source

Heilongjiang Province 4th CPC




Description

Mr. Li has a telephone.This confuses him very much.Because he always receives advertising messages.In order to get the important messages,he has to delete all the advertising messages.

The advertising message is received randomly.And the time that deleting one message takes is different.Li's phone has one amazing operation that it can delete all the messages.This operation spend the sum of the shortest message's delete time and the longest message's delete time.

Mr. Li is a weired person.He insists on that the messages which arrives later shouldn't be deleted earlier than the messages which arrives earlier. Time is valuable.Mr. Li wants to know the shortest time he needs to delete all the messages.

Input

There are several cases.Each case contains one integer n(1<=n<=500) firstly,indicating that there are n messages.Then n lines follow.Each line contains two positive integers a and b.a is the arrival time of the message.b is the time that deleting the message takes.We assume that the arrival time of each message is different.The input is ended by EOF

Output

For each case, please output the shortest time that deleting all the messages takes.

Sample Input

4
1 3
2 4
9 1
11 2
4
4 2
3 2
2 2
1 1

Sample Output

13
7

Source

Heilongjiang Province 4th CPC Online



Description

Suppose there is a tree named A. All nodes of A have a weight v(0<v<4000000).Now, we will give the definition of "Prime Node".A node is a Prime Node if the following conditions are satisfied.The subtree of A whose root node is b will be marked as B. If all nodes in B have prime weights and b's weight is greater than other nodes', then b is a Prime Node.Now you are to calculate how many Prime Nodes are in A.

Input

For each test case:The fist line will contains an integer n(1<=n<=10000) indicating the number of nodes in A,the root of A will always be node 1.The second line has n integers giving the weights of each node numbered from 1 to n.The following n-1 lines, each contains a pair of integers x and y indicating there is an edge between x and y, give the n-1 edges of A.

Process to the end of file.

Output

For each test case, first print a line saying "Scenario #k", where k is the number of the test case.Then, print the number of Prime Nodes on a single line.Print a blank line after each test case, even after the last one.

Sample Input

5
12 11 5 7 3
1 2
2 3
2 5
3 4

Sample Output

Scenario #1
3


Source

Heilongjiang Province 4th CPC




Description

哪怕在和平的年代,许多国家也会举行演习来保持军队的警惕性。某个国家也发动了一次虚拟的海军战役。
在演习阶段,海军上将打算评估两个战舰的战斗力,“胜利号”和“荣誉号”,所以他让两个战舰进行打击练习。两艘战舰的指挥官都是年轻有前途的青年,都以出色的成绩毕业于海军学院。他们不仅有丰富的导航经验,也掌握了很深的科学知识,特别是数学方面的。

这位海军上将指定了一个 有许多星罗棋布的小岛的区域。假设这些小岛都被敌方占领,而且敌方的火力点存在优势。虚拟情景和比赛的要求如下:
(1) 所有被占领的小岛都是互相连接的。岛屿之间有若干路线, 但这些路线都是单向的。换句话说,如果我们把每个小岛看作结点,每条路线当作边,则可以得到一个有向无环图。
(2)图中有且仅有一个一号岛 屿。就是说我们从这个岛屿出发就能抵达任何其他小岛。(当然,一号岛屿并不一定是序号为一的岛屿)。
(3)演习开始时,两艘战舰同时 到达一号岛屿然后一同消灭所有的敌方火力点。
(4)这两艘战舰轮流导航并且每到达一个岛屿就交换导航权再一起航行。每次它们只能沿着 一条单向路线驶向下一个岛屿,然后消灭岛屿上的所有敌对火力点。注意,“胜利号”首先从一号岛屿开始导航。
(5)因为每条路线都是单向的, 而且这是一个有向无环图,因此总有战舰无法继续导航的时候,此时演习终止。
(6)演习终止后,计算沿途消灭的火力点数目,如果这个数目大 于某个上将指定的数目f则“胜利号”获胜,否则“荣誉号”获胜。
战舰的指挥官都是优秀的数学家。接到任务后,他们把其视为图论问题。在一张图上画出结点和边,每个结点有一个正数,两人轮流沿着一定 的路线移动,直到无法移动为止。计算这条路线上所有数字的和并和上将指定的f比较,决定最后的输赢。
在此,我们认为两人总是做 出对自己最有利的选择。


Input

输入多组测试样例,每个样例第一行有三个数字n,m,f。n表示图中有n(1<n<10000)个结点。分别编号1到n。m表示图中 有m条边。接下来一行有n个正数,依次表示每个结点中的火力点数目。最后m行,每行两个整数a,b表示在a和b结点中有 一条路线。输入以EOF终结。

Output

对于每个测试样例,如果“胜利号”获胜则输 出"Victory",如果“荣誉号”获胜则输出"Glory"。每个输出占一行。

Sample Input

4 4 7
2 2 2 2
4 2
2 1
4 3
3 1
4 5 6
1 2 3 4
1 2
1 3
1 4
2 3
4 3


Sample Output

Glory
Victory


Description

小丹手里有n根不同长度的木棍,她一根一根的按顺序把它们丢到地上,木棍在地上的位置是随机的。后面丢的木棍一定在前面丢的木棍的前面,现在需要让你求出丢完所有木棍后,最上面一层木棍的编号。


Input

每中情况第一行是n(1 <= n <= 100000)木棍的数目,接下来n行是按顺序丢的每根木棍的两个端点坐标。输入当n为0时结束。


Output

每次输出随上面一层木棍的编号,按升序。


Sample Input

5
1 1 4 2
2 3 3 1
1 -2.0 8 4
1 4 8 2
3 3 6 -2.0
3
0 0 1 1
1 0 2 1
2 0 3 1
0


Sample Output

Top sticks: 2, 4, 5.
Top sticks: 1, 2, 3.


Description

现在有一种新研发的卫星,它配备了一种智能的相机,这种相机对拍摄的地球上的图片中有公路连接的一片封闭的城市区域进行压缩处理。这样就需要不同的区域之间没有相交的部分。但是最近科学家发现了一种bug图片,如右图,它的最外一层轮廓就不符合条件。
其中城市间的公路有如下连接要求:
图片中所有的城市至少有两条公路和其他城市连接;
每对城市之间一定会有一条路径;
每对城市之间至多有一条公路;
每条公路不相互交叉。
现在需要你写一个程序求出最外层的区域。

Input

第一行一个整数N(1<=N<=20),测试的情况。每组测试数据的第一行是图片中城市的数目n(1<=n<=50),接下来的n行是n个城市的坐标,每行两个整数。下一行是整数m(1<=m<=50),表示有多少可以压缩的区域。接下来的m行中,每行给出每个区域的轮廓上的城市编号,按照顺时针或逆时针。


Output

输出最外轮廓在m个区域中的编号。


Sample Input

1
5
2 6
4 4
4 7
8 6
4 10
3
4 1 2 4 3
4 1 3 4 5
4 1 2 4 5


Sample Output

3


Description

在xy坐标系中给出许多点,求用一个单位圆(半径为1)最多能覆盖多少个点。点在单位圆内和其上都算作覆盖。

Input

输入有许多组测试数据,其中每组测试数据的第一行是图中给出的点数n(1<=n<=300),当n为0时输入结束。接下来的n行,每行有两个有五位小数点的小数分别代表点的横纵坐标。没有两个点的距离小于0.0001,任何两点的距离不满足1.9999<=d<=2.0001。


Output

每组测试数据输出单位圆能覆盖的最多的顶点数目。


Sample Input

3
6.47634 7.69628
5.16828 4.79915
6.69533 6.20378
6
7.15296 4.08328
6.50827 2.69466
5.91219 3.86661
5.29853 4.16097
6.10838 3.46039
6.34060 2.41599
8
7.90650 4.01746
4.10998 4.18354
4.67289 4.01887
6.33885 4.28388
4.98106 3.82728
5.12379 5.16473
7.84664 4.67693
4.02776 3.87990
20
6.65128 5.47490
6.42743 6.26189
6.35864 4.61611
6.59020 4.54228
4.43967 5.70059
4.38226 5.70536
5.50755 6.18163
7.41971 6.13668
6.71936 3.04496
5.61832 4.23857
5.99424 4.29328
5.60961 4.32998
6.82242 5.79683
5.44693 3.82724
6.70906 3.65736
7.89087 5.68000
6.23300 4.59530
5.92401 4.92329
6.24168 3.81389
6.22671 3.62210
0


Sample Output

2
5
5
11


Description

说到自然数,它是如此简单,几乎没有人不知道。但是有时候它们之间的一些规律你却真的不知道。比如3,4,5,就我们所知,它们是非常有名的勾股定理:3^2+4^2=5^2。
那么看一下下面的一组数10、11、12、13、14,你能找到什么?也许你不能马上找到它们之间的关系,那么这个式子呢:10^2+11^2+12^2=13^2+14^2.,你从这里得到什么什么启发了吗?
现在让我们仔细官场这两组数:
3、4、5 3^2+4^2=5^2
10、11、12、13、14 10^2+11^2+12^2=13^2+14^2
你会发现它们都是连续的自然数,而且式子左边有n+1个自然数,右边有n个自然数。

Input

输入一个自然数n (1<=n<=1000),请判断是否存在2*n+1个连续的自然数满足左边n+1个数的平方和等于右边n个数的平方和。


Output

如果你找到这样的解,输出这2*n+1个数,每两个数之间一个空格。


Sample Input

1
2


Sample Output

3 4 5
10 11 12 13 14 15



Description

在一首诗(或者一首很长的诗歌中的一节)中,韵律安排使我们知道哪些行和其他行有相同的韵脚(尾音发音相同或相近)。
例如,一首五行打油诗如下:
如果你能用量子做电脑,
那么所有的间谍都想要。
我们的代码将全部完蛋,
他们将阅读我们的信函,
直到我们加密到量子将他们难倒。
珍妮弗和彼得肖
它的韵律安排是“aabba”,也就是说第1,2,5行具有相同的韵脚,第3,4行具有相同的韵脚。
对于一首只有四行的诗或诗节来说,只有15种本质上不相同的韵律安排。
aaaa, aaab, aaba, aabb, aabc, abaa, abab, abac, abba, abbb, abbc, abca, abcb, abcc, and abcd.
请写出程序,计算一首N行诗的不同韵律安排方案数(N将会由输入给出)

Input

输入有一系列的N值(诗的行数)组成,每行只含有一个数,数字0表示输入数据结束。


Output

对于每个输入的N,你的程序需要输出N,接着输出一个空格,然后是N行诗具有的韵律安排方案数


Sample Input

1
2
3
4
20
30
10
0


Sample Output

1 1
2 2
3 5
4 15
20 51724158235372
30 846749014511809332450147
10 115975


Description

给出一个无限的数字序列 2,3,....对其进行一些操作.
刚才提到的操作是从序列中选出一 个未被选择过的最小的数, 并对其除了自身之外的倍数进行反转操作(反转操作: 如果一个数在序列中, 将其删除; 如果不在, 将其加入)
例如, 第一步, 选择数字2, 改变4,6,8,10...的状态---他们将被从序列中删除. 第二步, 选择3, 改变6,9,12,15...的状态。注意: 在第二步操作时, 9和15被移出序列, 而6和12被加入序列.

Input

每行输入包括一个整数n, n=0表示输入结束.


Output

根据n是否在序列中, 输出"yes"或"no".


Sample Input

2
30
90
0


Sample Output

yes
yes
no

声明:所给的整数的都能分解成13000000内的数相乘,但是所给的整数可能很大。比如可以给一个整数10000000000000000000000000000000(31个0)可以表示成10*10*10*...*10(31个10相乘)。




Description

Thala教授在我 们学院中最受欢迎. 尽管选择Thala教授意味着你今后的学习任务将很多很艰难, 但鉴于当前的世界形势, 学生们需要掌握更多知识来找到好的工作,
因此越来越多的学生想要选择Thala教授作为他们的导师. 然而我们学校有规定, 每个教授带的学生数目都有上限, 因此Thala教授需要挑出最为杰出的学生作为他的弟子.
Thala教授知道, 想要学好计算机, 学生们需要丰富的数学知识. 于是, Thala教授总是用许多数学题目来挑选他的学生.
这一年, Thala教授的题目之一是这样的: 给出数字n, 如果n可以被表示为2个合数的乘积, 这个数就被叫做"thala number", 否则就被叫做"loser number'.
例如81=9*9, 因此81就是"thala number". Thala教授交给学生们许多数, 要求学生判断这些数是"thala number"还是"loser number".
Softa是 Thala教授的一个疯狂的仰慕者, 他十分渴望成为Thala教授的学生, 并在Thala教授的实验室中学习. Softa知道他必须在Thala教授的考试中表现出色,
否则Thala教授将不会注意到他. 但当面对Thala教授的数字的时候, Softa感到紧张, 他对自己说:"Thala教授的确和传说中一样伟大. 可是这些数字实在太多,
一个人无法在这么短的时间内作出回答. Thala教授一定是想要同时考察学生的数学与编程知识. 因此, 我需要一个程序来计算出答案." 想到了这点, Softa感觉好多了,
因为他有许多朋友参与了"ACM/ICPC"竞赛, 他们可以帮助Softa. 当然, 你也想要想Softa展示你的编程技巧, 因此, 你的程序应该高效, 这样才能让Softa更加钦佩你.

Input

Thala教授发布题目的方式是这样的: 每个学生会收到很多组测试数据, 按Thala教授的规则, 测试数据将越来越难, 这样他就可以轻松地控制学生的数量.
只有回答正确的学生可以进入下一道题目, 否则就会退出考试. 这样下去直到剩余的学生数目等于Thala教授想要的学生数目.


Output

对于每组输入数据, 请在时间T之内判断数据中的每一个数是"thala number"还是"loser number", 并输出你的答案. 在每组数据之间输出一个空白行.


Sample Input

2 2
81
25

1 1
16


Sample Output

thala number
loser number

thala number


Description

中国人认为8是幸运的数字. Bob同样喜欢数字8. 不过, Bob有他自己的幸运数字L. 现在他想要构造出一个最幸运的数, 使这最幸运的数是最小的能被L整除并且只包含数字8的数.

Input

输入包含多组测试数据. 每一组测试数据只有一行, 包含了L(1<=L<=2,000,000,000). 最后一组测试数据后是一行, 包含一个数字0.


Output

对于每组输入数据, 输出一行, 包含了测试数据的序号(从1开始), 以及Bob的最幸运的数. 如果这样的数无法被构造出来, 输出0.


Sample Input

8
11
16
0


Sample Output

Case 1: 1
Case 2: 2
Case 3: 0


Description

现有一公式:X^a mod b = c.给出a,b,c,求出所有满足条件的X。

Input

输入包括多组数据,每组数据三个正整数1<=a,b,c<=10^9,b总是质数。


Output

每组数据输出若干行,每一行代表了满足方程的一个X的解,解的顺序按照从小到大输出,最后输出一个空行。没有解输出“No Solution!”


Sample Input

3 13 8
2 3 2


Sample Output

2
5
6

No Solution!


Description

现在有一列人,从1到n对这n个人进行编号,现在这n个人开始排队,有一个排队规则就是编号为i的人不能站在第i位上,问n个人进行排队,有多少种可能的排队方法。

Input

输入包括多组测试数据,每组测试数据含一个整数n,代表一共有n个人进行排队(1<=n<=1000)。


Output

输出包括一个整数,代表有多少种可能的排队方法。


Sample Input

3
4
6


Sample Output

2
9
265


Description

从A+B个不同的物品中选择A个物品,共有多少种不同的选法。由于A,B会很大,所以结果对C取下余。

Input

首先输入T,代表共有T组测试数据。
每组数据包括三个数字,A,B,C;


Output

输出只有一个数,如题目描述。


Sample Input

2
1 1 100
2 2 100


Sample Output

2
6


Description

On a clear moon-less night, you can see millions of stars glimmering in the sky. Faced with this overwhelming number, the Greeks started nearly 2,000 years ago to bring some order to the chaos. They identified groups of stars, called constellations, and gave them names, mostly from the Greek mythology, that are still in use today. Examples are ``Ursa Minor'', ``Pisces'', ``Cancer'', and many others.

Given a sketch of the constellation, it is not easy for the amateur to actually find the constellation in the sky. Moreover, simple constellations, such as ``Triangulum'' (triangle,) which consists of only three stars, may appear several times in the sky. Again, singling out the ``correct'' occurrence is not easy.

Traditionally, maps were printed for just this purpose. But in this problem, we will see how the computer can help us find constellations in the sky.

You will be given a star map; for simplicity this will be a collection of points in the plane, each having a certain brightness associated with it. Then, given a constellation, also as a set of points in the plane, you are to determine:

?the number of occurrences of the constellation in the star map, and

?the position of the brightest occurrence, if one exists. (The rationale behind this is as follows: if a constellation seems to appear several times in the sky, the brightest one is most likely to be the real one, since it is the most eye-catching one.)

An occurrence is a subset of stars from the map that forms a (possibly) arbitrarily rotated and/or scaled copy of the stars in the constellation.

The brightness of an occurrence is the average brightness of the stars it consists of, i.e. the sum of individual brightnesses divided by the number of stars in the constellation.

Input

The input file contains the descriptions of several star maps. Each map starts with a line containing a single integer n, specifying the number of stars in the map (1 <= n < 1000). The following n lines contain three integers each, namely the x- and y-coordinates and the brightness of every star. The larger the value, the brighter the star shines.

The next line contains a single integer m, the number of constellations to follow (1 <= m < 50). Each constellation description starts with a line containing an integer si, the number of stars in constellation i, and a string Ni, the name of the constellation. (Ni will consist of no more than 40 characters and contain no blanks.) The following si lines then contain the coordinates of the constellation, again as x/y-pairs.

A blank line separates the star map from the next map. The input file ends with an empty map (having n = 0), which should not be processed.

N.B.: Since all star coordinates are integer numbers, you can easily rule out any rotated or scaled constellation whose points do not fall on integer coordinates.

Output

For each star map first output the number of the map (`Map #1', `Map #2', etc.) on a line of its own.

For each constellation, in the same order as in the input, output first its name and how many times it occurs in the map on one line, as shown in the output sample.

If there is at least one occurrence, output the position of the brightest occurrence by listing the positions of the stars that form the brightest occurrence. The star positions have to be printed in ascending x-order. Positions having the same x-coordinates must be sorted in ascending y-order. If there are several equally bright solutions, output only one of them. Adhere to the format shown in the sample output.

Output a blank line before each constellation and a line of 5 dashes (`-----') after every star map.

Sample Input

6
1 2 1
2 1 4
2 4 3
3 2 1
4 1 5
4 3 2
2
3 Triangulum
1 1
3 1
2 4
4 Cancer
1 3
4 3
6 1
7 5

0

Sample Output

Map #1

Triangulum occurs 2 time(s) in the map.
Brightest occurrence: (1,2) (4,1) (4,3)

Cancer occurs 0 time(s) in the map.
-----

Source

Southwestern European Regional Contest ETH Z??rich,November 16, 1996


更多相关文档:

ACM简单例题四

ACM 简单例题四 鸡兔同笼 查看文章 C 程序设计基础-鸡兔同笼 2009-10-26 ...ACM简单例题 6页 免费 ACM简单练习题 13页 免费 ACM 入门简单试题 12页 2...

ACM百练习题分类汇总

ACM练习题分类汇总_IT认证_资格考试/认证_教育专区。百练上的题,ACM入门用 ...简单密码 ac 数字求和 垂直直方图 1017 简单计算题 ac 棋盘上的距离 2714 2715...

ACM必做50题的解题-模拟

ACM必做50题的解题-模拟_理学_高等教育_教育专区。POJ 1029 False coin Slyar...} poj 1120 A New Growth Industry 这道题目比较简单,只是对于题目的理解可能不...

ACM试题及答案

本题仍然需要采用循环读入。下面给出三个示例程序。...A:注册 一个帐号,然后就可以练习,点击比赛列表 ...ACM简单例题 暂无评价 21页 5下载券 ACM之组合数学...

acm编程作业练习题

acm编程作业练习题_IT认证_资格考试/认证_教育专区。acm编程作业练习题杭电...每次考试的第一个题目总是很简单, 今天也不例外, 本题是要求输出指定大小的"...

杭电acm 练习题100例(删减版)

杭电acm 练习题100例(删减版)_其它_高等教育_教育专区。【程序 1】题目:有 ...=== 【程序 75】题目:放松一下,算一道简单的题目。 main() { int i,n...

ACM几道练习题及其答案

ACM几道练习题及其答案_其它_高等教育_教育专区 暂无评价|0人阅读|0次下载|举报文档 ACM几道练习题及其答案_其它_高等教育_教育专区。ACM练习题...

整理的---ACM题目及答案_图文

整理的---ACM题目及答案_其它_高等教育_教育专区。ACM大赛经典题目与答案 杭电...每次考试的第一个题目总是很简单, 今天也不例外, 本题是要求输出指定大小的"...

ACM练习题

ACM练习题_IT认证_资格考试/认证_教育专区。ACM 练习题 ZDM 一、 高精度运算 Propram 1: Input file: t1.in X+Y , X-Y Output file: t1.out Time limi...

acm编程比赛入门题目集

acm编程比赛入门题目集_计算机软件及应用_IT/计算机_...最简单的计算机 Time Limit: 2000/1000 MS (Java/...描述】 让我们来做做 David Hilbert 的一个练习题...
更多相关标签:
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com