Problem A: Strategic Game
Execution time limit: 1 second
Bob enjoys playing computer games, especially strategic games, but sometimes he cannot find the solution fast enough and then he is very sad. Now he has the following problem. He must defend a medieval city, the roads of which form a tree. He has to put the minimum number of soldiers on the nodes so that they can observe all the edges. Can you help him?
Your program should find the minimum number of soldiers that Bob has to put for a given tree.
Input Format
The input file contains several data sets in text format. Each data set represents a tree with the following description:
- the number of nodes
- the description of each node in the following format
node_identifier:(number_of_roads) node_identifier1 node_identifier2 … node_identifiernumber_of_roads
or
node_identifier:(0)
The node identifiers are integer numbers between 0and n-1, for n nodes (0 < n <= 1500). Every edge appears only once in the input data.
For example for the tree:
0
|
1
/ \
2 3
the solution is one soldier ( at the node 1).
Output Format
The output should be printed on the standard output. For each given input data set, print one integer number in a single line that gives the result (the minimum number of soldiers).
Sample Input
4
0:(1) 1
1:(2) 2 3
2:(0)
3:(0)
5
3:(3) 1 4 2
1:(1) 0
2:(0)
0:(0)
4:(0)
Sample Output
1
2
Problem B: Regular Fractions
Execution time limit: 1 second
A fraction (m and n are not necessarily co-prime to each other) is called regular, if it can be written as a sum of fractions where’s are distinct divisors of n. Your task is
to determine whether a given fraction is regular.
Input Format
The first line has a number N (0 < N < 50) telling the number of test cases, followed by N lines each ofwhich has two integers m (0 < m < 20000) and n (0 < n < 20000000) separated by space. Also one can assume that number of divisors of n is less than 70.
Output Format
The output should have one line corresponding to each test case saying YES or NO depending on the case whether is regular or not.
Sample Input
3
3 4
5 9
29 50
Sample Output
YES
NO
NO
Problem C: Coloring Problem
Execution time limit: 1 second
A well known theorem in graph theory says that any planar map can be colored with
four colors such that neighboring regions (regions sharing an edge) do not share the
same color. However, it is not always necessary to use four colors and in many maps fewer colors suffice. One such example is the region constructed by circles in a plane where only two colors are needed to color the whole region. A few examples of such regions are shown in the picture below.
The task is to find out whether in a given region two specified points will get the same color.
Input Format
The first line has a number N (0 < N < 10) telling the number of test cases, followed by the description of the N test cases. The description of each test case goes like this: first line contains an integer n (0 < n < 10000) indicating the number of circles of region, followed by n lines each of which contains three float values x, y, r (i.e., describing a circle with center (x, y) and radius r). Next line contains an integer m (0 < m < 150), which denotes the number of pairs of points whose relative colors we want to know. Each of the next lines contain four float values x1, y1, x2, y2 which denote the positions of the two points (x1, y1) and (x2, y2). One can assume that none of the specified points lie on the boundary of a circle.
Output Format
The output should have m lines corresponding to each test case saying SAME or DIFFERENT depending on whether the two points have same color or different color.
Sample Input
2
3
0 0 2
0 1 2
1 0 2
2
0 0 2 3
0 0 0 0.5
1
0 0 5
1
0 1 10 10
Sample Output
DIFFERENT
SAME
DIFFERENT
Problem D: Lattice Points
Execution time limit: 1 second
A lattice point is a point whose both co-ordinates are integers. In this problem your task is to count the number of lattice points inside a square.
Input Format
The first line contains an integer N (0 < N < 200) denoting the number of test cases. Each
of the next N lines contains 4 integers x1, y1, x2, y2 denoting the co-ordinates of two consecutive vertices of the square.
Output Format
The output should have N lines corresponding to each test case telling the number of lattice points inside or on the square.
Sample Input
1
0 0 2 0
Sample Output
9
Problem E: Inversions
Execution time limit: 1 second
Let a1 , a2 , …. an be a sequence of n distinct integer numbers. If i j and ai > aj then the pair (i, j) is called an inversion. For example, the sequence 3, 2, 1, 5, 6, 7, 8, 9 has 3 inversions, whereas the sequence 1, 2, 3, 4 has no inversion.
Write a program that prints the number of inversions in the sequence for each sequence of numbers from the text file.
Input Format
A text file contains non empty sequences of integers. Each sequence starts with a number
that specifies the number of integers in the sequence. This number is not part of the sequence. The numbers are separated freely by white-spaces (spaces, tabs and line breaks). The data in the text file are guaranteed correct.
Output Format
Each result is printed on separate line.
Sample Input
5
1 2 3 4 5
4
4 3 2 1
1
1000
Sample Output
0
6
0
Problem F: Call Routing
Execution time limit: 4 seconds
SwissCom has decided to implement a new architecture for providing telephone services in remote hilly areas. The new architecture is based on their new invention of a small hub which can be connected to the instrument of each telephone subscriber. This hub is used to relay information from one phone to another until it reaches the destination. Hub has a multiple input-multiple output format so that many calls can be transmitted at the same time and the subscriber will always find his own hub free whenever he wishes to place a phone call. So, rather then all the calls going through a central office, in this architecture phone call follow the relay architecture using interconnected phones (or hubs) thus reducing the investment in setting up a telephone exchange in hilly areas where the number of subscribers are few to give return on investment. The quality of call though degrades with the increasing number of hubs in the call route from source to destination. With its strong history in providing best quality, SwissCon would like to minimize the degradation in quality for each phone call. For this they have hired you to write the software which can route the call from the source to destination such that the number of intermediate hubs in this route is minimized. Also assume that the hubs can transmit any number of calls and never go busy.
Input Format
First line gives the number of subscribers, say N ( 1N105). Each subscriber is labeled from 0 to N-1. Following N lines gives the subscriber label followed by the number of subscribers he/she is connected, followed by their labels. All the integers are separated by a single blank. Last line gives the label of the source of a phone call followed by the label of the destination.
Output Format
Your program should output three integers separated by a blank: source label, destination label and the minimum number of intermediate hubs to reach destination
Sample Input
7
0 3 1 5 6
1 2 0 4
2 2 3 6
3 2 2 4
4 2 1 3
5 2 0 6
6 3 0 2 5
1 2
Sample Output
1 2 2
Problem G: The Path
Execution time limit: 10 seconds
``PATH" is a game played by two players on an N by N board, where N is a positive integer. (If N = 8, the board looks like a chess board.) Two players ``WHITE" and ``BLACK" compete in the game to build a path of pieces played on the board from the player's ``home" edge to the player's ``target" edge, opposite the home edge. WHITE uses white pieces and BLACK uses black pieces.
For this problem you will play the ``referee" for the game, analyzing boards containing black and white pieces to determine whether either of the players has won the game or if one of the players can win by placing one of their pieces in an unfilled position. WHITE's turn is next.
A representation of a board on paper (and in a computer) is an N x N matrix of characters 'W', 'B', and 'U'; where W represents white pieces, B represents black pieces, and 'U' represents unfilled positions on the board.
When we view a matrix representation of the board on paper, WHITE's home edge is the left edge of the board (the first column), and WHITE's target edge is the right edge (the last column). BLACK's home edge is the top edge of the board (the first row), and BLACK's target edge is the bottom edge (the last row). Thus WHITE wants to build a path from left to right, and BLACK wants to build a path from top to bottom.
Two locations on the board are ``adjacent" if one is immediately to the left, to the right above, or below the other. Thus an interior location on the board is adjacent to four other locations. For N > 1, corner locations each have two adjacent locations, and for N > 2, other border locations have three adjacent locations.
A path is a sequence of distinct positions on the board, such that each pair Li and Li+1 are adjacent for . A winning path for a player is a path filled with the player's pieces such that L0 is a position on the player's home edge and Lk is a position on the player's target edge. It is clear that if one player has a winning path then the other player is blocked from having a winning path. Thus if all the squares contain pieces, either there are no winning paths or exactly one of the players has at least one winning path.
InputFormat
Input is a series of game board data sets. Each set begins with a line containing an integer specifying the size N, 0<N<81 of the () game board. This is followed by a blank line and then by N lines, one for each row of the game board, from the top row to the bottom row. Each line begins with character and consists of N adjacent characters from the set `B', `W', `U'. A blank line separates each non-zero data set from the following data set. The input is terminated by a single line containing a board size of zero.
OutputFormat
As referee, for each game board in a series of game boards your program should report one of the five types of answers below:
White has a winning path.
Black has a winning path.
White can win in one move. (White can place a piece in an unfilled position)
Black can win in one move. (White can't win in one move AND Black can if White does't move)
There is no winning path.
Sample Input
7
WBBUUUU
WWBUWWW
UWBBBWB
BWBBWWB
BWWBWBB
UBWWWBU
UWBBBWW
3
WBB
WWU
WBB
0
Sample Output
White has a winning path.
White can win in one move.