Problem J
—- 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.

Figure 1: To reach Samarkand with 66 spoons, traveling through a town followed by two villages, you must start with 76 spoons.

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.

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.

The input consists of several test cases. Each test case consists of two parts: the roadmap followed by the delivery details.

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 が入る。」

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.

Sample Input
a Z
19 a Z
A b
b c
c X
39 A X

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.

  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.)


  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.


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.

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).

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.

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.

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.

  • 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.

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.

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.

The last case will be followed by a line containing only a dollar sign.

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.

Sample Input
C 03 01 02 03
C 03 04 05 06
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
C 06 A B C D E F
C 06 51 52 53 54 55 56

Output for the Sample Input

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

Case 2: checksum = 548C
——–      —-
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.

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.

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.
  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.

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.

The last test case is followed by two input lines, each containing a single zero.

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.

Sample Input

Output for the Sample Input
Image 1:

Image 2:

Image 3:

Problem D
—- 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:

“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)

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?

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.

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.

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
France 1 4 4 6
Spain 3 1 6 3
Portugal 1 1 2 2
Luxembourg 1 1 1 1
Netherlands 1 3 2 4
Belgium 1 1 2 2

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



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

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.

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.

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.

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.

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.

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.

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となる。」
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.

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

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.

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.

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.

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.

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.

The last test case is followed by a line containing two zeros.

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).

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.

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.

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”.

Miss C rotates all characters of the message to the right by one. For example, she transforms “aB23d” to “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”.

Mr. A reverses the message. For example, he transforms “aB23d” to “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” に戻さないといけない。」


The input format is as follows.

   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.


The inferred messages are printed each on a separate line.

Sample Input


Output for the Sample Input