Testing the CATCHER

 

CATCHER.C CATCHER.CPP CATCHER.PAS

A military contractor for the Department of Defense has just completed a series of preliminary tests for a new defensive missile called the CATCHER which is capable of intercepting multiple incoming offensive missiles. The CATCHER is supposed to be a remarkable defensive missile. It can move forward, laterally, and downward at very fast speeds, and it can intercept an offensive missile without being damaged. But it does have one major flaw. Although it can be fired to reach any initial elevation, it has no power to move higher than the last missile that it has intercepted.

The tests which the contractor completed were computer simulations of battlefield and hostile attack conditions. Since they were only preliminary, the simulations tested only the CATCHER's vertical movement capability. In each simulation, the CATCHER was fired at a sequence of offensive missiles which were incoming at fixed time intervals. The only information available to the CATCHER for each incoming missile was its height at the point it could be intercepted and where it appeared in the sequence of missiles. Each incoming missile for a test run is represented in the sequence only once.

The result of each test is reported as the sequence of incoming missiles and the total number of those missiles that are intercepted by the CATCHER in that test.

The General Accounting Office wants to be sure that the simulation test results submitted by the military contractor are attainable, given the constraints of the CATCHER. You must write a program that takes input data representing the pattern of incoming missiles for several different tests and outputs the maximum numbers of missiles that the CATCHER can intercept for those tests. For any incoming missile in a test, the CATCHER is able to intercept it if and only if it satisfies one of these two conditions:

The incoming missile is the first missile to be intercepted in this test.

-or-

The missile was fired after the last missile that was intercepted and it is not higher than the last missile which was intercepted.

Input

The input data for any test consists of a sequence of one or more non-negative integers, all of which are less than or equal to 32,767, representing the heights of the incoming missiles (the test pattern). The last number in each sequence is -1, which signifies the end of data for that particular test and is not considered to represent a missile height. There are not more than 1000 missiles in each test case. The end of data for the entire input is the number -1 as the first value in a test; it is not considered to be a separate test.

Output

Output for each test consists of a test number (Test #1, Test #2, etc.) and the maximum number of incoming missiles that the CATCHER could possibly intercept for the test. That maximum number appears after an identifying message. There must be at least one blank line between output for successive data sets.

Sample Input

389

207

155

300

299

170

158

65

-1

23

34

21

-1

-1

Sample Output

Test #1:

  maximum possible interceptions: 6

Test #2:

  maximum possible interceptions: 2

 

Just the Facts

 

FACTS.C FACTS.CPP FACTS.PAS

The expression N!, read as “N factorial”, denotes the product of the first N positive integers, where N is nonnegative. So, for example,

For this problem, you are to write a program that can compute the last non-zero digit of any factorial for (0 <= N <= 10000). For example, if your program is asked to compute the last nonzero digit of 5!, your program should produce “2” because 5! = 120, and 2 is the last nonzero digit of  120.

Input 

Input to the program is a series of nonnegative integers not exceeding 10000, each on its own line with no other letters, digits or spaces. For each integer N, you should read the value and compute the last nonzero digit of N!.

Output 

For each integer input, the program should print exactly one line of output. Each line of output should contain the value N, right-justified in columns 1 through 5 with leading blanks, not leading zeroes. Columns 6 - 9 must contain `` -> " (space hyphen greater space). Column 10 must contain the single last non-zero digit of N!.

Sample Input 

1

2

26

125

3125

9999

Sample Output 

    1 -> 1

    2 -> 2

   26 -> 4

  125 -> 8

 3125 -> 2

 9999 -> 8

 

Sex Assignments And Breeding Experiments

 

BREEDING.C BREEDING.CPP BREEDING.PAS

Everyone is familiar with the pictorial representation of family trees. In these "pictures" one uses points and lines to represent family structures and interfamily relationships. Thus, if M and F are the parents of three children, two boys and one girl, we have the figure below:

The next figure might represent the inter-family relationship of two families

It is easy to conceive of a large number of such pictures. Some can represent family trees and some cannot. You are to consider the problem of characterizing those which can represent family trees. We will actually work in a simpler context than that of human relationships. Most human societies preclude family trees of the forms shown below.

It is, however, quite complicated to give conditions which would eliminate pictures of this sort. For simplicity, we suppose that we are dealing with a population which is completely characterized by the condition of bisexual reproduction (M & F). If the picture or graph is such that by a proper assignment of sexes to the members of the population, the picture represents the results of a breeding experiment which could theoretically take place, then we say the graph is sexy. Otherwise the graph is not sexy. You must write a program to examine an arbitrary directed graph and determine if it is sexy.

Input

Input will be a description of a graph in the following form:

An integer n (n < 201) indicating the number of nodes in the graph, followed by an integer m indicating the number of directed edges in the graph will appear on the first line of input. The next m lines of the file will each contain a pair x, y of integers in the range 1 - n. Each pair will represent a directed edge from node x to node y.

Output

For each graph in the input file, you will output the appropriate one of the following statements.

Graph number i is sexy

Graph number i is not sexy

The number i represents the number of the graph in the input file.

We are adopting the convention that the existence of a directed edge from x to y indicates that x is a parent of y. Further, each individual usually has exactly two parents. No individual can have two parents of the same sex or more than two parents. Breeding experiments do not extend into the indefinite past. A point is always reached where one or both of the parents of a member of the population are unknown. The nodes with no parents would appear on the top level of a sexy graph. Births of individuals are assumed to be sequential in time. Thus the following graph is not sexy.

Sample input

5 6 

1 3 

2 3 

1 4 

2 4 

1 5 

2 5 

3 3 

1 2 

2 3 

3 1

Sample output

Graph number 1 is sexy

Graph number 2 is not sexy

 

Multiplying by Rotation

 

MULTIPLY.C MULTIPLY.CPP MULTIPLY.PAS

Multiplication of natural numbers in general is a cumbersome operation. In some cases however the product can be obtained by moving the last digit to the front.

Example: 179487 * 4 = 717948

Of course this property depends on the number system you use, in the above example we used the decimal representation. In base 9 we have a shorter example:

17 * 4 = 71 (base 9) 

as (9 * 1 + 7) * 4 = 7 * 9 + 1 

Input 

The input for your program is a textfile. Each line consists of three numbers separated by a space: the base of the number system, the least significant digit of the first factor, and the second factor. This second factor is one digit only hence less than the base. The base is less than or equal to 10. The input file ends with the standard end-of-file marker.

Output 

Your program determines for each input line the smallest first factor with the rotamult property. The output-file is also a textfile. Each line contains the answer for the corresponding input line.

Sample Input 

10 7 4

9 7 4

7 4 2

Sample Output 

179487

17

210352456314

 

Izštevanka

 

IZSTEJ.C IZSTEJ.CPP IZSTEJ.PAS

Otroci se gredo lovit. Določajo, kdo bo prvi lovil. Postavijo se v krog in vsak drugi je izločen. Tisti, ki ostane, lovi.

V Velikem Kašlju so se odločili, da organizirajo vsebutalsko prvenstvo v lovljenju. Ker pa je pričakujejo  zelo veliko prijav  tudi do 30000  bi izstevanje trajalo zelo dolgo. Zato so se odločili, da bodo sestavi li program, ki bo na osnovi  prijavnih številk tekmovalcev opravil to izštevanje. Pomagaj jim in sestavi program, ki bo na osnovi števila tekmovalcev, ki nosijo zaporedne številke od 1 do n, določil tistega, ki na začetku lovi.  Prvi je izločen tekovalec #2,  nato #4, …

Če bi bilo le 5 prijavljenih, bi bili po vrsti izločeni:  #2, #4, #1 in #5.  Lovil bi #3.

Vhodni podatki

Vhodno datoteko sestavlja en ali več testnih primerov. Vsak testni primer sestavlja vrstica, v kateri je podano število tekomvalcev n (1 <= n <= 30000). Tetsni primeri so zaključeni z vrednostjo nič (0) za n.

Izhodni podatki

Za vsak testni primer izpiši vrstico "Od x otrok ostane otrok #y." , kjer je x število otrok (tekmovalcev) in y otrok, ki prvi lovi. Za zadnjo vrednost 0 ne izpiši ničesar.

Primer vhodnih podatkov

5

1

7

0

Primer izhodnih podatkov

Od 5 otrok ostane otrok #3.

Od 1 otrok ostane otrok #1.

Od 7 otrok ostane otrok #7.

 

Frogger

 

FROGGER.C FROGGER.CPP FROGGER.PAS

Freddy Frog is sitting on a stone in the middle of a lake. Suddenly he notices Fiona Frog who is sitting on another stone. He plans to visit her, but since the water is dirty and full of tourists' sunscreen, he wants to avoid swimming and instead reach her by jumping.

Unfortunately Fiona's stone is out of his jump range. Therefore Freddy considers to use other stones as intermediate stops and reach her by a sequence of several small jumps.

To execute a given sequence of jumps, a frog's jump range obviously must be at least as long as the longest jump occuring in the sequence.

The frog distance (humans also call it minimax distance) between two stones therefore is defined as the minimum necessary jump range over all possible paths between the two stones.

You are given the coordinates of Freddy's stone, Fiona's stone and all other stones in the lake. Your job is to compute the frog distance between Freddy's and Fiona's stone.

Input Specification 

The input file will contain one or more test cases. The first line of each test case will contain the number of stones n (2 <= n <= 200). The next n lines each contain two integers x_i, y_i
(0 <= x_i, y_i <= 1000) representing the coordinates of stone #i. Stone #1 is Freddy's stone, stone #2 is Fiona's stone, the other n-2 stones are unoccupied. There's a blank line following each test case. Input is terminated by a value of zero (0) for n.

Output Specification 

For each test case, print a line saying ``Scenario #x" and a line saying ``Frog Distance = y" where x is replaced by the test case number (they are numbered from 1) and y is replaced by the appropriate real number, printed to three decimals. Put a blank line after each test case, even after the last one.

Sample Input 

2

0 0

3 4

3

17 4

19 4

18 5

0

Sample Output 

Scenario #1

Frog Distance = 5.000

Scenario #2

Frog Distance = 1.414

 

Bicoloring

 

BICOLORING.C BICOLORING.CPP BICOLORING.PAS

In 1976 the ``Four Color Map Theorem" was proven with the assistance of a computer. This theorem states that every map can be colored using only four colors, in such a way that no region is colored using the same color as a neighbor region.

Here you are asked to solve a simpler similar problem. You have to decide whether a given arbitrary connected graph can be bicolored. That is, if one can assign colors (from a palette of two) to the nodes in such a way that no two adjacent nodes have the same color. To simplify the problem you can assume:

• no node will have an edge to itself.
• the graph is nondirected. That is, if a node a is said to be connected to a node b, then you must assume that b is connected to a.
• the graph will be strongly connected. That is, there will be at least one path from any node to any other node.

Input 

The input consists of several test cases. Each test case starts with a line containing the number n (1 < n < 200) of different nodes. The second line contains the number of edges l. After this, l lines will follow, each containing two numbers that specify an edge between the two nodes that they represent. A node in the graph will be labeled using a number a (0 <= a < n).

An input with n = 0 will mark the end of the input and is not to be processed.

Output 

You have to decide whether the input graph can be bicolored or not, and print it as shown below.

Sample Input 

3

3

0 1

1 2

2 0

9

8

0 1

0 2

0 3

0 4

0 5

0 6

0 7

0 8

0

Sample Output 

NOT BICOLORABLE.

BICOLORABLE.

 

Pizza Anyone?

 

PIZZA.C PIZZA.CPP PIZZA.PAS

You are responsible for ordering a large pizza for you and your friends. Each of them has told you what he wants on a pizza and what he does not; of course they all understand that since there is only going to be one pizza, no one is likely to have all their requirements satisfied. Can you order a pizza that will satisfy at least one request from all your friends?

The pizza parlor you are calling offers the following pizza toppings; you can include or omit any of them in a pizza:

Your friends provide you with a line of text that describes their pizza preferences. For example, the line

+O-H+P;

reveals that someone will accept a pizza with onion, or without ham, or with pepperoni, and the line

-E-I-D+A+J;

indicates that someone else will accept a pizza that omits extra cheese, or Italian sausage, or diced garlic, or that includes anchovies or jalapenos.

Input 

The input consists of a series of pizza constraints.

A pizza constraint is a list of 1 to 12 topping constraint lists each on a line by itself followed by a period on a line by itself.

A topping constraint list is a series of topping requests terminated by a single semicolon.

An topping request is a sign character (+/-) and then an uppercase letter from A to P.

Output 

For each pizza constraint, provide a description of a pizza that satisfies it. A description is the string ``Toppings: " in columns 1 through 10 and then a series of letters, in alphabetical order, listing the toppings on the pizza. So, a pizza with onion, anchovies, fresh broccoli and Canadian bacon would be described by:

Toppings: ACFO

If no combination toppings can be found which satisfies at least one request of every person, your program should print the string

No pizza can satisfy these requests.

on a line by itself starting in column 1.

If there is more than one pizza satisfying the constraint, choose the cheapest one (the one with least toppings). If there are two possible pizzas with the same number of toppings, display lexicographicaly smaller one.

Sample Input 

+A+B+C+D-E-F-G-H;

-A-B+C+D-E-F+G+H;

-A+B-C+D-E+F-G+H;

.

+A+B+C+D;

+E+F+F+H;

+A+B-G;

+O+J-F;

+H+I+C;

+P;

+O+M+L;

+M-L+P;

.

+A+B+C+D;

+E+F+F+H;

+A+B-G;

+P-O;

+O+J-F;

+H+I+C;

+P;

+O;

+O+M+L;

-O-P;

+M-L+P;

.

Sample Output 

Toppings:

Toppings: CELP

No pizza can satisfy these requests.