The MTM Machine
|
|
The MTM is one of the first
digital machines ever designed. The aim of the machine is to process positive
integer numbers, but due to the primitive nature of the machine only some
numbers are accepted for processing; such numbers are called acceptable.
When a number is accepted by MTM, the machine outputs another number, according
to the rules stated below. When a number is not accepted, the machine simply
outputs NOT ACCEPTABLE.
A number is a non empty string of
decimal digits. Given two numbers N and M, when we write NM
we mean the number formed by the digits of N followed immediately by the
digits of M. For example, if N is 856 and M is 112 then NM
is 856112. For any number X, the associate of X is the number X2X.
For example, the associate of 78 is 78278.
We say that a number X produces
a number Y, if number X is acceptable and when given as input to
the machine MTM, the number returned by the machine is Y.
The behaviour of the MTM machine
is governed by the following rules:
Rule 0:
A number containing the digit 0 (zero) is not acceptable.
Rule 1:
Given any number X not containing a digit zero, then number 2X
produces X. For example, 234 produces 34.
Rule 2:
Given any pair of numbers X, Y, if X produces Y
then 3X produces the associate of Y. For example, 25 produces 5
by Rule 1, so 325 produces 525.
Rule 3:
No other numbers are acceptable.
Your task here is to write a
program that simulates the MTM machine.
Input
The input file
contains a set of test cases. Each test case appears in a separate line, and
consists of a single positive number N, N < 1032,
to be processed by the MTM machine. The file ends with a line containing the
number 0 that should not be processed.
You may assume that the largest
number output by the machine has at most 1000 digits.
Output
For each test
case, your program should write one line with the output produced by the
machine if the corresponding number is acceptable; otherwise your program
should write NOT ACCEPTABLE.
Sample Input
20224232332890
Sample Output
NOT ACCEPTABLE2NOT ACCEPTABLENOT ACCEPTABLE89289289289
Goldbach's Conjecture
|
|
Goldbach's Conjecture: For any even number n greater than
or equal to 4, there exists at least one pair of prime numbers p1
and p2 such that n = p1 + p2.
This conjecture has not been
proved nor refused yet. No one is sure whether this conjecture actually holds.
However, one can find such a pair of prime numbers, if any, for a given even
number. The problem here is to write a program that reports the number of all
the pairs of prime numbers satisfying the condition in the conjecture for a
given even number.
A sequence of even numbers is
given as input. Corresponding to each number, the program should output the
number of pairs mentioned above. Notice that we are interested in the number of
essentially different pairs and therefore you should not count (p1,
p2) and (p2, p1)
separately as two different pairs.
Input
An integer is given
in each input line. You may assume that each integer is even, and is greater
than or equal to 4 and less than 100000. The end of the input is indicated by a
number 0.
Output
Each output line
should contain an integer number. No other characters should appear in the
output.
Sample Input
610120
Sample Output
121
Pointing the Way
|
|
A compass is usually thought of as having 4 primary points at North, East, South, and West. These directions correspond to points on a circle, with North at 0 degrees, East at 90 degrees, South at 180 degrees, and West at 270 degrees. There can be many points between the primary points. For example, the point North-East is halfway between North and East, at 45 degrees and East-North-East is halfway between East and North-East at 67.5 degrees.
This plan has been determined to be too restrictive for space travel, so you have been asked to create a more general compass, with anywhere from 3 to 26 primary points.
For example, if a compass were to have 5 points, for simplicity sake, name them with the first five letters of the alphabet as below:
The point A is oriented with 0 degrees. This means B is at 72 degrees, C is at 144 degrees, D is at 216 degrees, and E is at 288 degrees. At 36 degrees, halfway between A and B, is the compass point AB. At 18 degrees, halfway between A and AB is the compass point AAB. At 54 degrees, halfway between AB and B is the point BAB.
To name compass points, follow the example in the chart below for a compass with 4 points and the rules below:
· 
The
major compass points are called 1-points. The name of a 1-point is a single alphabetic
character, where the first 1-point is 'A' (at 0 degrees) and others are B, C,
... in clockwise order.
· 2-points are halfway between two one points. The name of the 2-point between two contiguous 1‑points, P and Q (specified in clockwise order,) is PQ.
· A k-point (where k ³ 3) bisects an angle determined by a (k-1)-point and an n-point (where n < k-1). For instance, ABAB is a 4-point which bisects the angle of the 3-point BAB and the 2-point AB. The name of a k-point between a and b is ab, where b is the name of the nearest (k-1)-point and a is the name of the 1-point nearest to ab in the direction opposite of b.
Your program must take a number of compass points and a group of compass points for each and return the degree measure of the compass point. For example, for the example above, a 5 pointed compass would place BAB at 54 degrees and CD at 180 degrees.
Input
The input will have information about a number of different input sets. The first line of each set will be a number of compass points, n, where 3 £ n £ 26. The second line of the data set will have a number of compass points to be analyzed, k. The next k lines will each have compass point, where each point is a list of between 1 and 8 upper case letters. You may assume each string represents a valid compass point for the given compass. There will be no leading or trailing blanks on a line.
The end of input will be indicated by a compass with 0 points. This data should not be processed.
Output
Output the number of points of the compass at the beginning of the output for each set. For each of the k compass points, echo the compass point and give the degree measurement it represents to 2 decimal places of precision.
Have a blank line after each data set.
Sample Input
5
3
B
BBC
AAEA
26
1
W
4
1
BBAB
0
Sample Output
Compass with 5 points:
B : 72.00 degrees
BBC : 90.00 degrees
AAEA : 351.00 degrees
Compass with 26 points:
W : 304.62 degrees
Compass with 4 points:
BBAB : 78.75 degrees
North and South
|
|
Gainesville is a well known stop on Interstate 75, a north south route. But it is far from the only town along the highway. This problem asks you to look at a number of towns and determine their relative positions.
Input and Output
The input for this problem comes in two sets. The first part of the input gives the relative positions of towns. There will be 0 or more lines in this set, each of which has a pair of city names. In this input, the city listed first is to the south of the city listed second. So, the line:
City_1 City_2
represents the fact "City_1 is south of City_2."
The list of relative positions will end with a line containing just a single # sign.
After the pound signs will be questions about the data in the format:
City_1 City_2
This represents the question: What is the position of City_1 relative to City_2? Your program should print one of the following lines of output for each question:
City_1 is north of City_2.
City_1 is south of City_2.
The relative positioning of City_1 and City_2 is unknown.
Where the appropriate city names are substituted into the output. Have one blank line after each line of output.
The list of questions will be ended by a line containing a single # sign.
In both sections, each name is a string of up to 11 letters, and the names will be separated by at least one blank. Any blanks before or after a name should be ignored. Case is significant in names, so Gainesville and GAINESVILLE should be considered different cities by your program. There are not more than 100 cities on the highway.
Recall, "is north of" is a transitive relationship, so if City_1 is north of City_2 and City_2 is north of City_3, you may conclude City_1 is north of City_3. You may assume the input is consistent, that is, there will be no information that indicates a city is north of itself.
Sample Input
Gainesville Valdosta
Valdosta Atlanta
LakeCity Valdosta
#
Gainesville Atlanta
Tampa Gainesville
Atlanta Valdosta
LakeCity Gainesville
#
Sample Output
Gainesville is south of Atlanta.
The relative positioning of Tampa and Gainesville is unknown.
Atlanta is north of Valdosta.
The relative positioning of LakeCity and Gainesville is unknown.
A Prüf Problem
|
|
Prüfer codes are used to represent labeled free trees. A free tree is a connected, acyclic,
undirected graph. The labeling for a
free tree with n nodes gives each node a label from 1 to n, using each value
exactly one time. One possible labeled
free tree with 8 nodes is:
A Prüfer code for a free tree with n nodes is a sequence of n-2 labels that completely represents the free tree.
To construct a Prüfer code from a free tree, first identify all leaves. A leaf is a node with only one adjacent
node. In the tree above, the nodes 1,
3, 4, 6, and 7 are leaves. Then remove
the leaf with the lowest label (in this case 1) and add the label of the node
adjacent to it (in this case 5). This
will give a new free tree:
Continue to find the leaf with the smallest label, remove it, and add the label of the node adjacent to it to the Prüfer code, until there are only two nodes left in the free tree. The Prüfer code for the original free tree is 5, 2, 8, 5, 2, 5.
Notice that in the Prüfer code, each node appears k-1 times, where k is the number of edges adjacent to a node. For example, there are 4 edges adjacent to node 5 in the tree and 5 appears in the Prüfer code 3 times. Therefore, any node that is a leaf in the original free tree will not appear in the Prüfer code.
You should write a program to generate the original tree from its Prüfer code.
Input
The input to your program will be a number of different Prüfer codes. Each code will take one line of data. The first integer on the line will be n, the number of nodes in the free tree. You may assume 3 £ n £ 20. The next n-2 digits will be the Prüfer code for the free tree.
The last line of input will consist of just value 0 for n. You should not process this line.
Output
For each input set, write a line with the number of the input set. Then, on the next line, list the edges (as ordered pairs) in the tree in free tree in canonical order. To canonically order a set of edges, arrange each as (i, j), where i and j are the nodes they connect and i < j. Then, to compare two edges (i, j) and (m, n), the edge (i, j) comes before (m, n) if and only if i < m, or i = m and j < n.
Have one blank line after each output set.
Sample Input
3 2
8 5 2 8 5 2 5
5 3 3 5
0
Sample Output
Input set 1:
(1,2) (2,3)
Input set 2:
(1,5) (2,3) (2,5) (2,7) (4,8) (5,6) (5,8)
Input set 3:
(1,3) (2,3) (3,5) (4,5)