Problem G
Color the Map
—- 2004年 愛媛大会 —-

You were lucky enough to get a map just before entering the legendary magical mystery world. The map shows the whole area of your planned exploration, including several countries with complicated borders. The map is clearly drawn, but in sepia ink only; it is hard to recognize at a glance which region belongs to which country, and this might bring you into severe danger. You have decided to color the map before entering the area. “A good deal depends on preparation,” you talked to yourself.

Each country has one or more territories, each of which has a polygonal shape. Territories belonging to one country may or may not “touch” each other, i.e. there may be disconnected territories. All the territories belonging to the same country must be assigned the same color. You can assign the same color to more than one country, but, to avoid confusion, two countries “adjacent” to each other should be assigned different colors. Two countries are considered to be “adjacent” if any of their territories share a border of non-zero length.

Write a program that finds the least number of colors required to color the map.

Input

The input consists of multiple map data. Each map data starts with a line containing the total number of territories n, followed by the data for those territories. n is a positive integer not more than 100. The data for a territory with m vertices has the following format:

  String
  x1 y1
  x2 y2
  . . .
  xm ym

“String” (a sequence of alphanumerical characters) gives the name of the country it belongs to. A country name has at least one character and never has more than twenty. When a country has multiple territories, its name appears in each of them.

Remaining lines represent the vertices of the territory. A vertex data line has a pair of nonnegative integers which represent the x- and y-coordinates of a vertex. x- and y-coordinates are separated by a single space, and y-coordinate is immediately followed by a newline. Edges of the territory are obtained by connecting vertices given in two adjacent vertex data lines, and by connecting vertices given in the last and the first vertex data lines. None of x- and y-coordinates exceeds 1000. Finally,
You may assume that the contours of polygons are simple, i.e. they do not cross nor touch themselves. No two polygons share a region of non-zero area. The number of countries in a map does not exceed 10.

The last map data is followed by a line containing only a zero, marking the end of the input data.

Output

For each map data, output one line containing the least possible number of colors required to
color the map satisfying the specified conditions.

6
Blizid
0 0
60 0
60 60
0 60
0 50
50 50
50 10
0 10
-1
Blizid
0 10
10 10
10 50
0 50
-1
Windom
10 10
50 10
40 20
20 20
20 40
10 50
-1
Accent
50 10
50 50
35 50
35 25
-1
Pilot
35 25
35 50
10 50
-1
Blizid
20 20
40 20
20 40
-1
4
A1234567890123456789
0 0
0 100
100 100
100 0
-1
B1234567890123456789
100 100
100 200
200 200
200 100
-1
C1234567890123456789
0 100
100 100
100 200
0 200
-1
D123456789012345678
100 0
100 100
200 100
200 0
-1
0

Output for the Sample Input

4
2

Problem F
Dice Puzzle
—- 2004年 愛媛大会 —-

Let’s try a dice puzzle. The rules of this puzzle are as follows.

 1. Dice with six faces as shown in Figure 1 are used in the puzzle.


Figure 1: Faces of a die

 2. With twenty seven such dice, a 3 x 3 x 3 cube is built as shown in Figure 2.


Figure 2: 3 x 3 x 3 cube

 3. When building up a cube made of dice, the sum of the numbers marked on the faces of adjacent dice that are placed against each other must be seven (See Figure 3). For
example, if one face of the pair is marked “2”, then the other face must be “5”.


Figure 3: A pair of faces placed against each other

 4. The top and the front views of the cube are partially given, i.e. the numbers on faces of some of the dice on the top and on the front are given.


Figure 4: Top and front views of the cube

 5. The goal of the puzzle is to find all the plausible dice arrangements that are consistent with the given top and front view information.

Your job is to write a program that solves this puzzle.

Input

The input consists of multiple datasets in the following format.

  N
  Dataset1
  Dataset2
  . . .
  DatasetN

N is the number of the datasets.

The format of each dataset is as follows.

  T11 T12 T13
  T21 T22 T23
  T31 T32 T33
  F11 F12 F13
  F21 F22 F23
  F31 F32 F33

Tij and Fij (1 <= i <= 3, 1 <= j <= 3) are the faces of dice appearing on the top and front views, as shown in Figure 2, or a zero. A zero means that the face at the corresponding position is unknown.

Output

For each plausible arrangement of dice, compute the sum of the numbers marked on the nine faces appearing on the right side of the cube, that is, with the notation given in Figure 2, ΣΣRij.

For each dataset, you should output the right view sums for all the plausible arrangements, in ascending order and without duplicates. Numbers should be separated by a single space.

When there are no plausible arrangements for a dataset, output a zero.

For example, suppose that the top and the front views are given as follows.


Figure 5: Example

There are four plausible right views as shown in Figure 6. The right view sums are 33, 36, 32, and 33, respectively. After rearranging them into ascending order and eliminating duplicates, the answer should be \32 33 36″.


Figure 6: Plausible right views

The output should be one line for each dataset. The output may have spaces at ends of lines.

Sample Input

4
1 1 1
1 1 1
1 1 1
2 2 2
2 2 2
2 2 2
4 3 3
5 2 2
4 3 3
6 1 1
6 1 1
6 1 0
1 0 0
0 2 0
0 0 0
5 1 2
5 1 2
0 0 0
2 0 0
0 3 0
0 0 0
0 0 0
0 0 0
3 0 1

Output for the Sample Input

27
24
32 33 36
0

Problem E
Confusing Login Names
—- 2004年 愛媛大会 —-

Meikyokan University is very famous for its research and education in the area of computer science. This university has a computer center that has advanced and secure computing facilities including supercomputers and many personal computers connected to the Internet.

One of the policies of the computer center is to let the students select their own login names. Unfortunately, students are apt to select similar login names, and troubles caused by mistakes in entering or specifying login names are relatively common. These troubles are a burden on the staff of the computer center.

To avoid such troubles, Dr. Choei Takano, the chief manager of the computer center, decided to stamp out similar and confusing login names. To this end, Takano has to develop a program that detects confusing login names.

Based on the following four operations on strings, the distance between two login names is determined as the minimum number of operations that transforms one login name to the other.

  1. Deleting a character at an arbitrary position.
  2. Inserting a character into an arbitrary position.
  3. Replacing a character at an arbitrary position with another character.
  4. Swapping two adjacent characters at an arbitrary position.

For example, the distance between “omura” and “murai” is two, because the following sequence of operations transforms “omura” to “murai”.

  omura -> delete ‘o’ -> mura -> insert ‘i’ -> murai

Another example is that the distance between \akasan” and \kaason” is also two.

  akasan -> swap ‘a’ and ‘k’ -> kaasan -> replace ‘a’ with ‘o’ -> kaason

Takano decided that two login names with a small distance are confusing and thus must be avoided.

Your job is to write a program that enumerates all the confusing pairs of login names.

Beware that the rules may combine in subtle ways. For instance, the distance between “ant” and “neat” is two.

  ant -> swap ‘a’ and ‘n’ -> nat -> insert ‘e’ -> neat

Input

The input consists of multiple datasets. Each dataset is given in the following format.

  n
  d
  name1
  name2
  . . .
  namen

The first integer n is the number of login names. Then comes a positive integer d. Two login names whose distance is less than or equal to d are deemed to be confusing. You may assume that 0 < n <= 200 and 0 < d <= 2. The i-th student’s login name is given by namei, which is composed of only lowercase letters. Its length is less than 16. You can assume that there are no duplicates in namei (1 <= i <= n).

The end of the input is indicated by a line that solely contains a zero.

Output

For each dataset, your program should output all pairs of confusing login names, one pair per line, followed by the total number of confusing pairs in the dataset.

In each pair, the two login names are to be separated only by a comma character (,), and the login name that is alphabetically preceding the other should appear first. The entire output of confusing pairs for each dataset must be sorted as follows. For two pairs “w1,w2” and “w3,w4“, if w1 alphabetically precedes w3, or they are the same and w2 precedes w4, then “w1,w2” must appear before “w3,w4“.

Sample Input

8
2
omura
toshio
raku
tanaka
imura
yoshoi
hayashi
miura
3
1
tasaka
nakata
tanaka
1
1
foo
5
2
psqt
abcdef
abzdefa
pqrst
abdxcef
0

Output for the Sample Input

imura,miura
imura,omura
miura,omura
toshio,yoshoi
4
tanaka,tasaka
1
0
abcdef,abdxcef
abcdef,abzdefa
pqrst,psqt
3

Problem D
Pathological Paths
—- 2004年 愛媛大会 —-

Professor Pathfinder is a distinguished authority on the structure of hyperlinks in the World Wide Web. For establishing his hypotheses, he has been developing software agents, which automatically traverse hyperlinks and analyze the structure of the Web. Today, he has gotten an intriguing idea to improve his software agents. However, he is very busy and requires help from good programmers. You are now being asked to be involved in his development team and to create a small but critical software module of his new type of software agents.

Upon traversal of hyperlinks, Pathfinder’s software agents incrementally generate a map of visited portions of the Web. So the agents should maintain the list of traversed hyperlinks and visited web pages. One problem in keeping track of such information is that two or more different URLs can point to the same web page. For instance, by typing any one of the following five URLs, your favorite browsers probably bring you to the same web page, which as you may have visited is the home page of the ACM ICPC Ehime contest.

  http://www.ehime-u.ac.jp/ICPC/
  http://www.ehime-u.ac.jp/ICPC
  http://www.ehime-u.ac.jp/ICPC/../ICPC/
  http://www.ehime-u.ac.jp/ICPC/./
  http://www.ehime-u.ac.jp/ICPC/index.html

Your program should reveal such aliases for Pathfinder’s experiments.

Well, …but it were a real challenge and to be perfect you might have to embed rather complicated logic into your program. We are afraid that even excellent programmers like you could not complete it in five hours. So, we make the problem a little simpler and subtly unrealistic. You should focus on the path parts (i.e. /ICPC/, /ICPC, /ICPC/../ICPC/, /ICPC/./, and /ICPC/index.html in the above example) of URLs and ignore the scheme parts (e.g. http://), the server parts (e.g. www.ehime-u.ac.jp), and other optional parts. You should carefully read the rules described in the sequel since some of them may not be based on the reality of today’s Web and URLs.

Each path part in this problem is an absolute pathname, which specifies a path from the root directory to some web page in a hierarchical (tree-shaped) directory structure. A pathname always starts with a slash (/), representing the root directory, followed by path segments delimited by a slash. For instance, /ICPC/index.html is a pathname with two path segments ICPC and index.html.

All those path segments but the last should be directory names and the last one the name of an ordinary file where a web page is stored. However, we have one exceptional rule: an ordinary file name index.html at the end of a pathname may be omitted. For instance, a pathname /ICPC/index.html can be shortened to /ICPC/, if index.html is an existing ordinary file name. More precisely, if ICPC is the name of an existing directory just under the root and index.html is the name of an existing ordinary file just under the /ICPC directory, /ICPC/index.html and /ICPC/ refer to the same web page. Furthermore, the last slash following the last path segment can also be omitted. That is, for instance, /ICPC/ can be further shortened to /ICPC. However, /index.html can only be abbreviated to / (a single slash).

You should pay special attention to path segments consisting of a single period (.) or a double period (..), both of which are always regarded as directory names. The former represents the directory itself and the latter represents its parent directory. Therefore, if /ICPC/ refers to some web page, both /ICPC/./ and /ICPC/../ICPC/ refer to the same page. Also /ICPC2/../ICPC/ refers to the same page if ICPC2 is the name of an existing directory just under the root; otherwise it does not refer to any web page. Note that the root directory does not have any parent directory and thus such pathnames as /../ and /ICPC/../../index.html cannot point to any web page.

Your job in this problem is to write a program that checks whether two given pathnames refer to existing web pages and, if so, examines whether they are the same.

Input

The input consists of multiple datasets. The first line of each dataset contains two positive integers N and M, both of which are less than or equal to 100 and are separated by a single space character.

The rest of the dataset consists of N + 2M lines, each of which contains a syntactically correct pathname of at most 100 characters. You may assume that each path segment enclosed by two slashes is of length at least one. In other words, two consecutive slashes cannot occur in any pathname. Each path segment does not include anything other than alphanumerical characters (i.e. ‘a’-‘z’, ‘A’-‘Z’, and ‘0’-‘9’) and periods (‘.’).

The first N pathnames enumerate all the web pages (ordinary files). Every existing directory name occurs at least once in these pathnames. You can assume that these pathnames do not include any path segments consisting solely of single or double periods and that the last path segments are ordinary file names. Therefore, you do not have to worry about special rules for index.html and single/double periods. You can also assume that no two of the N pathnames point to the same page.

Each of the following M pairs of pathnames is a question: do the two pathnames point to the same web page? These pathnames may include single or double periods and may be terminated by a slash. They may include names that do not correspond to existing directories or ordinary files.

Two zeros in a line indicate the end of the input.

Output

For each dataset, your program should output the M answers to the M questions, each in a separate line. Each answer should be “yes” if both point to the same web page, “not found” if at least one of the pathnames does not point to any one of the first N web pages listed in the input, or “no” otherwise.

Sample Input

5 6
/home/ACM/index.html
/ICPC/index.html
/ICPC/general.html
/ICPC/japanese/index.html
/ICPC/secret/confidential/2005/index.html
/home/ACM/
/home/ICPC/../ACM/
/ICPC/secret/
/ICPC/secret/index.html
/ICPC
/ICPC/../ICPC/index.html
/ICPC
/ICPC/general.html
/ICPC/japanese/.././
/ICPC/japanese/./../
/home/ACM/index.html
/home/ACM/index.html/
1 4
/index.html/index.html
/
/index.html/index.html
/index.html
/index.html/index.html
/..
/index.html/../..
/index.html/
/index.html/index.html/..
0 0

Output for the Sample Input

not found
not found
yes
no
yes
not found
not found
yes
not found
not found

Problem C
Leaky Cryptography
—- 2004年 愛媛大会 —-

The ACM ICPC judges are very careful about not leaking their problems, and all communications are encrypted. However, one does sometimes make mistakes, like using too weak an encryption scheme. Here is an example of that.

The encryption chosen was very simple: encrypt each chunk of the input by flipping some bits according to a shared key. To provide reasonable security, the size of both chunk and key is 32 bits.

That is, suppose the input was a sequence of m 32-bit integers.

N1 N2 N3 . . . Nm

After encoding with the key K it becomes the following sequence of m 32-bit integers.

(N1 ^ K) (N2 ^ K) (N3 ^ K) . . . (Nm ^ K)

where (a ^ b) is the bitwise exclusive or of a and b.

Exclusive or is the logical operator which is 1 when only one of its operands is 1, and 0 otherwise. Here is its definition for 1-bit integers.

0 xor 0 = 0   0 xor 1 = 1
1 xor 0 = 1   1 xor 1 = 0

As you can see, it is identical to addition modulo 2. For two 32-bit integers a and b, their bitwise exclusive or a ^ b is defined as follows, using their binary representations, composed of 0’s and 1’s.

a ^ b = a31…a1a0 ^ b31…b1b0 = c31…c1c0

where ci = ai xor bi (i = 0,1, … 31).

For instance, using binary notation, 11010110 ^ 01010101 = 10100011, or using hexadecimal, d6 ^ 55 = a3.

Since this kind of encryption is notoriously weak to statistical attacks, the message has to be compressed in advance, so that it has no statistical regularity. We suppose that N1 N2 . . .Nm is already in compressed form.

However, the trouble is that the compression algorithm itself introduces some form of regularity: after every 8 integers of compressed data, it inserts a checksum, the sum of these integers. That is, in the above input, N9 = N1 + . . . + N8, where additions are modulo 232.

Luckily, you could intercept a communication between the judges. Maybe it contains a problem for the finals!

As you are very clever, you have certainly seen that you can easily find the lowest bit of the key, denoted by K0. On the one hand, if K0 = 1, then after encoding, the lowest bit of ΣNi ^ K (i = 1,…8) is unchanged, as K0 is added an even number of times, but the lowest bit of N9 ^ K is changed,
so they shall differ. On the other hand, if K0 = 0, then after encoding, the lowest bit of ΣNi ^ K (i=1,…8) shall still be identical to the lowest bit of N9 ^ K, as they do not change. For instance, if the lowest bits after encoding are 1 1 1 1 1 1 1 1 1 then K0 must be 1, but if they are 1 1 1 1 1 1 1 0 1 then K0 must be 0.

So far, so good. Can you do better?

You should find the key used for encoding.

Input

The input starts with a line containing only a positive integer S, indicating the number of datasets in the input. S is no more than 1000.

It is followed by S datasets. Each dataset is composed of nine 32-bit integers corresponding to the first nine chunks of a communication. They are written in hexadecimal notation, using digits ‘0’ to ‘9’ and lowercase letters ‘a’ to ‘f’, and with no leading zeros. They are separated by a space or a newline. Each dataset is ended by a newline.

Output

For each dataset you should output the key used for encoding. Each key shall appear alone on its line, and be written in hexadecimal notation, using digits ‘0’ to ‘9’ and lowercase letters ‘a’ to ‘f’, and with no leading zeros.

Sample Input

8
1 1 1 1 1 1 1 1 8
3 2 3 2 3 2 3 2 6
3 4 4 7 7 b a 2 2e
e1 13 ce 28 ca 6 ab 46 a6d
b08 49e2 6128 f27 8cf2 bc50 7380 7fe1 723b
4eba eb4 a352 fd14 6ac1 eed1 dd06 bb83 392bc
ef593c08 847e522f 74c02b9c 26f3a4e1 e2720a01 6fe66007 7a4e96ad 6ee5cef6 3853cd88
60202fb8 757d6d66 9c3a9525 fbcd7983 82b9571c ddc54bab 853e52da 22047c88 e5524401

Output for the Sample Input

0
2
6
1c6
4924afc7
ffff95c5
546991d
901c4a16

Problem A
The Balance
—- 2004年 愛媛大会 —-

Ms. Iyo Ki a-Australis has a balance and only two kinds of weights to measure a dose of medicine.

For example, to measure 200mg of aspirin using 300mg weights and 700mg weights, she can put one 700mg weight on the side of the medicine and three 300mg weights on the opposite side (Figure 1). Although she could put four 300mg weights on the medicine side and two 700mg weights on the other (Figure 2), she would not choose this solution because it is less convenient to use more weights.

You are asked to help her by calculating how many weights are required.

Figure 1: To measure 200mg of aspirin using three 300mg weights and one 700mg weight

Figure 2: To measure 200mg of aspirin using four 300mg weights and two 700mg weights

Input

The input is a sequence of datasets. A dataset is a line containing three positive integers a, b, and d separated by a space. The following relations hold: a ≠ b, a <= 10000, b <= 10000, and d <= 50000. You may assume that it is possible to measure d mg using a combination of a mg and b mg weights. In other words, you need not consider “no solution” cases.

The end of the input is indicated by a line containing three zeros separated by a space. It is not a dataset.

Output

The output should be composed of lines, each corresponding to an input dataset (a; b; d). An output line should contain two nonnegative integers x and y separated by a space. They should satisfy the following three conditions.

  • You can measure d mg using x many a mg weights and y many b mg weights
  • The total number of weights (x + y) is the smallest among those pairs of nonnegative integers satisfying the previous condition.
  • The total mass of weights (ax + by) is the smallest among those pairs of nonnegative integers satisfying the previous two conditions.

No extra characters (e.g. extra spaces) should appear in the output.

Sample Input

700 300 200
500 200 300
500 200 500
275 110 330
275 110 385
648 375 4002
3 1 10000
0 0 0

Output for the Sample Input

1 3
1 1
1 0
0 3
1 1
49 74
3333 1

Problem D
Insecure in Prague
—- The 2004 ACM Programming Contest World Finals —-

Prague is a dangerous city for developers of cryptographic schemes. In 2001, a pair of researchers in Prague announced a security flaw in the famous PGP encryption protocol. In Prague in 2003, a flaw was discovered in the SSL/TLS (Secure Sockets Layer and Transport Layer Security) protocols. However, Prague’s reputation for being tough on cryptographic protocols hasn’t stopped the part-time amateur cryptographer and full-time nutcase, Immanuel Kant-DeWitt (known to his friends as “I. Kant-DeWitt”), from bringing his latest encryption scheme to Prague. Here’s how it works:
 「プラハは暗号開発者にとって厄介な都市。2001年、研究者ペアがプラハで、有名なPGP暗号プロトコルにセキュリティ脆弱性のあることを公表した。2003年プラハで、SSL/TLS (セキュアソケットレイヤとトランスポートレイヤセキュリティ)の脆弱性が見つけられた。しかし、暗号プロトコルの不幸に対するプラハの評判があっても、アマチュア暗号開発者であり、奇人であるImanuel Kant-DeWitt(仲間ではI. Kant-DeWittとして知られている)が自分の開発した最新の暗号をもってプラハにやってきた。その詳細は以下の通り。」

A plain text message p of length n is to be transmitted. The sender chooses an integer m >= 2n, and integers s, t, i, and j, where 0 <= s, t, i, j < m and i < j. The scheme works as follows: m is the length of the transmitted ciphertext string, c. Initially, c contains m empty slots. The first letter of p is placed in position s of c. The kth letter, k >= 2, is placed by skipping over i empty slots in c after the (k-1)st letter, wrapping around to the beginning of c if necessary. Slots already containing letters are not counted as empty. For instance, if the message is PRAGUE, if s = 1, i = 6, and m = 15, then the letters are placed in c as follows:
 「長さnの平文テキストメッセージpを送ろうとする。送信者は整数m (m>=2n)、及び整数 s, t, i, j (0 <= s, t, i, j < m、i < j) を選ぶ。仕組みはこうは。mは送られた暗号文字列cの長さ。初期状態では、cにm個の空スロットを含む。pの最初の文字はcの位置sに置く。k (k >= 2) 番目の文字は、k-1番目の文字からi個の空スロットをスキップしたところに置く。必要であれば、cの先頭に戻ってもよい。文字の入ったスロットは空スロットとしてはカウントしない。例えば、メッセージがPRAGUEだとして、s = 1, i = 6, m = 15とすると、各文字はcに次のように置くことになる。」

Starting with the first empty slot in or after position t in string c, the plain text message is entered again, but this time skipping j empty slots between letters. For instance, if t = 0 and j = 8, the second copy of p is entered as follows (beginning in position 2, the first empty slot starting from t = 0):
 「文字列cについて、位置tのところ(そこが空スロットでなければそれ以降)の最初の空スロットから、平文テキストメッセージをもう一度入れる。ただし、今回は文字間の空スロットj個をスキップことにする。例えば、t = 0、j = 8とすると、pの2回目のコピーは以下になる(t=0からの最初の空スロットである、位置2より始まる)。」

Finally, any remaining unfilled slots in c are filled in with randomly chosen letters:
 「最後に、残りの空スロットに、ランダムに文字を選んで埋め込めばよい。」

Kant-DeWitt believes that the duplication of the message, combined with the use of random letters, will confuse decryption schemes based upon letter frequencies and that, without knowledge of s and i, no one can figure out what the original message is. Your job is to try to prove him wrong. Given a number of ciphertext strings (and no additional information), you will determine the longest possible message that could have been encoded using the Kant-DeWitt method.
 「ランダムに文字が組み込まれたメッセージの2重化によって、文字の出現頻度に基づく解読や、sとiの知識がなしに元の文字列を知ることはできないとKant-DeWitt believesは信じているが、彼の間違いを証明してほしい。複数の暗号文字列に対し、追加情報なしに、Kant-DeWitt方式で暗号化された最長のありうる文字列を決めて欲しい。」

Input
A number of ciphertext strings, one per line. Each string will consist only of upper case alphabetic letters, with no leading or trailing blanks; each will have length between 2 and 40. Input for the last test case is followed by a line consisting of the letter X.
 「1行ずつ、複数の暗号文字列が入力として与えられる。各文字列はアルファベット大文字のみを含み、空白文字は行頭や行末にない。文字列の長さは2から40。入力の最後に文字Xの行が入る。」

Output
For each input ciphertext string, print the longest string that could be encrypted in the ciphertext. If more than one string has the longest length, then print “Codeword not unique”. Follow the format of the sample output given below.
 「各暗号文字列に対し、その文字列に暗号化された最長文字列を表示すること。同じ長さの文字列が複数ある場合、”Codeword not unique”と表示すること。サンプル出力のフォーマットに従うこと。」

Sample Input
APPURAAURGEGEWE
ABABABAB
THEACMPROGRAMMINGCONTEST
X

Output for the Sample Input
Code 1: PRAGUE
Code 2: Codeword not unique
Code 3: Codeword not unique

Problem C
Image Is Everything
—- The 2004 ACM Programming Contest World Finals —-

Your new company is building a robot that can hold small lightweight objects. The robot will have the intelligence to determine if an object is light enough to hold. It does this by taking pictures of the object from the 6 cardinal directions, and then inferring an upper limit on the object’s weight based on those images. You must write a program to do that for the robot.
 「新しい会社が小さな軽量物体を持ち上げられるロボットを組み立てている。このロボットは物体の重さを知的に判別することができる。つまり、6方向から物体の写真を撮り、これらのイメージから重さの上限を推測するのだ。ロボット用のこのプログラムを作って欲しい。」

You can assume that each object is formed from an N×N×N lattice of cubes, some of which may be missing. Each 1×1×1 cube weighs 1 gram, and each cube is painted a single solid color. The object is not necessarily connected.
 「物体は N×N×N 立方体の格子状になっていて、いくつかは欠けているかもしれない。1×1×1 立方体の重さは1グラム。各立方体はそれぞれ、一色で塗られている。物体はつながる必要がない。」

Input
The input for this problem consists of several test cases representing different objects. Every case begins with a line containing N, which is the size of the object (1<=N<=10). The next N lines are the different N×N views of the object, in the order front, left, back, right, top, bottom. Each view will be separated by a single space from the view that follows it. The bottom edge of the top view corresponds to the top edge of the front view. Similarly, the top edge of the bottom view corresponds to the bottom edge of the front view. In each view, colors are represented by single, unique capital letters, while a period (.) indicates that the object can be seen through at that location.
 「入力に異なる物体を表す複数のテストケースが含まれる。各テストケースはNが入る行から始まる。N (1<=N<=10) は物体のサイズを表す。つぎのN行は、前(front)・左(left)・後(back)・右(right)・真上(top)・真下(bottom)からみた、物体の N×N ビューが入る。各ビューの間にスペース1文字が入る。トップ(top、真上)ビューの底辺がフロント(front、前)ビューの上辺と一致するのと同様、ボトム(bottom、真下)ビューの上辺がフロントビューの底辺と一致する。各ビューにおいて、色は大文字1文字で表し、ピリオド(.) はあの位置からは物体が通り抜けて見えることを表す。」

Input for the last test case is followed by a line consisting of the number 0.
 「入力の最後に数字0の行が入る。」

Output
For each test case, print a line containing the maximum possible weight of the object, using the format shown below.
 「各テストケースに対し、物体の可能な最大重さを表示する。出力フォーマットを活用すること。」

Sample Input
3
.R. YYR .Y. RYY .Y. .R.
GRB YGR BYG RBY GYB GRB
.R. YRR .Y. RRY .R. .Y.
2
ZZ ZZ ZZ ZZ ZZ ZZ
ZZ ZZ ZZ ZZ ZZ ZZ
0

Output for the Sample Input
Maximum weight: 11 gram(s)
Maximum weight: 8 gram(s)

多角形の中に入れる最大円を探し出すプログラム。

Problem B
Heliport
—- The 2004 ACM Programming Contest World Finals —-

In these fast-paced times, companies are investing in heliports to reduce travel time for their busy executives. The heliports are typically circular landing pads, constructed on the roofs of the companies’ headquarters. You must write a program that finds the largest radius for a circular heliport that can be constructed on the flat roof of a building that is in the form of a simple polygon. Since this is merely the design phase of the construction effort, your program must find only the radius of the heliport. The maximum radius for a heliport in the diagram shown is 10.
 「あっという間に時間が過ぎていく今日、多忙な役員達の移動時間を節約するため、会社はヘリポートへの投資を行っている。ヘリポートは一般的に円状の離着陸場であり、本社の屋上に建てられる。単純多角形の形をしている平らなビルの屋上に、円状ヘリポートを建設するよう、最大半径を見つけ出すプログラムを書いて欲しい。建設の設計段階にすぎないので、プログラムはヘリポートの半径を見つけ出すだけでよい。図に示したヘリポートの最大半径は10である。」

Input File
The input file contains several test cases. Each test case consists of two lines. The first line consists of an even integer n (4<=n<=20), which is the number of the sides of the building. The second line consists of n pairs of the form (m, d), where m is an integer (1<=m<=50) and d is a letter (U, R, D, L). Assuming the roof is drawn on the Cartesian plane, m is the length of a roof boundary segment and d is the direction of that segment as you travel counterclockwise around the roof. U, R, D, and L mean “Up,” “Right,” “Down,” and “Left。” respectively. The boundary segments of the roof, which are parallel to the x and y axes, are given in counterclockwise order. The starting position is the origin (0, 0). Input for the last test case is followed by a line consisting of the number 0.
 「入力ファイルに複数のテストケースが含まれる。各々のテストケースは2行を含む。1行目には偶数である整数 n (4<=n<=20)が入り、ビルの辺の数を表す。2行目には、n個の(m, d)ペアが入る。m ((1<=m<=50)は整数、dは文字(U, R, D, L)のどれか。屋上はデカルト平面に描かれ、mは屋上の端を表す線分の長さ、dは屋上を反時計回りで見たときの線分の方向を表す。U, R, D, Lはそれぞれ、上、右、下、左を示す。屋上の端となる線分は、x, y 軸と平行していて、反時計方向の順で与えられ、原点(0, 0)から始まる。入力の最後に数字0の行が入る。」

Output File
For each test case, the output consists of a separate line containing the case number (starting with 1) and a real number (rounded to two digits after the decimal point) representing the radius of the heliport. Print a blank line between cases as shown in the sample output.
 「各テストケースに対し、ケース番号(1からスタート)、およびヘリポートの半径を示す実数(小数点右2桁まで)をぞれぞれの行に出力すること。サンプル出力にあるように、テストケースの間に空白行を入れること。」

Sample Input
4
2 R 2 U 2 L 2 D
10
10 R 10 U 10 L 10 U 10 R 5 U 30 L 20 D 20 R 5 D
0

Output for the Sample Input
Case Number 1 radius is: 1.00

Case Number 2 radius is: 10.00

ジグザグに動く蟻たちの走行時間を算出するプログラム。

Problem A
Carl the Ant
—- The 2004 ACM Programming Contest World Finals —-

Ants leave small chemical trails on the ground in order to mark paths for other ants to follow. Ordinarily these trails follow rather straight lines. But in one ant colony there is an ant named Carl, and Carl is not an ordinary ant. Carl will often zigzag for no apparent reason, sometimes crossing his own path numerous times in the process. When other ants come to an intersection, they always follow the path with the strongest scent, which is the most recent path that leads away from the intersection point.
 「ほかの蟻の道しるべになるので、蟻は通った道に臭跡を残している。ふつう、これらの臭跡がそこそこの直線になるが、ひとつだけ、カールと呼ばれる蟻だけは特別。理由不明だが、カール蟻はジグザグに動き、本来の道を何度も途中で横切ったりする。他の蟻が交差点に来ると、最も臭いの強い道、つまり、交差点から最後にできた道、に進む。」

Ants are 1 centimeter long, move and burrow at 1 centimeter per second, and follow their paths exactly (bending at right angles when moving around corners). Ants cannot cross or overlap each other. If two ants meet at the exact same instant at an intersection point, the one that has been on Carl’s path the longest has the right of way; otherwise, the ant that has been waiting the longest at an intersection will move first.
 「蟻は長さが1cm、動くのももぐるのも1秒当たり1cmのスピード。また精確に道を沿って進む(コーナーのところでは直角に曲がる)。ほかの蟻を追い越したり、オーバーラップしたりすることはない。蟻2つが交差点で出くわしたら、最も長くカール蟻が歩いた道にいた蟻が優先的に動く。あるいは、最も長く交差点で待たされた蟻が先に動く。」

Carl burrows up from the ground to start at the origin at time 0. He then walks his path and burrows back down into the ground at the endpoint. The rest of the ants follow at regular intervals. Given the description of Carl’s path and when the other ants start the path, you are to determine how long it takes the entire set of ants to finish burrowing back into the ground. All the ants are guaranteed to finish.
 「カール蟻は土の中から現われて原点の位置から、時間0よりスタート。カールは道を歩き、終点のところで再び土に戻る。他の蟻は同じ時間間隔でつぎつぎと現われてくる。カール蟻の歩く道、および他の蟻のスタート時間が与えられるものとして、すべての蟻が歩き終え、土に戻るまでの時間を計算して欲しい。すべての蟻は途中で止めることはない。」

Input

Input consists of several test cases. The first line of the input file contains a single integer indicating the number of test cases.
 「入力に複数のテストケースが含まれる。入力ファイルの1行目にテストケースの数を示す整数が1つ入る。」

The input for each test case starts with a single line containing three positive integers n (1<=n<=50), m (1<=m<=100), and d (1<d<100). Here, n is the number of line segments in Carl’s path, m is the number of ants traveling the path (including Carl), and d is the time delay before each successive ant’s emergence. Carl (who is numbered 0) starts at time 0. The next ant (ant number 1) will emerge at time d, the next at time 2d, and so on. If the burrow is blocked, the ants will emerge as soon as possible in the correct order.
 「各テストケースでは、最初に3つの正整数 n (1<=n<=50), m (1<=m<=100), および d (1<d<100) を含む行が入る。n はカール蟻が歩く道を示す線分の数、m はカールを含む蟻の数、d は個々の蟻が現われてくる遅延時間。カール(番号0)は時間0からスタート。つぎの蟻(番号1)は時間dに現われる、そのつぎは時間2d、等。穴の出口が塞がれたら、決められた順番で可能になった時点で蟻が外に出てくる。」

Each of the next n lines for the test case consists of a unique integer pair x y (-100<x, y<100), which is the endpoint of a line segment of Carl’s path, in the order that Carl travels. The first line starts at the origin (0,0) and the starting point of every subsequent line is the endpoint of the previous line.
 「つぎのn行に、異なる整数ペア x y (-100<x, y<100) が入る。x, y ペアはカール蟻が歩く道である線分の終点を表し、カール蟻が歩く道順と一致する。最初の線分は原点 (0, 0)からスタートし、その後に続く線分は起点が前の線分の終点と重なる。」

For simplicity, Carl always travels on line segments parallel to the axes, and no endpoints lie on any segment other than the ones which they serve as an endpoint.
 「簡単にするため、カールは座標軸と並行な線分を歩き、終点と見なすもの以外に、線分上に終点がないと仮定してよい。」

Output

The output for each case is described as follows:
 「各ケースの出力は以下になる。」

Case C:
Carl finished the path at time t1
The ants finished in the following order: 
a1 a2 a3 … am
The last ant finished the path at time t2
 「ケース C:
  カールは時間t1で走行終了。
  蟻はつぎの順番で終了:
  a1 a2 a3 … am
  最後の蟻は時間t2で走行終了。」

Here, C is the case number (starting at 1), a1, a2, a3, … am are the ant numbers in the order that they go back underground, and t1 and t2 are the times (in seconds) at which Carl and the last ant finish going underground. You should separate consecutive cases with a single blank line.
 「Cはケース番号(1からのスタート)、a1, a2, a3, … am は土に戻る蟻の番号順、t1, t2は時間(秒単位)、カールと最後の蟻が土に戻る時間。各ケースの間に空白行を入れること。」

Sample Input

2
4 7 4
0 4
2 4
2 2
-2 2
4 7 2
0 4
2 4
2 2
-2 2

Output for the Sample Input

Case 1:
Carl finished the path at time 13
The ants finished in the following order:
0 2 1 3 4 5 6
The last ant finished the path at time 29

Case 2:
Carl finished the path at time 13
The ants finished in the following order:
0 4 1 5 2 6 3
The last ant finished the path at time 19