通行料を安くする最適ルートを探し出すプログラム。

Problem J
Toll
—- The 2003 ACM Programming Contest World Finals —-

Sindbad the Sailor sold 66 silver spoons to the Sultan of Samarkand. The selling was quite easy; but delivering was complicated. The items were transported over land, passing through several towns and villages. Each town and village demanded an entry toll. There were no tolls for leaving. The toll for entering a village was simply one item. The toll for entering a town was one piece per 20 items carried. For example, to enter a town carrying 70 items, you had to pay 4 items as toll. The towns and villages were situated strategically between rocks, swamps and rivers, so you could not avoid them.
 「シンドバッドがサマルカンドのサルタンにシルバースプーン66本を売りつけた。売るのは簡単だったけど、配達は大変。アイテムは陸路で運ばれ、いくつかの町と村を通らないといけなかった。すべての町と村では、入る時に通行料が必要だった。ただ、去るときは通行料はいらない。村の通行料は単に1アイテム。町の通行料は20アイテムにつき1つ。例えば、70アイテムをもって町に入ろうとしたら、4アイテムを通行料として支払わないといけない。町、村は岩や沼地、川の間の戦略要所にあり、避けて通ることはできない。」

Figure 1: To reach Samarkand with 66 spoons, traveling through a town followed by two villages, you must start with 76 spoons.
 「図1:町1つ、村2つを通った後に、66本のスプーンをサマルカンドに送り届けるには、76本のスプーンをもって出発しないといけない。」

Figure 2: The best route to reach X with 39 spoons, starting from A, is A→b→c→X, shown with arrows in the figure on the left. The best route to reach X with 10 spoons is A→D→X, shown in the figure on the right. The figures display towns as squares and villages as circles.
 「図2:39本のスプーンをX地点に送り届けるベストルートは、左図の矢印通り、A地点から A→b→c→X というもの。10本のスプーンなら、右図のように、A→D→X がベストルート。図に四角は町、円は村を表す。」

Predicting the tolls charged in each village or town is quite simple, but finding the best route (the cheapest route) is a real challenge. The best route depends upon the number of items carried. For numbers up to 20, villages and towns charge the same. For large numbers of items, it makes sense to avoid towns and travel through more villages, as illustrated in Figure 2.
 「各町や村に徴収される通行料を予測するのは簡単だけど、ベストルート(もっとも安いルート)を探し出すのは難しい。ベストルートが運ぶアイテムの数に依存するから。20本までなら、町も村も通行料が同じ。アイテムの量が多くなると、図2のように、町を避けて、数的に多くても村を選ぶのが賢明だろう。」

You must write a program to solve Sindbad’s problem. Given the number of items to be delivered to a certain town or village and a road map, your program must determine the total number of items required at the beginning of the journey that uses a cheapest route.
 「このシンドバッド問題を解くプログラムを書いて欲しい。目的地に届けるべきアイテムの本数とロードマップが与えられたものとして、プログラムは最も安いルートを利用するときの、出発時に必要なアイテム本数を算出しないといけない。」

Input
The input consists of several test cases. Each test case consists of two parts: the roadmap followed by the delivery details.
 「入力に複数のテストケースが含まれる。各テストケースは2つの部分、つまり、ロードマットと配達任務、からなる。」

The first line of the roadmap contains an integer n, which is the number of roads in the map (0 <= n). Each of the next n lines contains exactly two letters representing the two endpoints of a road. A capital letter represents a town; a lower case letter represents a village. Roads can be traveled in either direction.
 「ロードマップの1行目に整数nが入る。n (0<=n) マップにある道の数を示す。つぎのn行に、道の両端を表す2文字が入る。大文字は町、小文字は村を意味する。道は双方通行可能。」

Following the roadmap is a single line for the delivery details. This line consists of three things: an integer p (0 < p <= 1000) for the number of items that must be delivered, a letter for the starting place, and a letter for the place of delivery. The roadmap is always such that the items can be delivered.
 「ロードマップのつぎにある1行は配達任務を示す。その行は3つのこと、すなわち、整数p (0<p<=1000) 届けるアイテムの本数、出発地となる文字、目的地となる文字、が書かれる。ルートマップは配達可能なものだ。」

The last test case is followed by a line containing the number -1.
 「入力の最後に -1 が入る。」

Output
The output consists of a single line for each test case. Each line displays the case number and the number of items required at the beginning of the journey. Follow the output format in the example given below.
 「出力に、各テストケースに対応する1行をそれぞれ書くこと。各行にテストケースの番号と、出発時に必要なアイテム数を表示すること。サンプル出力データのフォーマットに従うこと。」

Sample Input
1
a Z
19 a Z
5
A D
D X
A b
b c
c X
39 A X
-1

Output for the Sample Input
Case 1: 20
Case 2: 44

Problem I
The Solar System
—- The 2003 ACM Programming Contest World Finals —-

It is common knowledge that the Solar System consists of the sun at its center and nine planets moving around the sun on elliptical orbits. Less well known is the fact that the planets’ orbits are not at all arbitrary. In fact, the orbits obey three laws discovered by Johannes Kepler. These laws, also called “The Laws of Planetary Motion,” are the following.
 「一般的な知識として、太陽系は中心に太陽があり、その周りに9個の惑星が楕円軌道に沿って動いている。しかし、惑星の軌道が勝手に決まるものではないことはあまり知られていない。事実、軌道はJ.ケプラーによって発見された3つの法則に従う。惑星運動法則とも呼ばれているこれらの法則は以下のようなもの。」

  1. The orbits of the planets are ellipses, with the sun at one focus of the ellipse. (Recall that the two foci of an ellipse are such that the sum of the distances to them is the same for all points on the ellipse.)

     「惑星の軌道は、太陽を1つの焦点とする楕円である。(楕円の2つの焦点とは、焦点から楕円上の任意の点までの距離の和がつねに同じというもの。)

  2. The line joining a planet to the sun sweeps over equal areas during equal time intervals as the planet travels around the ellipse.

     「楕円上で動く惑星は、時間間隔が同じであれば、惑星と太陽と繋ぐ線が同じ面積を掃いて行く。」

  3. The ratio of the squares of the revolutionary periods of two planets is equal to the ratio of the cubes of their semi major axes.

     「2つの惑星の公転周期の2乗の比は、それらの半長軸の3乗の比と等しい。」

By Kepler’s first law, the path of the planet shown in the figure on the left is an ellipse. According to Kepler’s second law, if the planet goes from M to N in time tA and from P to Q in time tB and if tA= tB, then area A equals area B. Kepler’s third law is illustrated next.
 「ケプラーの第1法則により、左側の図に書かれた惑星の経路は楕円となる。ケプラーの第2法則により、惑星がMからNまでの時間をtA、PからQまでの時間をtBとし、tA=tBとするならば、面積Aは面積Bと等しくなる。ケプラーの第3法則については以下で説明する。

Consider an ellipse whose center is at the origin O and that is symmetric with respect to the two coordinate axes. The x-axis intersects the ellipse at points A and B and the y-axis intersects the ellipse at points C and D. Set a=½|AB| and b=½|CD|. Then the ellipse is defined by the equation x2/a2+y2/b2=1. If a>=b, AB is called the major axis, CD the minor axis, and OA (with length a) is called the semi major axis. When two planets are revolving around the sun in times t1 and t2 respectively, and the semi major axes of their orbits have lengths a1 and a2, then according to Kepler’s third law (t1/t2)2 = (a1/a2)3.
 「中心が原点Oにあり、両軸に対称的な楕円を考えよう。x軸と楕円との交点をA, B、y軸と楕円との交点をC, Dとし、a=½|AB|、b=½|CD| とすると、楕円は方程式 x2/a2+y2/b2=1で定義される。a>bならば、ABは長軸、CDは短軸といい、長さaのOAは半長軸という。2つの惑星が太陽を公転する時間をt1、t2とし、軌道の半長軸の長さを a1、a2とすると、ケプラーの第3法則により、(t1/t2)2 = (a1/a2)3 となる。

In this problem, you are to compute the location of a planet using Kepler’s laws. You are given the description of one planet in the Solar System (i.e., the length of its semi-major axis, semi-minor axis, and its revolution time) and the description of a second planet (its semi-major axis and semi-minor axis). Assume that the second planet’s orbit is aligned with the coordinate axes (as in the above figure), that it moves in counter clockwise direction, and that the sun is located at the focal point with non-negative x-coordinate. You are to compute the position of the second planet a specified amount of time after it starts at the point with maximal x-coordinate on its orbit (point B in the above figure).
 「ケプラーの法則に用いて惑星の位置を計算してほしい。太陽系にあるある惑星に関する記述(半長軸、半短軸の長さや、公転周期の時間等)、および、2つ目の惑星についての記述(半長軸と半短軸の長さ)が与えられる。2つ目の惑星の軌道が上図で示した座標軸に合うものとする。つまり、その惑星は反時計方向に動き、太陽が負でないx座標の焦点に位置する。軌道上の最大x座標をもつ点(上図のB点)からスタートして決められた時間を経過した後の、2番目の惑星の位置を計算すること。」

Input
The input file contains several descriptions of pairs of planets. Each line contains six integers a1, b1, t1, a2, b2, t. The first five integers are positive, and describe two planets as follows:
  「入力にペアとなる惑星に関する複数の記述が与えられる。各行に6つの整数、a1, b1, t1, a2, b2, t が含まれる。最初の5つは正数、ふたつの惑星に関する説明である。」

    a1 = semi major axis of the first planet’s orbit (惑星1つ目の軌道の半長軸)
    b1 = semi minor axis of the first planet’s orbit (惑星1つ目の軌道の半短軸)
    t1 = period of revolution of the first planet (in days) (惑星1つ目の公転周期(日単位)
    a2 = semi major axis of the second planet’s orbit (惑星2つ目の半長軸)
    b2 = semi minor axis of the second planet’s orbit (惑星2つ目の半短軸)

The non-negative integer t is the time (in days) at which you have to determine the position of the second planet, assuming that the planet starts in position (a2,0).
 「非負の整数 t は2つ目の惑星の位置を決める時間(日単位)。惑星は位置 (a2, 0) からスタートと仮定してよい。」

The last description is followed by a line containing six zeros.
 「入力の最後に6つの0が入る。」

Output
For each pair of planets described in the input, produce one line of output. For each line, print the number of the test case. Then print the x- and y-coordinates of the position of the second planet after t days. These values must be exact to three digits to the right of the decimal point. Follow the format of the sample output provided below.
 「入力に記述される惑星のペアに対し、それぞれ1行ずつ出力すること。各行にテストケースの番号、t日後の2つ目の惑星のx, y 座標位置。値は小数点右3桁にすること。出力サンプルのフォーマットを利用すること。」

Sample Input
10 5 10 10 5 10
10 5 10 20 10 10
0 0 0 0 0 0

Output for the Sample Input
Solar System 1: 10.000 0.000
Solar System 2: -17.525 4.819

Problem G
A Linking Loader
—- The 2003 ACM Programming Contest World Finals —-

An object module is produced by a compiler as a result of processing a source program. A linking loader (or just a linker) is used to combine the multiple object modules used when a program contains several separately compiled modules. Two of its primary tasks are to relocate the code and data in each object module (since the compiler does not know where in memory a module will be placed), and to resolve symbolic references from one module to another. For example, a main program may reference a square root function called sqrt, and that function may be defined in a separate source module. The linker will then minimally have to assign addresses to the code and data in each module, and put the address of the sqrt function in the appropriate location(s) in the main module’s code.
 「ソースプログラムを処理した結果として、オブジェクトモジュールがコンパイラからつくり出される。別々にコンパイルされたモジュールを複数個含むプログラムの場合、これらのモジュールを結合するのにリンクローダ(リンカ)が使われる。リンカに基本的な役割が二つあり、ひとつ目は個々のモジュール内のコードとデータを再配置すること。(コンパイラがメモリのどこにモジュールが置かれるか知らないから。)二つ目はモジュール同士のシンボルの参照を解決すること。例えば、メインプログラムがsqrtという名前の平方根関数を参照としようとしていて、その関数が他のソースモジュールに定義されているとする。そこで、リンカは少なくとも、個々のモジュールのコードとデータにアドレスを割り当てないといけないし、sqrt関数のアドレスをメインモジュールコード内の適正箇所に書き込まないといけない。」

An object module contains (in order) zero or more external symbol definitions, zero or more external symbol references, zero or more bytes of code and data (that may include references to the values of external symbols), and an end of module marker. In this problem, an object module is represented as a sequence of text lines, each beginning with a single uppercase character that characterizes the remainder of the line. The format of each of these lines is as follows. Whitespace (one or more blanks and/or tab characters) will appear between the fields in these lines. Additional whitespace may follow the last field in each line.
 「オブジェクトモジュールは、順序として以下のものを含む、外部シンボル定義、外部シンボル参照、コードおよびデータ(外部シンボルの値を参照するかもしれない)、モジュールの終了記号。本問題では、オブジェクトモジュールはテキスト行として表現する。各行の先頭にアルファベット大文字の1字が入り、行の意味を決める。各行のフォーマットが以下の通り。ホワイトスペース(ひとつあるいはそれ以上のブランク文字かタブ文字)がフィールドの間に存在するかもしれない。また、各行の最後のフィールドの後ろにもホワイト文字があるかもしれない。」

  • A line of the form “D symbol offset” is an external symbol definition. It defines symbol as having the address offset bytes greater than the address where the first byte of code and data for the current object module is located by the linker. A symbol is a string of no more than eight upper case alphabetic characters. The offset is a hexadecimal number with no more than four digits (using only upper case alphabetic characters for the digits A through F). For example, in a module that is loaded starting at the address 10016, the line “D START 5C” indicates that the symbol START is defined as being associated with the address 15C16. The number of D lines in a test case is at most 100.
     「”D symbol offset”は外部シンボル定義の行。リンカによって配置された本モジュールのコードやデータに対し、そのスタートアドレスからのオフセット(バイト単位)アドレスを有するシンボルを定義する。シンボルは大文字8字以内の文字列。オフセットは4桁以内の16進数(A~Fには大文字しか使わない)。例えば、10016のアドレスからスタートするモジュールに対し、行”D START 5C”はアドレス15C16をもつものとしてシンボルSTARTを表す。D行の行数はテストケースでは最大100行まで。」

  • A line of the form “E symbol” is an external symbol reference, and indicates that the value of symbol (presumably defined in another object module) may be referenced as part of the code and data for the current module. For example, the line “E START” indicates that the value of the symbol START (that is, the address defined for it) may be used as part of the code and data for the module. Each of the “E” lines for each module is numbered sequentially, starting with 0, so they can be referenced in the “C” lines.
     「“E symbol”は外部シンボル参照の行。本モジュールのコードやデータの一部として参照されるシンボル(ほかのモジュールに定義されている)の値を示す。例えば、“E START”という行は、モジュールのコードとデータの一部としてシンボルSTARTの値(つまり、定義されたアドレス)が使われることを表す。各モジュールの各E行は、0からスタートする通し番号として番号づけられるので、 “C”行参照されることが可能。」

  • A line of the form “C n byte1 byte2 … byten” specifies the first or next n bytes of code and data for the current module. The value n is specified as a one or two digit hexadecimal number, and will be no larger than 10 hexadecimal. Each byte is either a one or two digit hexadecimal number, or a dollar sign. The first byte following a dollar sign (always on the same line) gives the 0-origin index of an external symbol reference for this module, and identifies the symbol which is to have its 16-bit value inserted at the current point in the linked program (that is, in the location indicated by the dollar sign and the following byte). The high-order byte is placed in the location indicated by the dollar sign. The values specified for the other bytes (those not following a dollar sign) are loaded into sequential memory locations, starting with the first (lowest) unused memory location. For example, the line “C 4 25 $ 0 37” would cause the values 2516 0116 5C16 and 3716 to be placed in the next four unused memory locations, assuming the first “E” line for the current module specified a symbol defined as having the address 15C16. If the 0-origin index of the external symbol reference is an undefined symbol, the 16-bit value inserted at the current point in the linked program is 000016.
     「 “C n byte1 byte2 … byten”は、本モジュールのコードとデータの最初またはそのつぎのnバイトを表す。値nは16進数の1桁ないし2桁、16進数10を超えることはない。個々のバイトも同様に1桁ないし2桁の16進数、あるいは、ドル記号($)のどちらだ。ドル記号の後に続く最初の1バイト(ドル記号とつねに同じ行にある)は本モジュールの外部シンボル参照のインデックス(0から)を示す。リンクが行われたとき、シンボルの16ビット値をここに、つまり、ドル記号とそれに続く1バイトの示す位置に、書き込まないといけない。上位バイトがドル記号の位置に書き込む。ドル記号の後に続く1バイト以外のものについて、その値がそのまま、未使用メモリの低いほうのスタート位置に転送される。例えば、“C 4 25 $ 0 37”の行は、次の4つの未使用メモリに、値2516 0116 5C16 3716を置くことを表す。ただし、本モジュールの最初のE行にアドレス15C16をもつシンボルを記述しているとする。0からスタートする外部シンボル参照のインデックスが未定義シンボルになってしまったときに、リンク時に書き込まれた16ビットの値は000016となる。」

  • A line of the form “Z” marks the end of an object module.
     「“Z”行はモジュールの終了マーク。」

You may assume that no address requires more than four hexadecimal digits. Lines are always given in the order shown above. There are no syntax errors in the input.
 「16進数4桁以上のアドレスは必要としない。行の並びはつねに上に説明した順序であり、入力にシンタックスエラーはないものとする。」

Input
This problem has multiple input cases. The input for each case is one or more object modules, in sequence, that are to be linked, followed by a line beginning with a dollar sign. The first address at which code is to be loaded in each case is 10016.
 「本問題に複数の入力ケースを含む。個々のケースにおいて、順次に、リンクすべき1つあるいは複数のモジュールが与えられ、終わりに先頭ドル($)記号の行が入る。すべてのケースにおいて、コードのスタートアドレスは10016だ。

The last case will be followed by a line containing only a dollar sign.
 「最後のケースの後に、ドル記号だけを含む行が入る。」

Output
For each case, print the case number (starting with 1), the 16-bit checksum of the loaded bytes (as described below), and the load map showing the address of each externally defined or referenced symbol, in ascending order of symbol name. For undefined symbols, print the value as four question marks, but use zero as the symbol’s value when it is referenced in “C” lines. If a symbol is defined more than once, print “M” following the address shown in the load map, and use the value from the first definition encountered in any object module to satisfy external references. Format the output exactly as shown in the samples.
 「個々のケースに対し、1からスタートするケース番号(case number)、転送されるバイトの16ビットチェックサム(詳細は下に述べる)、個々の外部定義、外部参照シンボルのアドレスを示すロードマップを表示すること。シンボル名は昇順で並ぶこと。未定義シンボルについては、値として4つの「?」記号を表示することだが、 “C”行に参照されるシンボルの値としては0を使うこと。シンボルが1回以上定義された場合、ロードマップに示すアドレスの後に “M”を表示すること。その値は外部参照を満たす、最初のモジュールにある定義によるものとすること。サンプルデータのフォーマットに従うこと。」

The 16-bit checksum is computed by first setting it to zero. Then, for each byte assigned to a memory location by the loader, in increasing address order, circularly left shift the checksum by one bit, and add the byte from the memory location, discarding any carry out of the low-order 16 bits.
 「16ビットチェックサムは次のように計算する。初期値は0。アドレスの昇順でメモリに転送される各バイトに対し、チェックサムを1ビット左に循環シフトしてから、そのバイトと加算を行い、下位16ビットからのキャリアを切り捨てる。」

Sample Input
D MAIN 0
D END 5
C 03 01 02 03
C 03 04 05 06
Z
$
D ENTRY 4
E SUBX
E SUBY
C 10 1 2 3 4 5 $ 0 6 7 8 9 A B C D E
C 8 10 20 30 40 50 60 70 80
C 8 90 A0 B0 C0 D0 E0 $ 1
C 5 $ 0 FF EE DD
Z
D SUBX 01
C 06 A B C D E F
Z
D SUBX 05
C 06 51 52 53 54 55 56
Z
$
$

Output for the Sample Input
出力サンプルに正確に従えとの指示なので、右のグラフを
参考すること。

Case 1: checksum = 0078
 SYMBOL    ADDR
——–     —-
END         0105
MAIN        0100

Case 2: checksum = 548C
 SYMBOL     ADDR
——–      —-
ENTRY        0104
SUBX          0126 M
SUBY          ????

Problem F
Combining Images
—- The 2003 ACM Programming Contest World Finals —-

As the exchange of images over computer networks becomes more common, the problem of image compression takes on increasing importance. Image compression algorithms are used to represent images using a relatively small number of bits.
 「コンピュータネットワークにおいて、イメージ画像がより多く使われ、その圧縮の重要度が増している。より少ないビット数で画像を表現するにはイメージ圧縮アルゴリズムが使われる。」

One image compression algorithm is based on an encoding called a “Quad Tree.” An image has a Quad Tree encoding if it is a square array of binary pixels (the value of each pixel is 0 or 1, called the “color” of the pixel), and the number of pixels on the side of the square is a power of two.
 「イメージ圧縮アルゴリズムのひとつに4分木(Quad Tree)による表現方法がある。イメージを4分木表現で表現できるのは、イメージが 0か1の値(モノクロ)をもつバイナリピクセルの正方形配列でつくられ、各辺のピクセルの数が2のべき乗になる場合だ。

If an image is homogeneous (all its pixels are of the same color), the Quad Tree encoding of the image is 1 followed by the color of the pixels. For example, the Quad Tree encoding of an image that contains pixels of color 1 only is 11, regardless of the size of the image.
 「イメージが同色の場合、4分木表現は1とそれに続くピクセルの色となる。たとえば、黒一色のイメージの表現は11であり、イメージのサイズと関係ない。」

If an image is heterogeneous (it contains pixels of both colors), the Quad Tree encoding of the image is 0 followed by the Quad Tree encodings of its upper-left quadrant, its upper-right quadrant, its lower-left quadrant, and its lower-right quadrant, in order.
 「イメージが白黒両方をもつ場合、4分木表現は0に続き、左上、右上、左下、右下の四箇所のそのさらなる4分木表現によって表される。」

The Quad Tree encoding of an image is a string of binary digits. For easier printing, a Quad Tree encoding can be converted to a Hex Quad Tree encoding by the following steps:
  a. Prepend a 1 digit as a delimiter on the left of the Quad Tree encoding.
  b. Prepend 0 digits on the left as necessary until the number of digits is a multiple of four.
  c. Convert each sequence of four binary digits into a hexadecimal digit, using the digits 0 to 9 and capital A through F to represent binary patterns from 0000 to 1111.
 「イメージの4分木表現は2進数列になる。見やすくするため、つぎの方法で16進4分木表現に変換できる。
  a. 4分木表現の左側に区切りとしてビット1をつける。
  b. ビット数が4の倍数になるまで、ビット0を左につける。
  c. 4ビットずつ16進数に変換する。ビットパターン0000~1111に0~9と大文字A~Fを使う。」

For example, the Hex Quad Tree encoding of an image that contains pixels of color 1 only is 7, which corresponds to the binary string 0111.
 「たとえば、黒一色だけのイメージの4分木表現は7であり、2進数列 0111に対応する。」

You must write a program that reads the Hex Quad Tree encoding of two images, computes a new image that is the intersection of those two images, and prints its Hex Quad Tree encoding. Assume that both input images are square and contain the same number of pixels (although the lengths of their encodings may differ). If two images A and B have the same size and shape, their intersection (written as A & B) also has the same size and shape. By definition, a pixel of A & B is equal to 1 if and only if the corresponding pixels of image A and image B are both equal to 1.
 「イメージ2つの16進4分木表現を読み取り、イメージの共通部分を取り出し、16進4分木表現で表示するプログラムをつくって欲しい。2つの入力イメージが正方形で、ピクセルの数も同じ(それらの表現の長さが違うかもしれない)と仮定してよい。イメージAとBが同じサイズと形をもつならば、これらの共通部分(A & B と書く)も同じサイズと形をもつ。定義として、ピクセルA & B が1になるのは、イメージAとBの対応するピクセルが両方とも1の場合に限る。」

The following figure illustrates two input images and their intersection, together with the Hex Quad Tree encodings of each image. In the illustration, shaded squares represent pixels of color 1.
 「つぎの図に入力イメージ2つの共通部分と、16進数4分木表現が示されている。影部分は黒を表現している。」

Input
The input data set contains a sequence of test cases, each of which is represented by two lines of input. In each test case, the first input line contains the Hex Quad Tree encoding of the first image and the second line contains the Hex Quad Tree encoding of the second image. For each input image, the number of hexadecimal digits in its Hex Quad Tree encoding will not exceed 100.
 「入力に複数のテストケースが入り、それぞれを2行で説明する。1行目にはイメージ1の16進4分木表現、2行目にはイメージ2のもの。各入力イメージに対し、16進4分木表現の桁数は100以下となる。」

The last test case is followed by two input lines, each containing a single zero.
 「入力の最後の2行に、0が入る。

Output
For each test case, print “Image” followed by its sequence number. On the next line, print the Hex Quad Tree encoding of the intersection of the two images for that test case. Separate the output for consecutive test cases with a blank line.
 「各テストケースに対し、イメージの通し番号を表示すること。つぎの行に、イメージの共通部分を16進4分木表現で表示すること。各ケースの間に空白行を入れること。」

Sample Input
2FA
2BB
2FB
2EF
7
2FA
0
0

Output for the Sample Input
Image 1:
2BA

Image 2:
2EB

Image 3:
2FA

Problem D
Eurodiffusion
—- The 2003 ACM Programming Contest World Finals —-

On January 1, 2002, twelve European countries abandoned their national currency for a new currency, the euro. No more francs, marks, lires, guldens, kroner,… only euros, all over the eurozone. The same banknotes are used in all countries. And the same coins? Well, not quite. Each country has limited freedom to create its own euro coins:
 「2002年元日から、欧州12カ国が自国の通貨を新しい通貨ユーロに切り換えた。ユーロの流通地域すべてに、フランもマルクもリラもグルデンもクローネもなくなり、ユーロだけになった。すべての国々に同じ紙幣が使われている。しかしコインについては、各国が自分達のユーロコインをつくる自由が与えられている。」

“Every euro coin carries a common European face. On the obverse, member states decorate the coins with their own motif. No matter which motif is on the coin, it can be used anywhere in the 12 Member States. For example, a French citizen is able to buy a hot dog in Berlin using a euro coin with the imprint of the King of Spain.” (source: http://europa.eu.int/euro/html/entry.html)
 「ユーロコインは共通した欧州風デザインを共有する。コインの表に、参加国が自国の模様等のモチーフを飾ることができる。モチーフの違いに関わりなく、12参加国のすべての地域に使われる。たとえば、フランス人がスペイン国王の刻印のあるユーロコインを使って、ベルリンでホットドッグを買うことができる。」

On January 1, 2002, the only euro coins available in Paris were French coins. Soon the first non-French coins appeared in Paris. Eventually, one may expect all types of coins to be evenly distributed over the twelve participating countries. (Actually this will not be true. All countries continue minting and distributing coins with their own motifs. So even in a stable situation, there should be an excess of German coins in Berlin.) So, how long will it be before the first Finnish or Irish coins are in circulation in the south of Italy? How long will it be before coins of each motif are available everywhere?
 「2002年元日に、パリで手に入れるのはフランスのユーロコインだけだった。間もなく、フランスコインでないものがパリに現われた。最終的に、異なる種類のコインすべてが12参加国に均等に流通しているかもしれない(実情は違う。すべての国が自国のコインを製造流通させているので、安定期に入っても、ベルリンにドイツコインが多いはずだ。)イタリアの南地方にフィンランドコインやアイルランドコインが最初に現われるのはいつだろう。すべての地方にすべてのコインが流通するのはいつになってからだろう。」

You must write a program to simulate the dissemination of euro coins throughout Europe, using a highly simplified model. Restrict your attention to a single euro denomination. Represent European cities as points in a rectangular grid. Each city may have up to 4 neighbors (one to the north, east, south and west). Each city belongs to a country, and a country is a rectangular part of the plane. The figure below shows a map with 3 countries and 28 cities. The graph of countries is connected, but countries may border holes that represent seas, or non-euro countries such as Switzerland or Denmark. Initially, each city has one million (1000000) coins in its country’s motif. Every day a representative portion of coins, based on the city’s beginning day balance, is transported to each neighbor of the city. A representative portion is defined as one coin for every full 1000 coins of a motif.
 「そこで、単純なモデルを使って、ユーロコイン普及のシミュレーションプログラムをつくってほしい。単一額面のコインだけを考えよう。格子状の長方形の点として都市を表す。各都市に最大4つの都市(東南西北方向)が隣り合わせする。各都市がそれぞれ一国に属し、国が長方形の一部分となる。図に3カ国と28都市が示されている。国のグラフが繋がっているが、海やスイス・デンマーク等の非ユーロ国を表す部分が国境線上にあるかもしれない。初めは、各都市が自国のコインを百万枚持っているとする。毎日、一まとめ(a representative portion) のコインを隣の都市にそれぞれ運ぶことができる。一まとめとは、ちょうど同じモチーフのコイン1000枚のこと。」

A city is complete when at least one coin of each motif is present in that city. A country is complete when all of its cities are complete. Your program must determine the time required for each country to become complete.
 「最低1枚でも、すべての国のコインが入ればその都市で流通完了(complete)したという。国のすべての都市が流通完了となれば、その国も流通完了したという。各国が流通完了になるまでの時間を算出してほしい。」

Input
The input consists of several test cases. The first line of each test case is the number of countries (1<=c<=20). The next c lines describe each country. The country description has the format: name xl yl xh yh, where name is a single word with at most 25 characters; xl, yl are the lower left city coordinates of that country (most southwestward city ) and xh, yh are the upper right city coordinates of that country (most northeastward city). 1<=xl<=xh<=10 and 1<=yl<=yh<=10.
 「入力に複数のテストケースが入る。各テストケースでは国の数c (1<=c<=20) が最初に入る。つぎにつづくc行に各国に関する説明が入る。その説明のフォーマット、国名(25文字までの単語ひとつ)、xl, yl, xh, yh (xl,ylはその国の最も左下(南西)に位置する都市の座標、xh,yhは最も右上(北東)にある都市の座標。1<=xl<=xh<=10 and 1<=yl<=yh<=10.」

The last case in the input is followed by a single zero.
 「入力の最後に0が入る。」

Output
For each test case, print a line indicating the case number, followed by a line for each country with the country name and number of days for that country to become complete. Order the countries by days to completion. If two countries have identical days to completion, order them alphabetically by name.
 「各テストケースについて、ケース番号(case number)を表示すること。その後に国名、およびその国が流通完了までの日数を1行に表示すること。流通完了の日数順で並べること。日数の同じ国が複数ある場合には、国名のアルファベット順で並べること。」

Use the output format shown in the example.
 「出力データのサンプルフォーマットを利用すること。」

Sample Input
3
France 1 4 4 6
Spain 3 1 6 3
Portugal 1 1 2 2
1
Luxembourg 1 1 1 1
2
Netherlands 1 3 2 4
Belgium 1 1 2 2
0

Output for the Sample Input
Case Number 1
   Spain 382
   Portugal 416
   France 1325
Case Number 2
   Luxembourg 0
Case Number 3
   Belgium 2
   Netherlands 2

多角形同士の被覆問題。

2003年3月の世界大会の問題。出場68チーム中、手をつけたのは1チーム、解いたのは0チーム。難問かも知れない。

情報処理学会にも こんな解答 が載っているが、参考になる?

Problem E
Covering Whole Holes
—- The 2003 ACM Programming Contest World Finals —-

Can you cover a round hole with a square cover? You can, as long as the square cover is big enough. It obviously will not be an exact fit, but it is still possible to cover the hole completely.
 「四角いカバーで丸いホール(穴)をカバーできるか。四角いカバーが十分に大きければOKと答えるだろう。ピッタリ合わせるには難しいが、完全にカバーすることは可能だろう。」

The Association of Cover Manufacturers (ACM) is a group of companies that produce covers for all kinds of holes — manholes, holes on streets, wells, ditches, cave entrances, holes in backyards dug by dogs to bury bones, to name only a few. ACM wants a program that determines whether a given cover can be used to completely cover a specified hole. At this time, they are interested only in covers and holes that are rectangular polygons (that is, polygons with interior angles of only 90 or 270 degrees). Moreover, both cover and hole are aligned along the same coordinate axes, and are not supposed to be rotated against each other — just translated relative to each other.
 「ACMはあらゆるホールのカバーをつくる企業集団だ。ACMはホールを完全にカバーできるかどうかを判断してくれるプログラムを必要としている。いまの時点では、カバーもホールも直角をなす多角形(つまり多角形の各内角は90度か270度)だけのものと考えていい。さらに、カバーもホールも座標の軸線に沿って並んでいる。また、互いに回転することはしない。平行移動だけで考えてほしい。」

Input
The input consists of several descriptions of covers and holes. The first line of each description contains two integers h and c (4<=h<=50 and 4<=c<=50), the number of points of the polygon describing the hole and the cover respectively. Each of the following h lines contains two integers x and y, which are the vertices of the hole's polygon in the order they would be visited in a trip around the polygon. The next c lines give a corresponding description of the cover. Both polygons are rectangular, and the sides of the polygons are aligned with the coordinate axes. The polygons have positive area and do not intersect themselves.
 「入力に複数のカバーとホールの説明が入る。各説明の1行目には整数2つ、hとc (4<=h<=50、4<=c<=50) が、それぞれホールとカバーの多角形頂点の数を表す。その後に続くh行に整数2つ、xとyが入る。それらは多角形に沿った順番で現われるホールの頂点を示す。そのつぎのc行は対応したカバーの頂点だ。両方の多角形はともに直角をなし、多角形の各辺が座標軸線上にのっている。それぞれの多角形は正の面積をもち、内部で横切ることはない。」

The last description is followed by a line containing two zeros.
 「入力の最後に0が2つ入る。」

Output
For each problem description, print its number in the sequence of descriptions. If the hole can be completely covered by moving the cover (without rotating it), print “Yes” otherwise print “No”. Recall that the cover may extend beyond the boundaries of the hole as long as no part of the hole is uncovered. Follow the output format in the example given below.
 「各説明に対し、説明の番号を表示すること。カバーを回転せず移動だけでホールを完全にカバーすることができれば”Yes”と表示すること。そうできなければ”No”と表示すること。ホールをカバーしている限り、ホールの境界線からはみだしてカバーを動かせることに留意。

Sample Input
4 4
0 0
0 10
10 10
10 0
0 0
0 20
20 20
20 0
4 6
0 0
0 10
10 10
10 0
0 0
0 10
10 10
10 1
9 1
9 0
0 0

Output for the Sample Input
Hole 1: Yes
Hole 2: No

再帰的に定義された図形の距離算出の問題。

Problem C
Riding the Bus
—- The 2003 ACM Programming Contest World Finals —-

The latest research in reconfigurable multiprocessor chips focuses on the use of a single bus that winds around the chip. Processor components, which can be anywhere on the chip, are attached to connecting points on the bus so that they can communicate with each other.
 「マルチプロセッサ・チップの部品配置に関する最新研究として、チップ上に走るバスの使い方に焦点が当てられている。プロセッサの部品が、チップのどこにも配置可能だが、バスの接続点と繋いでおかないといけない。それで互いに通信可能になるのだ。」

Some research involves bus layout that uses recursively-defined “SZ” curves, also known as “S-shaped Peano curves.” Two examples of these curves are shown below. Each curve is drawn on the unit square. The order-1 curve, shown on the left, approximates the letter “S” and consists of line segments connecting the points (0,0), (1,0), (1,0.5), (0,0.5), (0,1), and (1,1) in order. Each horizontal line in an “S” or “Z” curve is twice as long as each vertical line. For the order-1 curve, the length of a vertical line, len, is 0.5.
 「ある研究に、再帰的に定義される”SZ”カーブのバスレイアウトが必要としている。下図にこういう形のカーブの例を2つ示した。カーブは単位正方形に書かれる。左側の1次カーブ、文字”S”に似ていて、点 (0,0), (1,0), (1,0.5), (0,0.5), (0,1), 及び (1,1) を繋ぐ線分で構成される。”S”あるいは”Z”カーブにある水平の線は縦の線の2倍の長さ。1次カーブでは、縦の線の長さlenは0.5となる。」

The order-2 curve, shown on the right, contains 9 smaller copies of the order-1 curve (4 of which are reversed left to right to yield “Z” curves). These copies are connected by line segments of length len, shown as dotted lines. Since the width and height of the order-2 curve is 8 x len, and the curve is drawn on the unit square, len = 0.125 for the order-2 curve.
 「右側に示した2次カーブは、1次カーブの縮小した9つのコピーを含む(うちの4つは左右反転していて、”Z”カーブの形をしている。)これらは長さlenの線分によって繋ぎ、ドットで図に示した。2次カーブは横幅と高さが8xlen、カーブが単位正方形に書かれているので、len=0.125。」

The order-3 curve contains 9 smaller copies of the order-2 curve (with 4 reversed left to right), connected by line segments, as described for the order-2 curve. Higher order curves are drawn in a similar manner. The connecting points to which processor components attach are evenly spaced every len units along the bus. The first connecting point is at (0,0) and the last is at (1,1). There are 9k connecting points along the order-k curve, and the total bus length is (9k-1)xlen units.
 「3次カーブは2次カーブの縮小したコピー9つからなり(うちの4つは左右逆転)、線分によって繋ぐ。高次カーブは同じ手法で書くことができる。プロセッサ部品のつなぐ接続点とはバス上のlen単位で等分した点のこと。最初の接続点は(0,0)、最後の点は(1,1)。k次カーブに9k個の接続点があり、バスの総長は(9k-1)xlen単位。」

You must write a program to determine the total distance that signals must travel between two processor components. Each component’s coordinates are given as an x, y pair, 0<=x<=1 and 0<=y<=1, where x is the distance from the left side of the chip, and y is the distance from the lower edge of the chip. Each component is attached to the closest connecting point by a straight line. If multiple connecting points are equidistant from a component, the one with the smallest x coordinate and smallest y coordinate is used. The total distance a signal must travel between two components is the sum of the length of the lines connecting the components to the bus, and the length of the bus between the two connecting points. For example, the distance between components located at (0.5, 0.25) and (1.0, 0.875) on a chip using the order-1 curve is 3.8750 units.
 「プログラムを書いて、プロセッサ部品2つの間に伝わる信号の総距離を算出して欲しい。部品の座標はx, yペアで与えられ、0<=x<=1、 0<=y<=1。x はチップの左側からの距離、y は下側からの距離。各部品は直線で最寄の接続点に繋ぐ。部品から等距離の接続点が複数ある場合は、最小のx と最小のyの点を使う。部品間、信号の伝わる総距離とは、部品からバスの接続点までの距離の和と、2つの接続点間のバスの長さの合計距離だ。例えば、(0.5, 0.25) および (1.0, 0.875) に配置された部品間の距離は、1次カーブでは3.8750となる。」
 
Input
The input contains several cases. For each case, the input consists of an integer that gives the order of the SZ curve used as the bus (no larger than 8), and then four real numbers x1, y1, x2, y2 that give the coordinates of the processor components to be connected. While each processor component should actually be in a unique location not on the bus, your program must correctly handle all possible locations.
 「入力に複数のケースが含まれる。各ケースにおいて、整数1つ、SZカーブの次元(オーダー、最大8まで)を示すもの、実数4つ、x1, y1, x2, y2、繋ぐべくプロセッサ部品の座標を示すもの、が入る。プロセッサ部品はバス上にあってはいけないが、プログラムは可能な位置をすべて取り扱えるようにすること。」

The last case in the input is followed by a single zero.
 「入力の最後に0が入る。」

Output
For each case, display the case number (starting with 1 for the first case) and the distance between the processor components when they are connected as described. Display the distance with 4 digits to the right of the decimal point.
 「各々のケースについて、ケース番号(case number)(最初のケースは1として)および部品間の距離を入れること。距離は小数点以下4桁で表示すること。」

Use the same format as that shown in the sample output shown below. Leave a blank line between the output lines for consecutive cases.
 「出力フォーマット例を利用すること。各ケースの間に空白行を入れること。」

Sample Input
1 0.5 .25 1 .875
1 0 0 1 1
2 .3 .3 .7 .7
2 0 0 1 1
0

Output for the Sample Input
Case 1. Distance is 3.8750

Case 2. Distance is 4.0000

Case 3. Distance is 8.1414

Case 4. Distance is 10.0000

Problem B
Light Bulbs
—- The 2003 ACM Programming Contest World Finals —-

Hollywood’s newest theater, the Atheneum of Culture and Movies, has a huge computer-operated marquee composed of thousands of light bulbs. Each row of bulbs is operated by a set of switches that are electronically controlled by a computer program. Unfortunately, the electrician installed the wrong kind of switches, and tonight is the ACM’s opening night. You must write a program to make the switches perform correctly.
 「ハリウッドの最新劇場 Atheneum of Culture and Movies の入り口に、コンピュータで制御可能な、何千本もの照明電球の入った看板がある。電球の照明はスイッチの操作によって行われるが、そのスイッチはコンピュータプログラムから電気的に制御される。不幸なことに、スイッチが間違って組み込まれてしまった。しかし、ACMオープンニング・ナイトが間もなく始まる。スイッチを正しく動かすプログラムを急いでつくれ。」

A row of the marquee contains n light bulbs controlled by n switches. Bulbs and switches are numbered from 1 to n, left to right. Each bulb can either be ON or OFF. Each input case will contain the initial state and the desired final state for a single row of bulbs.
 「1列に配置された n本の電球がn個のスイッチによって制御される。電球およびスイッチに、左から右まで、1からnの番号がついている。電球はON、OFFできる。入力データに、電球一列の初期状態と、必要とされる最終状態が書かれている。」

The original lighting plan was to have each switch control a single bulb. However the electrician’s error caused each switch to control two or three consecutive bulbs, as shown in Figure 1. The leftmost switch (i = 1) toggles the states of the two leftmost bulbs (1 and 2); the rightmost switch (i = n) toggles the states of the two rightmost bulbs (n-1 and n). Each remaining switch (1 < i < n) toggles the states of the three bulbs with indices i-1, i, and i+1. (In the special case where there is a single bulb and a single switch, the switch simply toggles the state of that bulb.) Thus, if bulb 1 is ON and bulb 2 is OFF, flipping switch 1 will turn bulb 1 OFF and bulb 2 ON. The minimum cost of changing a row of bulbs from an initial configuration to a final configuration is the minimum number of switches that must be flipped to achieve the change.
 「スイッチ1つが電球1本を制御するように当初計画されていたが、間違えられて、図のように、スイッチ1つが電球2本または3本を同時に制御するようになってしまった。左端のスイッチ(i=1)は左端の電球2本(1と2)を、右端のスイッチ(i=n)は右端の電球2本(n-1とn)を、その間のスイッチ(1<i<n)が電球3本(i-1、i、i+1)を制御している。(極端なケースでは、スイッチ1つと電球1本だけの構成もありうる。その場合、1対1の操作と考えてよい。)電球1がON、電球2がOFFの状態であれば、フリップスイッチ1(<訳注>Flipイッチ。押すたびにオン⇔オフと切り替わるタイプのスイッチと考えてよい</訳注>)は電球1をOFF、電球2をONにする。初期状態から最終状態に変える最小コストとは、スイッチの押す回数を最小にすることだ。」

You can represent the state of a row of bulbs in binary, where 0 means the bulb is OFF and 1 means the bulb is ON. For instance, 01100 represents a row of five bulbs in which the second and third bulbs are both ON. You could transform this state into 10000 by flipping switches 1, 4, and 5, but it would be less costly to simply flip switch 2.
 「電球1列の状態を2進数で表現する。0を電球のOFF、1を電球のONを示す。例えば、01100は5本の電球に、2本目と3本目がONになっていることを表す。この状態から、スイッチ1、4、5を押すことで10000にすることができるが、もっとも簡単なのはスイッチ2を押すことだ。」

You must write a program that determines the switches that must be flipped to change a row of light bulbs from its initial state to its desired final state with minimal cost. Some combinations of initial and final states may not be feasible. For compactness of representation, decimal integers are used instead of binary for the bulb configurations. Thus, 01100 and 10000 are represented by the decimal integers 12 and 16.
 「初期状態から最終状態にするため、押さなきゃいけないスイッチの最小コストを決めるプログラムをつくってほしい。組合せによっては、最終状態は初期状態から実現できないかもしれない。短く表現したいので、2進数の代わりに10進数を使う。それで、01100と10000を10進数12と16で表現する。」

Input
The input file contains several test cases. Each test case consists of one line. The line contains two non-negative decimal integers, at least one of which is positive and each of which contains at most 100 digits. The first integer represents the initial state of the row of bulbs and the second integer represents the final state of the row. The binary equivalent of these integers represents the initial and final states of the bulbs, where 1 means ON and 0 means OFF.
 「入力にいくつかのテストケースが含まれる。各テストケースは1行に書かれる。その行に負でない10進整数が2つが入り、すくなくとも2つのうちの1つは正数。2つの整数は最大100桁。1つ目の整数は電球の初期状態、2つ目は電球の最終状態を表す。2つの整数に対応した2進表現では、1が電球のON、0が電球のOFFを示す。」

To avoid problems with leading zeros, assume that the first bulb in either the initial or the final configuration (or both) is ON. There are no leading or trailing blanks in the input lines, no leading zeros in the two decimal integers, and the initial and final states are separated by a single blank.
 「数字の先頭に0を無くすために、最初の電球が初期状態においても、終了状態においてもONと考えてよい。入力行の先頭と末尾に空白文字は入らないし、2つの10進整数の先頭に0は入らない。初期状態と終了状態との間に空白文字が1つ入る。」

The last test case is followed by a line containing two zeros.
 「入力の最後に0が二つ入る。

Output
For each test case, print a line containing the case number and a decimal integer representing a minimum-cost set of switches that need to be flipped to convert the row of bulbs from initial state to final state. In the binary equivalent of this integer, the rightmost (least significant) bit represents the nth switch, 1 indicates that a switch has been flipped, and 0 indicates that the switch has not been flipped. If there is no solution, print “impossible”. If there is more than one solution, print the one with the smallest decimal equivalent.
 「各テストケースに対して、ケース番号(case number)と、初期状態から最終状態にするための押すスイッチの組合せの最小コストを10進整数で1行に書くこと。整数の2進表現では、右端ビット(最下位)はn番目のスイッチを表し、1は押すべくスイッチ、0はそのまま押さないスイッチを表すこと。解答がなければ、”impossible”と表示すること。解答が複数ある場合、最小の10進表現にすること。」

Print a blank line between cases. Use the output format shown in the example.
 「各ケースの間に空白行を入れること。出力フォーマット例を参照せよ。」

Sample Input
12 16
1 1
3 0
30 5
7038312 7427958190
4253404109 657546225
0 0

Output for the Sample Input
Case Number 1: 8

Case Number 2: 0

Case Number 3: 1

Case Number 4: 10

Case Number 5: 2805591535

Case Number 6: impossible

ビルをつなぐ通路の本数と最短距離を求めるプログラム。

Problem A
Building Bridges
—- The 2003 ACM Programming Contest World Finals —-

The City Council of New Altonville plans to build a system of bridges connecting all of its downtown buildings together so people can walk from one building to another without going outside. You must write a program to help determine an optimal bridge configuration.
 「New Altonville町の議会が町の各ビルをブリッジでつなぐ計画を立てている。外で歩かなくてもビル間の行き来ができるのがその理由。とにかく最適なプランを決めて欲しい。」

New Altonville is laid out as a grid of squares. Each building occupies a connected set of one or more squares. Two occupied squares whose corners touch are considered to be a single building and do not need a bridge. Bridges may be built only on the grid lines that form the edges of the squares. Each bridge must be built in a straight line and must connect exactly two buildings.
 「New Altonville町はグリッドごとの正方形ブロックに建てられている。各ビルは1つあるいは複数のブロックを使っている。ブロックの角がくっ付いているビルは一つと見なし、間にブリッジは必要ない。ブリッジはグリッド線に沿って建てるべきだ。ブリッジは直線でないといけないし、直接2つのビルをつなぐものでないといけない。」

For a given set of buildings, you must find the minimum number of bridges needed to connect all the buildings. If this is impossible, find a solution that minimizes the number of disconnected groups of buildings. Among possible solutions with the same number of bridges, choose the one that minimizes the sum of the lengths of the bridges, measured in multiples of the grid size. Two bridges may cross, but in this case they are considered to be on separate levels and do not provide a connection from one bridge to the other.
 「ビルの配置が判れば、すべてのビルをつなぐブリッジの最小数を計算してほしい。不可能であれば、つないでいないビルの数を最小にしてほしい。ブリッジの数が同数の解答が複数ある場合には、ブリッジの長さを最短のものにすること。ブリッジが交差するかもしれないが、その場合、ブリッジの高さが互いに違うと考えていい。つまり、ブリッジ同士をつなぐ必要はない。」

The figure below illustrates four possible city configurations. City 1 consists of five buildings that can be connected by four bridges with a total length of 4. In City 2, no bridges are possible, since no buildings share a common grid line. In City 3, no bridges are needed because there is only one building. In City 4, the best solution uses a single bridge of length 1 to connect two buildings, leaving two disconnected groups (one containing two buildings and one containing a single building).
 「町の配置図が4つ示されている。町1に5つのビルがあり、総長4のブリッジ4本でつなぐことができる。町2ではブリッジを建てることは不可能。グリッド線を共有しているビルがないから。町3ではブリッジは必要ない。ビルが1つしかないから。町4では、長さ1のブリッジ1本で2つのビルをつなぐのが最もよい。2つのつながっていないビル群をそのままにする。片方のビル群に2つのビルがつながっているが、もう片方に独立したビルが1つある。

Input
The input data set describes several rectangular cities. Each city description begins with a line containing two integers r and c, representing the size of the city on the north-south and east-west axes measured in grid lengths (1<=r<=50 and 1<=c<=50). These numbers are followed by exactly r lines, each consisting of c hash (“#”) and dot (“.”) characters. Each character corresponds to one square of the grid. A hash character corresponds to a square that is occupied by a building, and a dot character corresponds to a square that is not occupied by a building.
 「入力データに複数の長方形町を示している。各町は二つの整数 r(町の南北方向の長さ、1<=r<=50)、c(東西方向の長さ、1<=c<=50)からスタートし、 その後にr行が続き、それらの行にc個の”#”と”.”文字が入る。各文字が正方形ブロックを表し、”#”はビル、”.”は空き地を示す。」

The input data for the last city will be followed by a line containing two zeros.
 「入力の最後に0が2つ入る。」

Output
For each city description, print two or three lines of output as shown below. The first line consists of the city number. If the city has fewer than two buildings, the second line is the sentence “No bridges are needed.” If the city has two or more buildings but none of them can be connected by bridges, the second line is the sentence “No bridges are possible.” Otherwise, the second line is “N bridges of total length L” where N is the number of bridges and L is the sum of the lengths of the bridges of the best solution. (If N is 1, use the word “bridge” rather than “bridges.”) If the solution leaves two or more disconnected groups of buildings, print a third line containing the number of disconnected groups.
 「各町に対し、2行あるいは3行を表示すること。1行目に町の番号(City Number)を入れること。町にビルが1つしかない場合、2行目に “No bridges are needed.” と表示すること。 町にビルが2つ以上あるけれど、ブリッジでつなぐことができなければ、2行目に “No bridges are possible.” と表示すること。それら以外の場合、2行目に “N bridges of total length L” と表示すること。Nはブリッジの数。N=1の場合、”bridges” の代わりに “bridge” を使うこと。Lはブリッジの最短総長。2つ以上のつないでいないビル群があれば、3行目にその数を表示すること。」

Print a blank line between cases. Use the output format shown in the example.
 「各町に対応する出力データの間に、空白行を入れること。例に示されているフォーマットを利用するといいだろう。」

Sample Input
3 5
#…#
..#..
#…#
3 5
##…
…..
….#
3 5
#.###
#.#.#
###.#
3 5
#.#..
…..
….#
0 0

Output for the Sample Input
City 1
4 bridges of total length 4

City 2
No bridges are possible.
2 disconnected groups

City 3
No bridges are needed.

City 4
1 bridge of total length 1
2 disconnected groups

Problem A
Unreliable Messengers
—- 2003年 会津大会 —-

The King of a little Kingdom on a little island in the Pacific Ocean frequently has childish ideas. One day he said, “You shall make use of a message relaying game when you inform me of something.” In response to the King’s statement, six servants were selected as messengers whose names were Mr. J, Miss C, Mr. E, Mr. A, Dr. P, and Mr. M. They had to relay a message to the next messenger until the message got to the King.
 「島に住む国王が面白いことを言った、「何かを伝えたい時に、メッセージのリレーゲームでないといかん。」それで、Jさん、Cさん、Eさん、Aさん、Pさん、Mさんら6人が選ばれ、国王にメッセージが伝わるまで、互いにメッセージのリレーをしないといけなくなった。」

Messages addressed to the King consist of digits (‘0’-‘9’) and alphabet characters (‘a’-‘z’, ‘A’-‘Z’). Capital and small letters are distinguished in messages. For example, “ke3E9Aa” is a message.
 「国王に届くメッセージは数字と英字で書かれる。大文字小文字は区別される。例えば、“ke3E9Aa” は1通のメッセージ。」

Contrary to King’s expectations, he always received wrong messages, because each messenger changed messages a bit before passing them to the next messenger. Since it irritated the King, he told you who are the Minister of the Science and Technology Agency of the Kingdom, “We don’t want such a wrong message any more. You shall develop software to correct it!” In response to the King’s new statement, you analyzed the messengers’ mistakes with all technologies in the Kingdom, and acquired the following features of mistakes of each messenger. A surprising point was that each messenger made the same mistake whenever relaying a message. The following facts were observed.
 「期待に反して、国王にいつも間違ったメッセージしか伝わらなかった。怒った国王は科学技術大臣に命令した。「うんざりだ。エラーを直せ!」大臣が頑張った結果、以下の特徴を見つけ出した。また、すべてのメッセージに同じ間違いがあったことも突き止めた。」

Mr. J rotates all characters of the message to the left by one. For example, he transforms “aB23d” to “B23da”.
 「Jさんはメッセージを一文字左に回転させる。例、“aB23d”→“B23da”。」

Miss C rotates all characters of the message to the right by one. For example, she transforms “aB23d” to “daB23”.
 「Cさんはメッセージを一文字右に回転させる。例、“aB23d”→“daB23”。」

Mr. E swaps the left half of the message with the right half. If the message has an odd number of characters, the middle one does not move. For example, he transforms “e3ac” to “ace3”, and “aB23d” to “3d2aB”.
 「Eさんはメッセージの左半分と右半分とを入れ替える。メッセージの文字数が奇数の場合、真ん中の文字はそのまま。例、“e3ac”→“ace3”、“aB23d”→“3d2aB”。」

Mr. A reverses the message. For example, he transforms “aB23d” to “d32Ba”.
 「Aさんはメッセージを左右逆にする。例、“aB23d”→“d32Ba”。」

Dr. P increments by one all the digits in the message. If a digit is ‘9’, it becomes ‘0’. The alphabet characters do not change. For example, he transforms “aB23d” to “aB34d”, and “e9ac” to “e0ac”.
 「Pさんはすべての数字の値を1つ増やす、つまり、数字が9なら、0になる。英字は変わらない。例、“aB23d”→“aB34d”、 “e9ac”→“e0ac”。」

Mr. M decrements by one all the digits in the message. If a digit is ‘0’, it becomes ‘9’. The alphabet characters do not change. For example, he transforms “aB23d” to “aB12d”, and “e0ac” to “e9ac”.
 「Mさんはすべての数字の値を1つ減らす、つまり、数字が0なら、9になる。英字は変わらない。例、“aB23d”→“aB12d”、 “e0ac”→“e9ac”。」

The software you must develop is to infer the original message from the final message, given the order of the messengers. For example, if the order of the messengers is A→J→M→P and the message given to the King is “aB23d”, what is the original message? According to the features of the messengers’ mistakes, the sequence leading to the final message is

    “32Bad”→ A →“daB23”→ J →“aB23d”→ M →“aB12d”→ P →“aB23d”:

As a result, the original message should be “32Bad”.
 「6人のリレー順番が判ったとして、最後のメッセージを元に戻さないといけない。例えば、リレーの順番がA→J→M→Pの元で、国王に伝わったメッセージが “aB23d” だとすると、元のメッセージ “32Bad” に戻さないといけない。」

Input

The input format is as follows.
 「入力フォーマットは以下の通り。」

   n
   The order of messengers
   The message given to the King
   …
   The order of messengers
   The message given to the King

The first line of the input contains a positive integer n, which denotes the number of data sets. Each data set is a pair of the order of messengers and the message given to the King. The number of messengers relaying a message is between 1 and 6 inclusive. The same person may not appear more than once in the order of messengers. The length of a message is between 1 and 25 inclusive.
 「最初の行に正の整数nが入り、データセットの数を表す。各データセットは、リレーの順番と国王に伝わったメッセージとのペアだ。リレーに参加する人数は1から6まで。1人が2度以上リレーすることはない。メッセージの長さが1から25まで。」

Output

The inferred messages are printed each on a separate line.
 「各行に元のメッセージを表示すること。」

Sample Input

5
AJMP
aB23d
E
86AE
AM
6
JPEM
WaEaETC302Q
CP
rTurnAGundam1isdefferentf

Output for the Sample Input

32Bad
AE86
7
EC302QTWaEa
TurnAGundam0isdefferentfr