第五届程序设计大赛预赛第二场题目

 

1.Elegant fibonacci numbers again

Time Limit:

1000MS

Memory Limit:

10000K

Description

Fibonacci numbers are nice simple integers. All of you are familiar with it, aren’t you?

The Fibonacci sequenceare defined by the recurrence:

F[0]=0;

F[1]=1;

F[n]=F[n-1]+F[n-2], for n>1

You know that the value of F[n] increases rapidly when the n becomes larger. So for each test case, output the value F[n] mod m will be ok.

Input

The first line of the input is a positive integer. It is the number of the test cases followed. Each test case two integers n (0<=n<2^32) and m (0

Output

The output of the program should consist of one line of output for each test case. The output of each test case only contains one integer which equals to the value F[n] mod m. No any redundant spaces are needed.

Sample Input

2

1 1000

2 100

Sample Output

1

1

 

2.Conflict

Time Limit:

1000MS

Memory Limit:

10000K

Description

Given several formula like “variable1 relation variable2”,where relation may be <,<=,=,!=,>=,variables may contain up to 10 letters or digits and are case-sensitive. Please determine whether there is a conflict.

Input

There are several cases. Each case begins with a line “Case%n:”(%n is the case number),and contains several formulas, one per line. There are no more than 100 formulas for each case. Please see sample input for more details. Input is terminated by EOF.

Output

If there is no conflict, output “YES”, otherwise, output “NO”. Please refer to sample output for the exact output format.

Sample Input

Case1:

xyz < 123

123 < 45

Case2:

x < y

y < x

Sample Output

Case1: YES

Case2: NO

 

3.Hotel

Time Limit:

2000MS

Memory Limit:

10000K

Description

Last year summer Max traveled to California for his vacation. He had a great time there: took many photos, visited famous universities, enjoyed beautiful beaches and tasted various delicious foods. It is such a good trip that Max plans to travel there one more time this year. Max is satisfied with the accommodation of the hotel he booked last year but he lost the card of that hotel and not remembers quite clearly what its name is. So, Max searched in web for the information of hotels in California and got piles of choice. Could you help Max pick out those that might be right hotel?

Input

Input may consist of several test data sets. For each data set, it can be format as below:

For the first line, there is ones string consisting of ‘*’, ’?’, and ‘a’-‘z’ characters. This string represents the hotel name that Max can remember. The ‘*’ and ‘?’ is wildcard characters. ‘*’ matches zero or more lowercase character(s), and ‘?’ matches only one lowercase character.

In the next line there is one integer n (1 ≦n≦10000) representing the number of hotel Max found and then n lines follow. Each line contains one string of lowercase character(s), the name of the hotel.

The length of every string doesn’t exceed 50.

Output

For each test data set, just simply output one integer in a line telling the number of hotel in the list whose name matches the one Max remembered.

Sample Input

herbert

2

amazon

herbert

?ert*

2

amazon

hertert

*

2

amazon

anything

hertber?

2

amazon

herber

Sample Output

1

1

2

0

 

4.Game

Time Limit:

1000MS

Memory Limit:

10000K

Description

Bob always plays game with Alice. Today, they are playing a game on a tree. Alice has m1 stones, Bob has m2 stones. At the beginning of the game, all the stones are placed on the nodes of a tree, except the root. Alice moves first and they take turns moving the stones. On each turn, the player chooses exactly ONE of his stones, move this stone from current node to its parent node. During the game, any number of stones can be put on the same node.

The player who first moves all of his stones to the root of the tree is the loser. Assume that Bob and Alice are both clever enough. Given the initial positions of the stones, write a program to find the winner.

Input

Input contains multiple test cases.

The first line of each test case contains three integers: n(1≦10), m1(1≦m1≦3), m2(1≦m2≦3),n is the number of nodes.

Next n-1 lines describe the tree. Each line contains two integers A and B in range [0,n], representing an edge of the tree. Node 0 is the root.

There are m1 integers and m2 integers on the next two lines, representing the initial positions of Alice’s and Bob’s stones.

There is a blank line after each test case.

Output

For each test case, just simply output the winner's name.

Sample Input

3 1 1

0 1

2 0

1

2

 

3 2 1

0 1

1 2

2 2

2

Sample Output

Bob

Alice

 

5.Small tree

Time Limit:

1000MS

Memory Limit:

10000K

Description

There is a rooted tree which has N nodes numbered from 0 to N-1. Root is labeled 0. Each edge connects two nodes with a weight. Your job is to find S, a set of nodes {s1,s2…sm}(0≦m< N),satisfying that:

（1）Root is not in S, which means 0≦i≦m;

（2）There is only one common ancestor between si and sj, which means, they have no common ancestor except root.

（3）There are two associate set W, {w1,w2…wm}, and D,{d1,d2…dm},wi is the sum of weights of the path from root to si,di is the edge numbers of the path from root to si. The average outcome of S=∑wi/∑di(1≦i≦m) is maximal.

Input

There is a number T in the first line which is the number of test cases.

Each case begins with a integer n(2≦n≦1000), the number of nodes of the tree.

Next n-1 lines each contains three integers i, j, k, indicating there is a directed edge from i to j with weight k.

Output

Output a floating point number for each case ,which is the maximum average weight of S.

Exact to 0.01.

Sample Input

3

1

2

0 1 2

3

0 1 1

0 2 2

Sample Output

0.00

2.00

2.00

 

6.Jetpack Sniper 3000 Fragfest Extreme

Time Limit:

1000MS

Memory Limit:

65536K

Description

You are a beta tester for a new online game, Jetpack Sniper 3000 Fragfest Extreme. In this game, players with jetpacks fly around major metropolitan areas and attempt to shoot each other with laser guns. The only obstacles behind which players can hide are the ever-present glass towers of cubicle farms, skyscrapers.

To assist you in playing the game, you've written a program that will tell you which players could currently shoot (or be shot) by you. These are the players who have an unobstructed view of your position.

Input

Input to this problem will begin with a line containing a single integer n indicating the number of cities in the input. Each city is made of 100 city blocks (10x10), each of which contains a skyscraper of an integer height from 0 to 9. A city is represented in the input as 10 lines of 10 integers, where the integers are the height values of the corresponding skyscrapers. This is followed by one line with four sets of coordinates. The first denotes your position; the other three denote the positions of players A, B, and C, respectively. Positions are given in the format (x, y, height), where x is measured from left to right on the input city grid, y is measured from top to bottom, height is measured from the ground up, and (0,0,0) is at the top left of the input city grid at ground level.

Note:

l  The coordinates of player positions may contain floating point numbers.

l  Neither you nor any of the other players will ever be inside a building or on one of its edges or sides. Your line of sight to another player will never be tangent to the side, edge, or corner of a building in such a way that it changes the outcome of the program.

Output

For each city in the input, output the header "Fragfest City #X" where X is 1 for the first city, 2 for the second, etc. Follow this line with one line for each of players A, B, and C and print either "Player Y is in sight" or "Player Y is hiding" depending on whether or not a building obstructs your view of that player.

Please make these two simplifying assumptions:

1.A skyscraper is a rectangular solid with dimensions 1x1xheight;

2.a player is the size and shape of a point;

3.and a player does not block the view of another player.

Sample Input

2

0000005000

0000005000

0000005000

0000005000

9999999999

0000000000

0000000000

0000000000

0000000000

0000000000

(0,0,0) (10, 10, 10) (5.5, 5.5, 5.5) (9, 1.0, 9)

0123456789

1000000000

2064646400

3045555600

4065005400

5045005600

6065555400

7046464600

8000000000

9123456789

(4.5, 4.5, 5.5) (7.5, 4.5, 5.5) (1.5, 4.5, 5.1) (7.5, 4.5, 6.5)

Sample Output

Fragfest City #1

Player A is hiding

Player B is hiding

Player C is in sight

Fragfest City #2

Player A is in sight

Player B is hiding

Player C is in sight