# ACM简单练习题

Description

Input

（3<=n<=16），表示包围区的顶点的个数。

。再接下来的一行是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

1024 1025 1026 1027 1028 1029 1030 1031 1032

Input

Output

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

Input

Output

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

1 2 3
4 5 6
7 8 x

Input

Output

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

（2） Sub i j ，i和j为正整数，表示第j个营地减少j个人（j不超过30） ；
（3） Query i j ，i和j为正整数，i<=j，表示询问第i到第j个营地的总人数；
（4） End 表示结束，这条命令在每组数据最后出现；

Output

Sample Input

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

Sample Output

Case 1:
6
33
59

Description

Input

Output

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则“胜利号”获胜，否则“荣誉号”获胜。

Input

Output

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

Input

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

Input

Output

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

Input

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

Input

Output

Sample Input

1
2

Sample Output

3 4 5
10 11 12 13 14 15

Description

aaaa, aaab, aaba, aabb, aabc, abaa, abab, abac, abba, abbb, abbc, abca, abcb, abcc, and abcd.

Input

Output

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

Input

Output

Sample Input

2
30
90
0

Sample Output

yes
yes
no

Description

Thala教授在我 们学院中最受欢迎. 尽管选择Thala教授意味着你今后的学习任务将很多很艰难, 但鉴于当前的世界形势, 学生们需要掌握更多知识来找到好的工作,

Thala教授知道, 想要学好计算机, 学生们需要丰富的数学知识. 于是, Thala教授总是用许多数学题目来挑选他的学生.

Softa是 Thala教授的一个疯狂的仰慕者, 他十分渴望成为Thala教授的学生, 并在Thala教授的实验室中学习. Softa知道他必须在Thala教授的考试中表现出色,

Input

Thala教授发布题目的方式是这样的: 每个学生会收到很多组测试数据, 按Thala教授的规则, 测试数据将越来越难, 这样他就可以轻松地控制学生的数量.

Output

Sample Input

2 2
81
25

1 1
16

Sample Output

thala number
loser number

thala number

Description

Input

Output

Sample Input

8
11
16
0

Sample Output

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

Description

Input

Output

Sample Input

3 13 8
2 3 2

Sample Output

2
5
6

No Solution！

Description

Input

Output

Sample Input

3
4
6

Sample Output

2
9
265

Description

Input

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_入门简单试题[1]

ACM_入门简单试题[1]_英语考试_外语学习_教育专区。在线评判系统中,一道题目的...ACM入门简单数学题 暂无评价 31页 免费 ACM入门习题一百道(1) 19页 1下载券...

### ACM经典算法及配套练习题

ACM经典算法及配套练习题_计算机软件及应用_IT/计算机_专业资料。ACM入门算法及习题...(poj1837,poj1276) (2)型如下表的简单 DP(可参考 lrj 的书 page149): ...

### ACM练习题

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

### ACM几道练习题及其答案

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

### ACM竞赛练习题

ACM竞赛练习题_英语考试_外语学习_教育专区。ACM竞赛练习题 1、蛇和梯子 2002 年 11 月 2 日 阿拉伯和北非地区第 5 届地区赛 问题简述:“蛇和梯子”是一个...

### ACM练习题_图文

ACM练习题_IT/计算机_专业资料。本人收集的各种ACM练习题!!!绝对绝无仅有!!!赶紧下载收藏吧!!!ACM 练习题(1)描述 浙江工商大学校园里绿树成荫,环境非常舒适,...

### acm编程作业练习题

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

### ACM练习题

00 结束时间: 2008-12-26 20:30:00 第二题为选做,是我和同学以前做的 Acm 练习题,希望大家都能参与到其中来 是我和同学以前做的 希望大家都能参与到其中...