Johnny and his friends have decided to spend Halloween night doing the usual candy collection from the households of their village. As the village is too big for a single group to collect the candy from all houses sequentially, Johnny and his friends have decided to split up so that each of them goes to a different house, collects the candy (or wreaks havoc if the residents don't give out candy), and returns to a meeting point arranged in advance.
There are $$$n$$$ houses in the village, the positions of which can be identified with their Cartesian coordinates on the Euclidean plane. Johnny's gang is also made up of n people (including Johnny himself). They have decided to distribute the candy after everybody comes back with their booty. The houses might be far away, but Johnny's interest is in eating the candy as soon as possible.
Keeping in mind that, because of their response to the hospitality of some villagers, some children might be wanted by the local authorities, they have agreed to fix the meeting point by the river running through the village, which is the line $$$y = 0$$$. Note that there may be houses on both sides of the river, and some of the houses may be houseboats ($$$y = 0$$$). The walking speed of every child is $$$1$$$ meter per second, and they can move along any direction on the plane.
At exactly midnight, each child will knock on the door of the house he has chosen, collect the candy instantaneously, and walk back along the shortest route to the meeting point. Tell Johnny at what time he will be able to start eating the candy.
Each test case starts with a line indicating the number $$$n$$$ of houses ($$$1 \le n \le 50 000$$$). The next $$$n$$$ lines describe the positions of the houses; each of these lines contains two floating point numbers $$$x$$$ and $$$y$$$ ($$$-200 000 \le x, y \le 200 000$$$), the coordinates of a house in meters. All houses are at different positions.
A blank line follows each case. A line with $$$n = 0$$$ indicates the end of the input; do not write any output for this case.
For each test case, print two numbers in a line separated by a space: the coordinate $$$x$$$ of the meeting point on the line $$$y = 0$$$ that minimizes the time the last child arrives, and this time itself (measured in seconds after midnight). Your answer should be accurate to within an absolute or relative error of $$$10^{-5}$$$.
2 1.5 1.5 3 0 1 0 0 4 1 4 4 4 -3 3 2 4 5 4 7 -4 0 7 -6 -2 4 8 -5 0
1.500000000 1.500000000 0.000000000 0.000000000 1.000000000 5.000000000 3.136363636 7.136363636
Last night, Tom went on a date with a really nice girl. However, he forgot to take his credit card with him and he had no cash in his wallet, so he ended up working at the restaurant to pay for the bill. His task is to take plates from the waiter when he comes from the tables, and pass them along when the diswasher requests them. It is very important for the plates to be washed in the same order as they are brought from the tables, as otherwise it could take too long before a plate is washed, and leftover food might get stuck. Trying to hold all the plates in his hands is probably not a great idea, so Tom puts them on a table as soon as the waiter hands them over to him, and picks them up from the table again when the time comes to pass them along to the dishwasher. There is space for only two piles of plates on the table, which will be referred to as pile 1 and pile 2. There is only one table Tom can use.
Tom won last year's SWERC, so he is certainly capable of optimizing for efficiency. You have to output a transcript of one possible way in which Tom might decide to organize the plates on the table during the process, given the sequence of plates and requests he receives.
The input has several test cases. Each case begins with a line containing a number $$$N$$$ ($$$1 \le N \le 1 000$$$), followed by $$$N$$$ lines, which contain either DROP $$$m$$$ or TAKE $$$m$$$, where $$$m \gt 0$$$ is the number of plates to take or drop. DROP $$$m$$$ represents that the next event is the waiter bringing $$$m$$$ plates to Tom, so he has to drop them on the table, while TAKE $$$m$$$ represents that the next event is Tom taking $$$m$$$ plates from the table and passing them along in the right order. You can assume that he never receives a TAKE $$$m$$$ instruction when there are fewer than $$$m$$$ plates on the table, and that the sum $$$M$$$ of all values of $$$m$$$ corresponding to DROP operations does not exceed 100 000. Note that there might be plates left on Tom's table when the last request is issued, as Tom might be relieved of his duty to stay until the restaurant closes.
The input ends with a line with $$$N = 0$$$, which must not be processed.
For every test case, the output will be a series of lines describing the operations to be performed with the plates. The content of each line will be one of the following:
Note that Tom must obey the commands in the same order as they are issued. This means that, if he receives a TAKE m command, he must perform a certain number of MOVE and TAKE operations such that the sum of the numbers of plates taken adds up exactly to m before performing the operations corresponding to the next command; and if he receives a DROP m command, he must perform a number of DROP or MOVE operations for which the sum of the numbers of plates dropped adds up exactly to m before performing the operations corresponding to the next command.
Of course, it is also forbidden to take plates from the waiter or pass them along to the dishwasher in the absence of the corresponding order.
There must be an empty line between the outputs of different cases.
Any solution satisfying these conditions will be accepted.
3 DROP 100 TAKE 50 TAKE 20 3 DROP 3 DROP 5 TAKE 8 0
DROP 2 100 MOVE 2->1 100 TAKE 1 50 TAKE 1 20 DROP 2 3 DROP 2 5 MOVE 2->1 8 TAKE 1 8
John has n light bulbs and a switchboard with n switches; each bulb can be either on or off, and pressing the $$$i$$$-th switch changes the state of bulb $$$i$$$ from on to off, and vice-versa. He is using them to play a game he has made up. In each move, John selects a (possibly empty) set of switches and presses them, thus inverting the states of the corresponding bulbs. After exactly m moves, John would like to have the first v bulbs on and the rest off; otherwise he loses the game. There is only one restriction: he is not allowed to press the same set of switches in two different moves.
This is quite an easy game, as there are lots of ways of winning. This has encouraged him to keep playing different winning games, and now he is intent on trying them all. Help him count how many ways of winning there are. Two games are considered the same if, after reordering the moves in one of them, at every step, the same set of switches is pressed in both of them.
For example, if $$$n = 4$$$, $$$m = 3$$$, and $$$v = 2$$$, one possible winning game is obtained by pressing switches 1, 2 and 4 in the first move, 1 and 3 in the second one, and 1, 3 and 4 in the last one. This is considered equivalent to, say, first pressing 1 and 3; then 1, 2, 4; and then 1, 3, 4.
The input has at most $$$500$$$ lines, one for each test case. Each line contains three integers $$$n$$$ ($$$1 \le n \le 1000$$$), $$$m$$$ ($$$1 \le m \le 1000$$$), and $$$v$$$ ($$$0 \le v \le n$$$). The last line of input will hold the values 0 0 0 and must not be processed.
Print one line for each test case containing the number of ways John can play the game, modulo the prime $$$10567201$$$.
3 3 1 6 4 0 6 4 3 0 0 0
7 10416 9920
After a long week of work at the ICPC Headquarters, Bill and his friends usually go to a small pub on Friday evenings to have a couple of beers and play darts. All of them are well aware of the fact that their ability at darts decreases at the same rate as the amount of beer left in their mugs.
They always play $$$501$$$, one of the easiest games. Players start with a score of $$$N$$$ points (typically, $$$N = 501$$$, hence the name) and take turns throwing darts. The score of each player decreases by the value of the section hit by the dart, unless the score becomes negative, in which case it remains unchanged. The first player to reach a score of $$$0$$$ wins. The figure below shows the dartboard with which the game is played.
Figure 1: Dartboard The input consists of a series of lines, each containing an integer $$$N$$$ ($$$1 \le N \le 501$$$), the initial score of both players. A case with $$$N = 0$$$ marks the end of the input and must not be processed.
For each number in the input, your program should output a line containing two real numbers: the probability that $$$A$$$ wins if $$$A$$$ throws the first dart, and the probability that $$$B$$$ wins if $$$B$$$ throws the first dart. Your answers should be accurate to within an absolute or relative error of $$$10^{-8}$$$.
5 100 0
0.136363636364 0.909090909091 0.072504908290 0.950215081962
A colony of alien bacteria has recently been discovered close to a crater in New Mexico. Dr. Poucher is in charge of the scientific team at the ICPC BioLab committed to the study of the alien DNA structure. We briefly sketch their discoveries here.
Alien DNA molecules have the structure of a circular sequence. Each sequence is composed of nucleotides. There are 26 different types of nucleotides, and each of them can occur in two faces. It is very important to remark that in any given alien DNA molecule, every nucleotide either does not appear at all or appears exactly twice (hence, the length of a DNA molecule is an even integer between 2 and 52). In case a nucleotide occurs twice, each occurrence can be of either type independently. Alien bacteria have two types of extremities, which in the technical biological jargon are referred to as arms and legs. A major discovery of Dr. Poucher's team is a method to determine the exact number of arms and legs of a bacterium by examining its DNA structure.
Here we represent each nucleotide as a letter of the alphabet. We refer to the different nucleotides as $$$a, A, \ldots, z, Z$$$, where the lowercase and uppercase forms of a letter represent the two possible faces a nucleotide may appear with; we shall also use $$$a/A, b/B, \ldots, z/Z$$$ to refer to a nucleotide in either face.
To determine the number of extremities, Dr. Poucher starts by initializing two counters of arms and legs to zero, and then proceeds to perform a number of surgeries, transforming a DNA sequence into another one. After each transformation, you may need to increase some of the counters, depending on the type of surgery applied. When the empty sequence of nucleotides (which will be denoted by $$$\emptyset$$$) has been reached, the number of extremities of the original molecule has been found. The possible surgeries are:
Second, if both occurrences of $$$a/A$$$ are of the same face, one of the chains is "inverted" by reversing the sequence and changing the face of every nucleotide in the chain.
Then, the chains are combined by concatenating the subsequence occurring before a with the subsequence occurring after $$$A$$$, and the subsequence occurring after a with the subsequence occurring before $$$A$$$.
Finally, two new $$$a/A$$$ nucleotides are added to close the chain into a circular shape. The face of the new nucleotides is the same if the original pair of nucleotides selected had the same face, and is different otherwise.
Formally, suppose you select the nucleotide $$$a/A$$$, and further assume for the moment that it appears both times with the face $$$a$$$ ($$$A$$$). The cut and paste surgery turns sequences of the form $$$S_1aS_2S_3aS_4$$$ (respectively $$$S_1AS_2S_3AS_4$$$) into $$$S2aS_1\overline{S_3}a\overline{S_4}$$$ (respectively $$$S_2AS_1\overline{S_3}A\overline{S_4}$$$). On the other hand, if nucleotide $$$a/A$$$ appears with its two different faces, the surgery turns sequences of the form $$$S_1aS_2S_3AS_4$$$ into $$$S_2aS_1S_4AS_3$$$. $$$S_1$$$, $$$S_2$$$, $$$S_3$$$ and $$$S_4$$$ are arbitrary sub-chains (possibly empty). In both cases, the original circular chain was chopped into $$$S_1(a/A)S_2$$$ and $$$S_3(a/A)S_4$$$ .
For example (see the figure below): starting with the sequence $$$BacDcAbD$$$, we can get chains $$$BacDc$$$ and $$$AbD$$$. Then, merging at nucleotide $$$a/A$$$ we get the sequence $$$cDca'BbDA'$$$ where $$$a'$$$ and $$$A'$$$ represents the new $$$a/A$$$ nucleotides. Here, $$$S_1 = B$$$, $$$S_2 = cDc$$$, $$$S_3 = \emptyset$$$ and $$$S_4 = bD$$$.
Another example: take the same DNA sequence $$$BacDcAbD$$$, and cut to get the chains $$$DBac$$$ and $$$DcAb$$$; paste nucleotide $$$c/C$$$ (in this case you need to reverse one chain, for example $$$BaCd$$$) to get the sequence $$$cDBadcBa$$$. Here, $$$S_1 = DBa$$$, $$$S2 = \emptyset$$$, $$$S3 = D$$$ and $$$S_4 = Ab$$$.
Figure: First example of cut& paste However, alien bacteria do not present both arms and legs at the same time. This is due to the fact that, in their early development, a leg, in the presence of one or more arms, becomes two arms. Because of the above, the end result is either a number of arms or a number of legs, but not both at the same time. In order to avoid expensive surgical procedures, Dr. Poucher has hired you to write a program that computes the number of arms and legs a bacterium will develop, given its DNA sequence. It is guaranteed that the result is determined uniquely by the original string, regardless of the particular sequence of surgeries applied.
Each test case consists of a string of even length between 2 and 52, inclusive, representing the DNA structure of an alien bacterium. All the characters are letters. There will be one case per line in the input. The last line contains the word "END" and must not be processed.
The output for each test case should have exactly one line, containing the number of arms or legs the bacterium will have, followed by the word "arms" or "legs" respectively (if the number is 1, the words should be in singular). In case there will be neither arms nor legs, the program should print the word "none".
rkrk abcdeABCDE shcoOCfFHS END
1 arm 2 legs none
Tonight is Halloween and Scared John and his friends have decided to do something fun to celebrate the occasion: crossing the graveyard. Although Scared John does not find this fun at all, he finally agreed to join them in their adventure. Once at the entrance, the friends have begun to cross the graveyard one by one, and now it is the time for Scared John. He still remembers the tales his grandmother told him when he was a child. She told him that, on Halloween night, "haunted holes" appear in the graveyard. These are not usual holes, but they transport people who fall inside to some point in the graveyard, possibly far away. But the scariest feature of these holes is that they allow one to travel in time as well as in space; i.e., if you fall inside a "haunted hole", you appear somewhere in the graveyard a certain time before (or after) you entered the hole, in a parallel universe otherwise identical to ours.
The graveyard is organized as a grid of $$$W \times H$$$ cells, with the entrance in the cell at position $$$(0, 0)$$$ and the exit at $$$(W - 1, H - 1)$$$. Despite the darkness, Scared John can always recognize the exit, and he will leave as soon as he reaches it, determined never to set foot anywhere in the graveyard again. On his way to the exit, he can walk from one cell to an adjacent one, and he can only head to the North, East, SouthWest. In each cell there can be either one gravestone, one "haunted hole", or grass:
Figure: Sample graveyard The input consists of several test cases. Each test case begins with a line containing two integers $$$W$$$ and $$$H$$$ ($$$1 \le W, H \le 30$$$). These integers represent the width $$$W$$$ and height $$$H$$$ of the graveyard. The next line contains an integer $$$G$$$ ($$$G \ge 0$$$), the number of gravestones in the graveyard, and is followed by $$$G$$$ lines containing the positions of the gravestones. Each position is given by two integers $$$X$$$ and $$$Y$$$ ($$$0 \le X \lt W$$$ and $$$0 \le Y \lt H$$$).
The next line contains an integer $$$E$$$ ($$$E \ge 0$$$), the number of "haunted holes", and is followed by $$$E$$$ lines. Each of these contains five integers $$$X_1$$$, $$$Y_1$$$, $$$X_2$$$, $$$Y_2$$$, $$$T$$$. $$$(X_1, Y_1)$$$ is the position of the "haunted hole" ($$$0 \le X_1 \lt W$$$ and $$$0 \le Y_1 \lt H)$$$. $$$(X_2, Y_2)$$$ is the destination of the "haunted hole" ($$$0 \le X_2 \lt W$$$ and $$$0 \le Y_2 \lt H$$$). Note that the origin and the destination of a "haunted hole" can be identical. $$$T$$$ ($$$-10 000 \le T \le 10 000$$$) is the difference in seconds between the moment somebody enters the "haunted hole" and the moment he appears in the destination position; a positive number indicates that he reaches the destination after entering the hole. You can safely assume that there are no two "haunted holes" with the same origin, and the destination cell of a "haunted hole" does not contain a gravestone. Furthermore, there are neither gravestones nor "haunted holes" at positions $$$(0,0)$$$ and $$$(W-1,H-1)$$$.
The input will finish with a line containing 0 0, which should not be processed.
For each test case, if it is possible for Scared John to travel back in time indefinitely, output Never. Otherwise, print the minimum time in seconds that it takes him to cross the graveyard from the entrance to the exit if it is reachable, and Impossible if not.
3 3 2 2 1 1 2 0 4 3 2 2 1 3 1 1 3 0 2 2 0 4 2 0 1 2 0 1 0 -3 0 0
Impossible 4 Never
In this problem, we deal with only one of the multiple alpine skiing disciplines: slalom. A course is constructed by laying out a series of gates, which are formed by two poles. The skier must pass between the two poles forming each gate. The winner is the skier who takes the least time to complete the course while not missing any of the gates.
You have recently started to learn to ski, but you have already set yourself the goal of taking part in the Winter Olympic Games of 2018, for which Madrid will presumably present a candidature. As part of the theoretical training, you need to write a program that calculates, given a starting point and a series of gates, the minimum-length path starting from the point given and passing through each gate until you reach the last one, which is the finish line. You may assume that the gates are horizontal and are ordered from highest to lowest so that you need to pass through them in order. You consider yourself an accomplished skier, so you can make any series of turns, no matter how difficult, and your only concern is minimizing the total length of the path.
The first line of each case gives the number of gates $$$n$$$ ($$$1 \le n \le 1 000$$$). The next line contains two floating-point numbers, the Cartesian coordinates $$$x$$$ and $$$y$$$ of the starting position, in that order. Next, come $$$n$$$ lines with three floating-point numbers each, $$$y$$$ $$$x_1$$$ $$$x_2$$$ , meaning that the next gate is a horizontal line from $$$(x_1 , y)$$$ to $$$(x_2 , y)$$$. You can safely assume that $$$x_1 \lt x_2$$$. The values of $$$y$$$ are strictly decreasing and are always smaller than that of the starting position. The last gate represents the finish line. All coordinates are between $$$-500 000$$$ and $$$500 000$$$, inclusive. A value of $$$0$$$ for $$$n$$$ means the end of the input. A blank line follows each case.
For each test case, output a line with the minimum distance needed to reach the finish line. Your answer should be accurate to within an absolute or relative error of $$$10^{-7}$$$.
2 0 2 1 1 2 0 0.5 3 3 0 4 3 1 2 2 -1 0 1 1 2 0
2.41421356237 4.24264068712
You work as an engineer for the Inane Collaboration for Performance Computing, where you are in charge of designing an intercommunication network for their computers. The network is arranged as a rectangular array of $$$2n - 1$$$ rows, each having $$$2^{n-1}$$$ switches. A switch is a device with two input wires, $$$X$$$ and $$$Y$$$, and two output wires, $$$X_0$$$ and $$$Y_0$$$. If the switch is off, data from input $$$X$$$ will be relayed to output $$$X_0$$$, and data from $$$Y$$$ to $$$Y_0$$$. If it is on, $$$X$$$ will be connected to $$$Y_0$$$ and $$$Y$$$ to $$$X_0$$$. Additionally, there are $$$2^n$$$ computers in the topmost and bottommost rows, and messages need to be sent between pairs of them. Notice that data from two different sources cannot share a wire but, of course, both pieces of data can be routed through the same switch on different inputs.
You have come to the conclusion that the network that best suits your purposes has the Benes topology. A 1-Benes network is just a switch. For $$$n \gt 1$$$, a $$$n$$$-Benes network can be constructed recursively as follows:
Figure: 3-Benes network You are given a set of pairs $$$(a, b)$$$ of computers to connect simultaneously (where $$$a$$$ is a computer in the bottom row and $$$b$$$ a computer in the top row) by means of wire-disjoint paths, and you are to find how to select the state of all switches so that this can be accomplished.
The first line of each test case is an integer $$$n$$$ ($$$1 \le n \le 13$$$), meaning that you have $$$2^n$$$ pairs of computers to connect, as described above. A line with $$$n = 0$$$ marks the end of the input and should not be processed.
Each line with $$$n \gt 0$$$ will be followed by another line containing $$$2^n$$$ integers. The $$$i$$$-th integer ($$$0 \le i \lt 2^n$$$) will be the computer in the topmost row that the $$$i$$$-th computer in the bottommost row needs to communicate with.
The output for each case should have $$$2n-1$$$ lines, each containing a binary string of length $$$2^{n-1}$$$ indicating, for each switch, whether it must be turned on (1) or off (0).
The input given will always have at least one solution. In the case of several solutions, return the lexicographically smallest one. That is, the string in the top row must be lexicographically smallest; in case of a tie, the string in the second row must be lexicographically smallest, and so on.
Outputs for different test cases should be separated by a blank line.
2 3 2 1 0 3 3 7 4 0 2 6 1 5 0
00 11 11 0011 0000 0110 1111 1101
The police wants to hire the appropriate number of operators to listen to all conversations in a given period of time. Unfortunately, each of their operators can listen to one conversation only before needing a really long break to rest from the effort.
As a contractor of the police department, you have been asked to provide a program capable of determining the required number of operators. If the program does not work correctly, you will be put in jail as well, along with all the unhappy complainers. Do you really want to end up there?
Each test case starts with two integers denoting the number of phone calls $$$N$$$ ($$$1 \le N \lt 10000$$$) and the number of intervals $$$M$$$ ($$$1 \le M \lt 100$$$). This is followed by $$$N$$$ lines describing the telephone calls, each one consisting of four integers $$$Source$$$, $$$Destination$$$, $$$Start$$$ and $$$Duration$$$. $$$Source$$$ and $$$Destination$$$ identify the pair of telephone numbers establishing the connection ($$$0 \le Source, Destination \le 10 000 000$$$). $$$Start$$$ and $$$Duration$$$ are the start time and duration of the call in seconds ($$$1 \le Duration \le 10 000$$$ and $$$Start \ge 0$$$). You can safely assume that the sum of $$$Start$$$ and $$$Duration$$$ fits into a $$$32$$$-bit signed integer.
Afterwards follow $$$M$$$ lines containing the time intervals the police are interested in, each on described by two integers $$$Start$$$ and $$$Duration$$$, in the same format and with the same meaning and constraints as those in the telephone calls. The last test case is represented by $$$N = M = 0$$$ and must not be processed.
For each of the M intervals of each test case, print the number of calls that are active during at least one second of the interval.
3 2 3 4 2 5 1 2 0 10 6 5 5 8 0 6 8 2 1 2 8 9 0 10 9 1 10 1 0 0
3 2 1 0
Dr. Ellie Arroway has established contact with an extraterrestrial civilization. However, all efforts to decode their messages have failed so far because, as luck would have it, they have stumbled upon a race of stuttering aliens! Her team has found out that, in every long enough message, the most important words appear repeated a certain number of times as a sequence of consecutive characters, even in the middle of other words. Furthermore, sometimes they use contractions in an obscure manner. For example, if they need to say $$$bab$$$ twice, they might just send the message $$$babab$$$, which has been abbreviated because the second $$$b$$$ of the first word can be reused as the first $$$b$$$ of the second one.
Thus, the message contains possibly overlapping repetitions of the same words over and over again. As a result, Ellie turns to you, S.R. Hadden, for help in identifying the gist of the message.
Given an integer $$$m$$$, and a string $$$s$$$, representing the message, your task is to find the longest substring of $$$s$$$ that appears at least $$$m$$$ times. For example, in the message $$$baaaababababbababbab$$$, the length-5 word $$$babab$$$ is contained 3 times, namely at positions 5, 7 and 12 (where indices start at zero). No substring appearing 3 or more times is longer (see the first example from the sample input). On the other hand, no substring appears 11 times or more (see example 2).
In case there are several solutions, the substring with the rightmost occurrence is preferred (see example 3).
The input contains several test cases. Each test case consists of a line with an integer $$$m$$$ ($$$m \ge 1$$$), the minimum number of repetitions, followed by a line containing a string $$$s$$$ of length between $$$m$$$ and $$$40000$$$, inclusive. All characters in $$$s$$$ are lowercase characters from 'a' to 'z'. The last test case is denoted by $$$m = 0$$$ and must not be processed.
Print one line of output for each test case. If there is no solution, output none; otherwise, print two integers in a line, separated by a space. The first integer denotes the maximum length of a substring appearing at least m times; the second integer gives the rightmost starting position of this substring.
3 baaaababababbababbab 11 baaaababababbababbab 3 cccccc 0
5 12 none 4 2