group: B

Program 1： Transmitters（TOJ_1916）

In a wireless network with multiple transmitters sending on the same frequencies, it is often a requirement that signals don't overlap, or at least that they don't conflict. One way of accomplishing this is to restrict a transmitter's coverage area. This problem uses a shielded transmitter that only broadcasts in a semicircle.

A transmitter T is located somewhere on a 1,000 square meter grid. It broadcasts in a semicircular area of radius r. The transmitter may be rotated any amount, but not moved. Given N points anywhere on the grid, compute the maximum number of points that can be simultaneously reached by the transmitter's signal. Figure 1 shows the same data points with two different transmitter rotations.

All input coordinates are integers (0-1000). The radius is a positive real number greater than 0. Points on the boundary of a semicircle are considered within that semicircle. There are 1-150 unique points to examine per transmitter. No points are at the same location as the transmitter.

Input consists of information for one or more independent transmitter problems. Each problem begins with one line containing the (x,y) coordinates of the transmitter followed by the broadcast radius, r. The next line contains the number of points N on the grid, followed by N sets of (x,y) coordinates, one set per line. The end of the input is signalled by a line with a negative radius; the (x,y) values will be present but indeterminate. Figures 1 and 2 represent the data in the first two example data sets below, though they are on different scales. Figures 1a and 2 show transmitter rotations that result in maximal coverage.

For each transmitter, the output contains a single line with the maximum number of points that can be contained in some semicircle.

Sample Input

25 25 3.5

7

25 28

23 27

27 27

24 23

26 23

24 29

26 29

350 200 2.0

5

350 202

350 199

350 198

348 200

352 200

995 995 10.0

4

1000 1000

999 998

990 992

1000 999

100 100 -2.5

Sample Output

3

4

4

Program 2： Robots (TOJ_1926)

Your company provides robots that can be used to pick up litter from fields after sporting events and concerts. Before robots are assigned to a job, an aerial photograph of the field is marked with a grid. Each location in the grid that contains garbage is marked. All robots begin in the Northwest corner and end their movement in the Southeast corner. A robot can only move in two directions, either to the East or South. Upon entering a cell that contains garbage, the robot will pick it up before proceeding. Once a robot reaches its destination at the Southeast corner it cannot be repositioned or reused. Since your expenses are directly proportional to the number of robots used for a particular job, you are interested in finding the minimum number of robots that can clean a given field. For example, consider the field map shown in Figure 1 with rows and columns numbered as shown and garbage locations marked with a 'G'. In this scheme, all robots will begin in location 1,1 and end in location 6, 7.

Figure 1 - A Field Map

Figure 2 below shows two possible solutions, the second of which is preferable since it uses two robots rather than three.

Figure 2 - Two Possible Solutions

Your task is to create a program that will determine the minimum number of robots needed to pick up all the garbage from a field.

An input file consists of one or more field maps followed by a line containing -1 -1 to signal the end of the input data. A field map consists of one or more lines, each containing one garbage location, followed by a line containing 0 0 to signal the end of the map. Each garbage location consists of two integers, the row and column, separated by a single space. The rows and columns are numbered as shown in Figure 1. The garbage locations will be given in row-major order. No single field map will have more than 24 rows and 24 columns. The sample input below shows an input file with two field maps. The first is the field map from Figure 1.

The output will consist of a single line for each field map containing the minimum number of robots needed to clean the corresponding field.

Sample Input

1 2
1 4
2 4
2 6
4 4
4 7
6 6
0 0
1 1
2 2
4 4
0 0
-1 -1

Sample Output

2
1

Program 3： A DP Problem (TOJ_1283)

In this problem, you are to solve a very easy linear equation with only one variable x with no parentheses! An example of such equations is like the following:

2x - 4 + 5x + 300 = 98x

An expression in its general form, will contain a '=' character with two expressions on its sides. Each expression is made up of one or more terms combined by '+' or '-' operators. No unary plus or minus operators are allowed in the expressions. Each term is either a single integer, or an integer followed by the lower-case character x or the single character x which is equivalent to 1x.

You are to write a program to find the value of x that satisfies the equation. Note that it is possible for the equation to have no solution or have infinitely many. Your program must detect these cases too.

Input

The first number in the input line, t (1 ≤ t ≤ 10) is the number of test cases, followed by t lines of length at most 255 each containing an equation. There is no blank character in the equations and the variable is always represented by the lower-case character x. The coefficients are integers in the range (0 ... 1000) inclusive.

Output

The output contains one line per test case containing the solution of the equation. If s is the solution to the equation, the output line should contain |_s_| (the floor of s, i.e., the largest integer number less than or equal to s). The output should be "IMPOSSIBLE" or "IDENTITY" if the equation has no solution or has infinite solutions, respectively. Note that the output is case-sensitive.

Sample Input

2

2x-4+5x+300=98x

x+2=2+x

Sample Output

3

IDENTITY

Program 4： Friends (TOJ_2469)

There are some people traveling together. Some of them are friends. The friend relation is transitive, that is, if A and B are friends, B and C are friends, then A and C will become friends too. 
     
     

These people are planning to book some rooms in the hotel. But every one of them doesn't want to live with strangers, that is, if A and D are not friends, they can't live in the same room. 
     
     

Given the information about these people, can you determine how many rooms they have to book at least? You can assume that the rooms are large enough. 
     
     

Input
      
      

The first line of the input is the number of test cases, and then some test cases followed. 
     
     

The first line of each test case contain two integers N and M, indicating the number of people and the number of the relationship between them. Each line of the following M lines contain two numbers A and B (1 ≤ A ≤ N , 1 ≤ B ≤ N , A ≠ B), indicating that A and B are friends. 
     
     

You can assume 1 ≤ N ≤ 100, 0 ≤ M ≤ N * (N-1) / 2. All the people are numbered from 1 to N. 
     
     

Output
      
      

Output one line for each test case, indicating the minimum number of rooms they have to book. 
     
     

Sample Input
      
      

3
     
     

5 3
     
     

1 2
     
     

2 3
     
     

4 5
     
     

5 4
     
     

1 2
     
     

2 3
     
     

3 4
     
     

4 5
     
     

10 0
     
     

Sample Output
      
      

2
     
     

1
     
     

10
     
     

Hint
      
      

In the first sample test case, there are 5 people. We see that 1,2,3 can live in a room, while 4,5 can live in another room. So the answer should be 2. Please note even though 1 and 3 are not "direct" friends, but they are both 2's friends, so 1 and 3 are friends too. 
     
     

In the second sample test case, there are 5 people, any two of them will become friends. So they can live in one room. 
     
     

In the third sample test case, there are 10 people and no friend relationship between them. No two people can live the same room. They have to book 10 rooms.
     
     

   
   
    
     group: C
   
   

   
   
    
      
    
    

     
     GROUP B
    
    
    
    

     
      
    
    
    
    

     
     Program 1
     
     ：
     
      Robot in Maze
     
     （
     
     TOJ_2470
     
     ）
    
    
    
    
There is a robot trapped in the maze. Now you have to send out some instructions, telling it how to reach its destination. 

    
    
The maze is an M * N grid. Some of the cells are empty, while others are occupied by the wall. Of course the robot can't move into the wall, and the robot can't move outside the grid too. The robot can only accept three commands: TURN LEFT, TURN RIGHT and GO. The robot may face to North, South, East or West during the movement. When it receive a TURN LEFT command, it will rotate 90 degree to the left. That is, if it faces to east before the command, it will face to north after the TURN LEFT command. The TURN RIGHT command is almost the same, except that the direction is opposite. When receive the GO command, the robot will move 1 unit towards its orientation, unless there is a nonempty cell in front of it. 

    
    
Please note the robot is always face to north at the beginning, i.e., face to the upper border in the maze map. (The maze map will be described below.) 

    
    
You want to use minimum number of instructions, so you should write a program for help. 

    
    
 

    
    
Input

    
    
 

    
    
The first line of the input is the number of test cases. 

    
    
The first line of each test case contains two integers M and N, indicating the size of the maze. There are M lines followed, each line contains exactly N characters, describing an M * N maze. The '#' indicating the wall, the '.' indicating the empty cell, the 'S' and 'T' indicating the start point and the destination of the robot respectively. There are no other characters in the maze map. 

    
    
The orientation of the maze map is just the same as the common sense. That is, the upper-left corner of the maze map indicating the north-west direction, and the lower-right corner indicating the south-east. 

    
    
You can assume 1 ≤ M ≤ 100 and 1 ≤ N ≤ 100. There is only one 'S' and one 'T' in the maze. 

    
    
 

    
    
Output

    
    
 

    
    
Output one line for each test case, indicating the minimum number of instructions needed. Or output -1 if it's impossible to reach the robot's destination. 

    
    
 

    
    
Sample Input

    
    
2

    
    
5 5

    
    
#####

    
    
#...#

    
    
#.#.#

    
    
#S#T#

    
    
#####

    
    
4 5

    
    
#.#.#

    
    
#.#.#

    
    
#S#T#

    
    
#####

    
    
 

    
    
Sample Output

    
    
8

    
    
-1

    
    
 

    
    
Hint

    
    
The best instruction sequence for the first sample test case should be: GO, GO, TURN RIGHT, GO, GO, TURN RIGHT, GO, GO. And the length is 8.

    
    
 

    
    

     
      
    
    

    
    

     
     Object-oriented program design
    
    

    
    

     
     This project is about how to play poker , you need to implement three class : class Card , classDeck, class Hand.
    
    

    
    

     
      
    
    

    
    

     
     1
     
     、
     
     In class Card, first you should define the kind of the cards . 
    
    

    
    

     
     enum Rank { TWO=0 , THREE , FOUR , FIVE , SIX , SEVEN , EIGHT , NINE , TEN , JACK , QUEEN , KING , ACE };
    
    

    
    

     
     enum Suit { CLUBS=0 , DIAMONDS , HEARTS , SPADES};
    
    

    
    

     
     The insertion operator << is needed to be overloaded to show the kind of the cards .
    
    

    
    

     
     friend ostream& operator << (ostream& , const Card&);
    
    

    
    

     
     2
     
     、
     
     In class Deck , first you must construct a deck which contains 52 cards . The Deck ’ s constructor initializes all 52 cards in the deck.
    
    

    
    

     
     void shuffle()
     
      is to shuffle the 52 cards randomly. 
    
    

    
    

     
     void deal(Hand& , unsigned = 5)
     
     ; The deal() function every time gets the top five cards of the deck into the hand’s cards array, then it sorts the hand.
    
    

    
    

     
     3
     
     、
     
     In class Hand , you should determine the form of every five cards in hand .
    
    

    
    

     
     void sort()
     
     ; The sort() function is called by the Deck class . It sorts five cards, and it can be implemented by any simple sort algorithm such as the Bubble Sort.
    
    

    
    

     
     void display()
     
      uses the insertion operator << that is overloaded in the 
     
     Card class to show the kind of the cards .
    
    

    
    

     
     The following functions determine the form of every five cards.
    
    

    
    

     
     int isPair()
     
     is to judge whether there has a pair cards.
    
    

    
    

     
     int isTwoPair()
     
     is to judge whether there has two pairs cards.
    
    

    
    

     
     int isThreeOfKind()
     
     is to judge whether there has three same rank cards.
    
    

    
    

     
     int isFourOfKind()
     
      is to judge whether there has four same rank cards.
    
    

    
    

     
     int isStraight()
     
      is to judge whether there has five cards like 2,3,4,5,6 or 10,J,Q,K,A and so on.
    
    

    
    

     
     int isFlush()
     
     is to judge whether there has five same suit cards.
    
    

    
    

     
     int isFullHouse()
     
     is to judge whether there has a pair and three same rank cards like 2,2,3,3,3 or J,J,Q,Q,Q and so on.
    
    

    
    

     
     int isStraightFlush()
     
     is to judge whether the five cards are straight and flush.
    
    

    
    

     
      
    
    

    
    

     
     The project is to shuffle cards randomly, every time it gets five cards from the deck to hand then sorts them and judges the form of the five cards. Finally it shows five cards and their form on the screen. Input ‘y’ from keyboard to shuffle and show again or input ‘n’ to end the program.