Odd and even
Let us consider a country with N towns. A system of roads formed from direct connections between towns is given; all these direct connections are considered to have the length equal to 1. This system is called even-odd if there are two towns linked by a road of even length, as well as by a road of odd length.
a) Find out if the system of roads is even-odd or not.
b) If the answer for a) is negative, find one of the subsets X of towns which has a maximal number of elements and satisfies the following condition: for any two towns in X, if there is a path linking them, then its length is even.
The name of the input file is introduced from the keyboard. Its first line contains the value of N; the following lines contain pairs I,J with the meaning that the towns I and J are directly linked.
The value of N is at most 300. It can be assumed that every town can be reached from every other town.
Display the output on the screen in an intelligible form.
Examples:
If the input file contains
5
1 2
2 3
3 4
4 5
5 1
If the input file contains:
4
1 2
3 1
1 4
a valid output is
YES
then a valid output is:
NO
X: 2 3 4
Enlightened landscape\
Consider a landscape composed of connected line segments:
!Above the landscape, N light bulbs are hang at the same height T in various horizontal positions. The purpose of these light bulbs is to light up the entire landscape. A landscape point is considered lit if it can “see” a light bulb directly, that is, if the line segment which links the point with a bulb does not contain any other landscape segments point.\
Task
Write a program that determines the mi-ni-mum number of light bulbs that must be switched on in order to illuminate the entire landscape.\
Input
Input file name: LIGHT.IN
Line 1: M
An integer, the number of landscape height specifications, including the first and the last point of the landscape.
Lines 2..M+1: X_(i) H_(i)
Two integers, separated by a space: the landscape height H_(i) at horizontal position X_(i), 1 <= i <= M; for 1 <= i <= M-1 we have X_(i+1) > X_(i); any two consecutive specified points identify a segment of line in the landscape.
Line M+2: N T
Two integers, separated by a space, the num-ber of light bulbs and their height coordinate (altitude). The bulbs are numbered from 1 to N)
Line M+3: B₁ B₂ … B_(N)
N integers, separated by spaces: the hori-zon-tal coordinates of the light bulbs Bi+1 > Bi, 1 <= i <=N-1;\
Output
File name: LIGHT.OUT
Line 1: K
An integer: the minimum number of light bulbs to be switched on.
Line 2: L₁ L₂ … L_(K)
K integers, separated by spaces: the labels of the light bulbs to be switched on spe-cified in increasing order of their horizontal coordinates.\
Limits
1 <= M <= 200
1 <= N <= 200
1 <= X_(i) <= 10000 for 1 <= i <= M
1 < T <= 10000
1 <= H_(i) <= 10000 for 1 <= i <= M
T > H_(i) for any 1 <= i <= M
X₁ <= B₁ and B_(N) <= X _(M)
The task always has a solution for the test data. If there are multiple solutions, only one is required.\
Example
LIGHT.IN LIGHT.OUT
6 2
1 1 1 4
3 3
4 1
7 1
8 3
11 1
4 5
1 5 6 10
You are given a rectangle whose side lengths are integer numbers. You want to cut the rectangle into the smallest number of squares, whose side lengths are also integer numbers. Cutting can be performed with a cutting machine that can cut only from side to side across, parallel with one side of the rectangle. Obtained rectangles are cut separately.
The input file contains two positive integers in the first line: the lengths of the sides of the rectangle. Each side of the rectangle is at least 1 and at most 100.
The output file consist of one line on which your program should write the number of squares resulting from an optimal cutting.
CUTS.IN
5 6
CUTS.OUT
5
(file name: pig.c, pig.p, pig.C)
Before ACM can do anything, a budget must be prepared and the necessary financial support obtained. The main income for this action comes from Irreversibly Bound Money (IBM). The idea behind is simple. Whenever some ACM member has any small money, he takes all the coins and throws them into a piggy-bank. You know that this process is irreversible, the coins cannot be removed without breaking the pig. After a sufficiently long time, there should be enough cash in the piggy-bank to pay everything that needs to be paid.
But there is a big problem with piggy-banks. It is not possible to determine how much money is inside. So we might break the pig into pieces only to find out that there is not enough money. Clearly, we want to avoid this unpleasant situation. The only possibility is to weigh the piggy-bank and try to guess how many coins are inside. Assume that we are able to determine the weight of the pig exactly and that we know the weights of all coins of a given currency. Then there is some minimum amount of money in the piggy-bank that we can guarantee. Your task is to find out this worst case and determine the minimum amount of cash inside the piggy-bank. We need your help. No more prematurely broken pigs!
The input consists of T test cases. The number of them (T) is given on the first line of the input file. Each test case begins with a line containing two integers E and ` F. They indicate the weight of an empty pig and of the pig filled with coins. Both weights are given in grams. No pig will weigh more than 10 kg, that means 1 <= E <= F <= 10000. On the second line of each test case, there is an integer number N (1 <= N <= 500) that gives the number of various coins used in the given currency. Following this are exactly N lines, each specifying one coin type. These lines contain two integers each, Pand W ( 1 <= P <= 50000, 1 <= W <=10000). P is the value of the coin in monetary units, W` is it’s weight in grams.
Print exactly one line of output for each test case. The line must contain the sentence “The minimum amount of money in the piggy-bank is X.” where X is the minimum amount of money that can be achieved using coins with the given total weight. If the weight cannot be reached exactly, print a line “This is impossible.”.
3
10 110
2
1 1
30 50
10 110
2
1 1
50 30
1 6
2
10 3
20 4
The minimum amount of money in the piggy-bank is 60.
The minimum amount of money in the piggy-bank is 100.
This is impossible.
All the inhabitants of the planet X build their houses in a triangular shape. In order to save time and effort, they use a special construction method. Everything starts with a straight wall. After that, for the construction of every new house they just add two new walls to an already existing wall, thus resul-ting in a closed, triangular shaped house. Of course, the two new added walls might also be used as starting walls for new houses. Sometimes, using this con-struc-tion pattern, they arrive at situations where some houses are completely enclosed in others (like in the figure). However, this is not a problem, because kids might live in the included houses.
To light up their houses, the X-habitants install a light bulb on every corner of the final construction (a bulb in a corner is common to all the houses sharing that corner). On each corner, there is a switch whose touch toggles the state (on/off) of the bulb from both that corner and also that of all the bulbs of the connected corners. Two corners are considered connected if they are placed at the end of the same wall.\
Task
Write a program that finds a switch touch sequence that will turn on all the light bulbs, starting from a given state.\
Input
File name: X.IN\
Line 1: N
an integer, the number of corners of the building, labelled from 1 to N;
Lines 2..2xN - 2: I J
Two integers, separated by a blank, representing a wall between the corners I and J;
Line 2xN - 1: S₁ S₂ … S _(N)
N integers (separated by blanks) whose values are 0’s or 1’s, corresponding to the state of the N light bulbs;
0 means off; 1 means on.\
The input data are guaranteed to represent a building that can be constructed in the specified pattern.\
Output
File name: X.OUT
Line 1: L₁ L₂ … L_(K)
K integers, separated by blanks, represen-ting the list of the labels of the switches to be touched.
If there are several solutions, only one is required.
If there is no possible solution, you should write in the output file a single line containing the number 0.
Limits
3 <= N <= 1000
Example
X.IN X.OUT
6 1 6
1 3
1 4
1 5
2 3
2 4
3 4
3 6
4 5
4 6
0 1 1 1 0 0
In the figure below you can see a possible building steps for the example file; the labels for the bulbs initially illuminated are underlined.
!
inputfile: G.IN
outputfile: G.OUT
Nieuw Knollendam is a very modern town. This becomes clear already when looking at the layout of its map, which is just a rectangular grid of streets and avenues. Being an important trade centre, Nieuw Knollendam also has a lot of banks. Almost on every crossing a bank is found (although there are never two banks at the same crossing). Unfortunately this has attracted a lot of criminals. Bank hold-ups are quite common, and often on one day several banks are robbed. This has grown into a problem, not only to the banks, but to the criminals as well. After robbing a bank the robber tries to leave the town as soon as possible, most of the times chased at high speed by the police. Sometimes two running criminals pass the same crossing, causing several risks: collisions, crowds of police at one place and a larger risk to be caught. To prevent these unpleasant situations the robbers agreed to consult together. Every Saturday night they meet and make a schedule for the week to come: who is going to rob which bank on which day? For every day they try to plan the get-away routes, such that no two routes use the same crossing. Sometimes they do not succeed in planning the routes according to this condition, although they believe that such a planning should exist.
Given a grid of (s ( a) and the crossings where the banks to be robbed are located, find out whether or not it is possible to plan a get-away route from every robbed bank to the city-bounds, without using a crossing more than once.
The first line of the input contains the number of problems p to be solved. The first line of every problem contains the number s of streets (1 <= s <= 50) , followed by the number a of avenues (1 <= a <= 50) , followed by the number b (b >= 1) of banks to be robbed. Then b lines follow, each containing the location of a bank in the form of two numbers x (the number of the street) and y (the number of the avenue). Evidently 1 <= x <= s and 1 <= y <= a .
The output file consists of p lines. Each line contains the text
possible
or
not possible
. If it is possible to plan non-crossing get-away routes, this line should contain the word:
possible
. If this is not possible, the line should contain the words
not possible
.
2
6 6 10
4 1
3 2
4 2
5 2
3 4
4 4
5 4
3 6
4 6
5 6
5 5 5
3 2
2 3
3 3
4 3
3 4
possible
not possible
!
(file name:words.c, words.p, words.C )
Some of the secret doors contain a very interesting word puzzle. The team of archaeologists has to solve it to open that doors. Because there is no other way to open the doors, the puzzle is very important for us.
There is a large number of magnetic plates on every door. Every plate has one word written on it. The plates must be arranged into a sequence in such a way that every word begins with the same letter as the previous word ends. For example, the word ``acm’’ can be followed by the word ``motorola’’. Your task is to write a computer program that will read the list of words and determine whether it is possible to arrange all of the plates in a sequence (according to the given rule) and consequently to open the door.
The input consists of T test cases. The number of them ( T) is given on the first line of the input file. Each test case begins with a line containing a single integer number Nthat indicates the number of plates (1 <= N <= 100000). Then exactly ` Nlines follow, each containing a single word. Each word contains at least two and at most 1000 lowercase characters, that means only letters 'a' through 'z`’ will appear in the word. The same word may appear several times in the list.
Your program has to determine whether it is possible to arrange all the plates in a sequence such that the first letter of each word is equal to the last letter of the previous word. All the plates from the list must be used, each exactly once. The words mentioned several times must be used that number of times.
If there exists such an ordering of plates, your program should print the sentence “Ordering is possible.”. Otherwise, output the sentence “The door cannot be opened.”.
3
2
acm
ibm
3
acm
malform
mouse
2
ok
ok
The door cannot be opened.
Ordering is possible.
The door cannot be opened.
Bicycle messengers who deliver documents and small items to businesses have long been part of the guerrilla transportation services in several major U.S. cities. The cyclists of Boston are a rare breed of riders. They are notorious for their speed, their disrespect for one-way streets and traffic signals, and their brazen disregard for cars, taxis, buses, and pedestrians.
Bicycle messenger services are very competitive. Billy’s Bicycle Messenger Service is no exception. To boost its competitive edge and to determine its actual expenses, BBMS is developing a new scheme for pricing deliveries that depends on the shortest route messengers can travel. You are to write a program to help BBMS determine the distances for these routes.
The following assumptions help simplify your task:
Your program must be able to process several scenarios. Each scenario defines the buildings and the starting and stopping points for a delivery route. The picture below shows a bird’s-eye view of a typical scenario.
!The input file represents several scenarios. Input for each scenario consists of lines as follows:
First line: n
The number of rectangles describing the buildings in the scenario. 0 <= n <= 20
Second line: x₁ y₁ x₂ y₂
The x- and y-coordinates of the starting and stopping points of the route.
Remaining n lines: x₁ y₁ x₂ y₂ x₃ y₃
The x- and y-coordinates of three vertices of a rectangle.
The x- and y-coordinates of all input data are real numbers between 0 and 1000 inclusive. Successive coordinates on a line are separated by one or more blanks. The integer -1 follows the data of the last scenario.
Output should number each scenario (Scenario #1, Scenario #2, etc.) and give the distance of the shortest route from starting to stopping point as illustrated in the Sample Output below. The distance should be written with two digits to the right of the decimal point. Output for successive scenarios should be separated by blank lines.
Sample Input
5
6.5 9 10 3
1 5 3 3 6 6
5.25 2 8 2 8 3.5\
6 10 6 12 9 12\
7 6 11 6 11 8\
10 7 11 7 11 11\
-1
Sample Output
Scenario #1
route distance: 7.28
Source file: intersection.c / intersection.p
Input file: intersection.in
Output file: intersection.out\
You are to write a program that has to decide whether a given line segment intersects a given rectangle.
line: start point: (4,9)
end point: (11,2)
rectangle: left-top: (1,5)
right-bottom: (7,1)\
!\
Figure 1: Line segment does not intersect rectangle\
The line is said to intersect the rectangle if the line and the rectangle have at least one point in common. The rectangle consists of four straight lines and the area in between. Although all input values are integer numbers, valid intersection points do not have to lay on the integer grid.
The input consists of n test cases. The first line of the input file contains the number n. Each following line contains one test case of the format: xstart ystart xend yend xleft ytop xright ybottom where (xstart, ystart) is the start and (xend, yend) the end point of the line and (xleft, ytop) the top left and (xright, ybottom) the bottom right corner of the rectangle. The eight numbers are separated by a blank. The terms top left and bottom right do not imply any ordering of coordinates.
For each test case in the input file, the output file should contain a line consisting either of the letter “T” if the line segment intersects the rectangle or the letter “F” if the line segment does not intersect the rectangle.
1
4 9 11 2 1 5 7 1
F
(file name: stone.c, stone.p, stone.C )
There are many secret openings in the floor which are covered by a big heavy stone. When the stone is lifted up, a special mechanism detects this and activates poisoned arrows that are shot near the opening. The only possibility is to lift the stone very slowly and carefully. The ACM team must connect a rope to the stone and then lift it using a pulley. Moreover, the stone must be lifted all at once; no side can rise before another. So it is very important to find the centre of gravity and connect the rope exactly to that point. The stone has a polygonal shape and its height is the same throughout the whole polygonal area. Your task is to find the centre of gravity for the given polygon.
The input consists of T test cases. The number of them ( T) is given on the first line of the input file. Each test case begins with a line containing a single integer N (3 <= N <= 1000000) indicating the number of points that form the polygon. This is followed by N lines, each containing two integers X (i) and Y(i) (|X(i)|, |Y (i)| <= 20000). These numbers are the coordinates of the ` i`-th point. When we connect the points in the given order, we get a polygon. You may assume that the edges never touch each other (except the neighbouring ones) and that they never cross. The area of the polygon is never zero, i.e. it cannot collapse into a single line.
Print exactly one line for each test case. The line should contain exactly two numbers separated by one space. These numbers are the coordinates of the centre of gravity. Round the coordinates to the nearest number with exactly two digits after the decimal point (0.005 rounds up to 0.01). Note that the centre of gravity may be outside the polygon, if its shape is not convex. If there is such a case in the input data, print the centre anyway.
2
4
5 0
0 5
-5 0
0 -5
4
1 1
11 1
11 11
1 11
0.00 0.00
6.00 6.00
(file name: cipher.c, cipher.p, cipher.C )
Antique Comedians of Malidinesia would like to play a new discovered comedy of Aristofanes. Putting it on a stage should be a big surprise for the audience so all the preparations must be kept absolutely secret. The ACM director suspects one of his competitors of reading his correspondece. To prevent other companies from revealing his secret, he decided to use a substitution cipher in all the letters mentioning the new play.
Substitution cipher is defined by a substitution table assigning each character of the substitution alphabet another character of the same alphabet. The assignment is a bijection (to each character exactly one character is assigned – not neccessary different). The director is afraid of disclosing the substitution table and therefore he changes it frequently. After each change he chooses a few words from a dictionary by random, encrypts them and sends them together with an encrypted message. The plain (i.e. non-encrypted) words are sent by a secure channel, not by mail. The recipient of the message can then compare plain and encrypted words and create a new substitution table.
Unfortunately, one of the ACM cipher specialists have found that this system is sometimes insecure. Some messages can be decrypted by the rival company even without knowing the plain words. The reason is that when the director chooses the words from the dictionary and encrypts them, he never changes their order (the words in the dictionary are lexicographically sorted). String $a_{1}a_{2} … a_{p}$ is lexicografically smaller than $b_{1}b_{2} … b_{q}$ if there exists an integer $i$, $i \le p, i \le q$, such that $a_{j}=b_{j}$ for each $j, 1 \le j < i$ and $a_{i} < b_{i}$.
The director is interested in which of his messages could be read by the rival company. You are to write a program to determine that.
The input consists of $N$ cases. The first line of the input contains only positive integer $N$. Then follow the cases. The first line of each case contains only two positive integers $A$, $1 \le A \le 26$, and $K$, separated by space. $A$ determines the size of the substitution alphabet (the substitution alphabet consists of the first $A$ lowercase letters of the english alphabet (a–z) and $K$ is the number of encrypted words. The plain words contain only the letters of the substitution alphabet. The plain message can contain any symbol, but only the letters of the substitution alphabet are encrypted. Then follow $K$ lines, each containing exactly one encrypted word. At the next line is encrypted message.
For each case, print exactly one line. If it is possible to decrypt the message uniquely, print the decrypted message. Otherwise, print the sentence ‘Message cannot be decrypted.’.
2
5 6
cebdbac
cac
ecd
dca
aba
bac
cedab
4 4
cca
cad
aac
bca
bdac
abcde
Message cannot be decrypted.