魔方陣になるまでの最小回転回数を求める問題。

SQUARES

Consider a 3 by 3 arrangement of the digits 1 to 9, as illustrated in the following diagram:
 「1~9までの数字でつくった3x3配列がある。」

The arrangement can by modified by rotating any of the 2-by-2 groups in the corners, either clockwise or anticlockwise. Thus if the top-right corner of the above arrangement is rotated anticlockwise, the result is the following arrangement:
 「コーナーにある2x2のグループを時計方向または反時計方向に回転することができる。つまり、例えば、右上コーナーの部分を反時計方向に回転すると配列がつぎの画面になる。」

A magic square is an n-by-n arrangement of numbers, such that the sum of the numbers in each row, column, and diagonal is the same. For example, the following diagram illustrates one possible 3-by-3 magic square for the numbers 1 to 9:
 「数字のnxn魔方陣というのは、縦横斜め方向の数字の合計がすべて等しいものだ。例えば、つぎの図は3x3の魔方陣だ。」

Your task is to determine the minimum number of moves to transform a given digit arrangement into a magic square.
 「魔方陣になるまでの最小回転回数を計算して欲しい。」

For example, the magic square in Figure 3 can be obtained from the arrangement illustrated in Figure 2 by one clockwise rotation of the top-left corner. Thus the arrangement given in Figure 1 can be transformed into a magic square in 2 moves (and, as you can verify, no shorter sequences of moves would suffice).
 「例えば、図3は図2の左上コーナーの時計方向回転によって得られる。それで、図1から2回の回転で魔方陣にすることができるのだ。それ以下の回数では魔方陣にできないことも証明できるだろう。」

INPUT FORMAT

Input will consist of a series of lines, each specifying an initial arrangement of the digits 1 to 9, listed in row-by-row order.
 「入力データに複数の行が入る。各行は数字1~9の初期配列を示す。数字は配列の上から1行ずつの並びだ。」

The end of the input is indicated by a line that consists of the word END.
 「入力の終了として、単語 END が入る。」

SAMPLE INPUT:

135876492
438975261
672159834
129764583
END

OUTPUT FORMAT

Output for each arrangement should consist of either:
  o the minimum number of moves followed by a single space and then the word “moves”, or
  o the word “IMPOSSIBLE”, if it is not possible to achieve a magic square arrangement.
 「出力として、各配列に対応して
   o 最小回転回数、スペース1文字、単語 moves を入れる。または、
   o 魔方陣にできなければ、単語 IMPOSSIBLE を入れる。

SAMPLE OUTPUT:

2 moves
1 moves
0 moves
4 moves

Problem F
Gap
---- 2003年 会津大会 ----

Let’s play a card game called Gap.
 「ギャップと呼ばれるカードゲーム。」

You have 28 cards labeled with two-digit numbers. The first digit (from 1 to 4) represents the suit of the card, and the second digit (from 1 to 7) represents the value of the card.
 「2桁の数字の付いているカードが28枚ある。左の数字(1から4)はカードのスーツ(ハート、ダイアモンド、クラブ、スペードのこと)を表し、右の数字(1から7)はカードの大きさを表す。」

First, you shuffle the cards and lay them face up on the table in four rows of seven cards, leaving a space of one card at the extreme left of each row. The following shows an example of initial layout.
 「カードを混ぜて、テーブルに7枚ずつ4列をつくり、数字が見えるようにする。4列の左にカード1枚入るスペースを確保しておく。下図参照」

Next, you remove all cards of value 1, and put them in the open space at the left end of the rows: “11” to the top row, “21” to the next, and so on.
 「数字1のカードを左のスペースにもっていき、上から11、21等の順に置く。」

Now you have 28 cards and four spaces, called gaps, in four rows and eight columns. You start moving cards from this layout.
 「これで28枚のカードと4箇所のスペース(ギャップと呼ぶ)が4x8の列になる。ここからゲームがスタート。」

At each move, you choose one of the four gaps and fill it with the successor of the left neighbor of the gap. The successor of a card is the next card in the same suit, when it exists. For instance the successor of “42” is “43”, and “27” has no successor.
 「移動のルールとして、4箇所のギャップのどれかを選び、そのギャップの左隣のカードの次にくるもので埋めないといけない。スーツは同じでないといけない。例えば、"42"のつぎのカードは"43"であり、"27"につぎのカードはない。」

In the above layout, you can move “43” to the gap at the right of “42”, or “36” to the gap at the right of “35”. If you move “43”, a new gap is generated to the right of “16”. You cannot move any card to the right of a card of value 7, nor to the right of a gap.
 「上のレイアウトでは、"43"を"42"の右のギャップにいれることができる。または、"35"の右隣に"36"が移動可能。"43"を移動したら、"16"の右に新しいギャップが空く。しかし、数字7の右にカードを移動することができない。

The goal of the game is, by choosing clever moves, to make four ascending sequences of the same suit, as follows.
 「同じスーツが昇順で並ぶようになればゲームが完成し終了する。」

Your task is to find the minimum number of moves to reach the goal layout.
 「完成するまでの最小移動回数を計算して欲しい。」

Input

The input starts with a line containing the number of initial layouts that follow.
 「入力の1行目に、初期レイアウトの数が入る。」

Each layout consists of five lines --- a blank line and four lines which represent initial layouts of four rows. Each row has seven two-digit numbers which correspond to the cards.
 「個々のレイアウトは5行。1行は空白行、残りの4行はカード4列の最初の並びを表す。」

Output

For each initial layout, produce a line with the minimum number of moves to reach the goal layout. Note that this number should not include the initial four moves of the cards of value 1. If there is no move sequence from the initial layout to the goal layout, produce "-1".
 「個々のレイアウトに対応して、完成までの最短移動回数を表示すること。最初のカードの移動はこの回数に入れないこと。初期レイアウトから完成することは不可能な場合は、-1を表示すること。」

Sample Input

4

12 13 14 15 16 17 21
22 23 24 25 26 27 31
32 33 34 35 36 37 41
42 43 44 45 46 47 11

26 31 13 44 21 24 42
17 45 23 25 41 36 11
46 34 14 12 37 32 47
16 43 27 35 22 33 15

17 12 16 13 15 14 11
27 22 26 23 25 24 21
37 32 36 33 35 34 31
47 42 46 43 45 44 41

27 14 22 35 32 46 33
13 17 36 24 44 21 15
43 16 45 47 23 11 26
25 37 41 34 42 12 31

Output for the Sample Input

0
33
60
-1

分子式の構文解析問題。

Problem E
Molecular Formula
---- 2003年 会津大会 ----

Your mission in this problem is to write a computer program that manipulates molecular formulae in virtual chemistry. As in real chemistry, each molecular formula represents a molecule consisting of one or more atoms. However, it may not have chemical reality.
 「分子式を扱って欲しい。」

The following are the definitions of atomic symbols and molecular formulae you should consider.
 「以下は原子記号と分子式の定義。」

 ● An atom in a molecule is represented by an atomic symbol, which is either a single capital letter or a capital letter followed by a small letter. For instance H and He are atomic symbols.
   「分子式中の原子は原子記号でで表され、その原子記号は大文字の1文字、あるいは大文字に続き小文字の2文字である。例、HとHeは原子記号。」

 ● A molecular formula is a non-empty sequence of atomic symbols. For instance, HHHeHHHe is a molecular formula, and represents a molecule consisting of four H’s and two He’s.
   「分子式は原子記号の列である。例、HHHeHHHeは分子式、4つのHと2つのHeで構成される分子。」
 ● For convenience, a repetition of the same sub-formula where n is an integer between 2 and 99 inclusive, can be abbreviated to (X)n. Parentheses can be omitted if X is an atomic symbol. For instance, HHHeHHHe is also written as H2HeH2He, (HHHe)2, (H2He)2, or even ((H)2He)2.
   「便宜上、同じ式Xのn回の繰り返し(nは2から99までの整数)は(X)nと書くこともできる。Xが原子記号の場合、括弧も省略できる。例、HHHeHHHeはH2HeH2He、(HHHe)2、(H2He)2、((H)2He)2のどちらでもいい。」

The set of all molecular formulae can be viewed as a formal language. Summarizing the above description, the syntax of molecular formulae is defined as follows.
 「まとめると、分子式は形式上、つぎのように定義することができる。」

   Molecule → Atom | Atom Number | ( Molecule ) Number | Molecule Molecule
   Atom → CapitalLetter | CapitalLetter SmallLetter
   Number → 2 | 3 | 4 | … | 97 | 98 | 99
   CapitalLetter → A | B | C | … | X | Y | Z
   SmallLetter → a | b | c | … | x | y | z

Each atom in our virtual chemistry has its own atomic weight. Given the weights of atoms, your program should calculate the weight of a molecule represented by a molecular formula. The molecular weight is defined by the sum of the weights of the constituent atoms. For instance, assuming that the atomic weights of the atoms whose symbols are H and He are 1 and 4, respectively, the total weight of a molecule represented by (H2He)2 is 12.
 「各原子は質量をもている。原子の質量が与えられるものとして、分子式で書き表される分子の質量を計算しなさい。分子の質量は原子の質量の合計である。例えば、HとHeの質量はそれぞれ1と4とすると、分子(H2He)2の質量は12である。」

Input

The input consists of two parts. The first part, the Atomic Table, is composed of a number of lines, each line including an atomic symbol, one or more spaces, and its atomic weight which is a positive integer no more than 1000. No two lines include the same atomic symbol.
 「入力は2部からなる。第1部には原子表があり、各行に原子記号とその質量(1000を越えない正の整数)が入る。間には1つ以上のスペースで区切られる。同じ原子記号が異なる行に書かれることはない。」

The first part ends with a line containing only the string END OF FIRST PART.
 「第1部の終了として、文字列 END OF FIRST PART の行が入る。」

The second part of the input is a sequence of lines. Each line is a molecular formula, not exceeding 80 characters, and contains no spaces. A molecule contains at most 105 atoms. Some atomic symbols in a molecular formula may not appear in the Atomic Table. The sequence is followed by a line containing a single zero, indicating the end of the input.
 「第2部には複数の行があり、それぞれの行が80文字を越えない分子式が書かれている。スペース文字は含まない。分子式1つに最大105の原子を含むことがある。原子表になかった原子記号が含まれることもある。入力の最後として、0だけの行が入る。」

Output

The output is a sequence of lines, one for each line of the second part of the input. Each line contains either an integer, the molecular weight for a given molecular formula in the corresponding input line if all its atomic symbols appear in the Atomic Table, or UNKNOWN otherwise. No extra characters are allowed.
 「出力の各行に入力の第2部の各行に対応すること。原子表に存在する原子の分子式についてはその質量、表にない原子が含まれた分子式については UNKNOWN と表示すること。その他の文字は入れてはいけない。」

Sample Input

H 1
He 4
C 12
O 16
F 19
Ne 20
Cu 64
Cc 333
END_OF_FIRST_PART
H2C
(MgF)2As
Cu(OH)2
H((CO)2F)99
0

Output for the Sample Input

14
UNKNOWN
98
7426

天気のスケジュールをつくる問題。

Problem D
Weather Forecast
---- 2003年 会津大会 ----

You are the God of Wind.
 「貴方は風の神様。」

By moving a big cloud around, you can decide the weather: it invariably rains under the cloud, and the sun shines everywhere else.
 「雨雲を動かすことで、天気を左右できる。雲の下はいつも雨、雲のないところはいつも晴れだから。」

But you are a benign God: your goal is to give enough rain to every field in the countryside, and sun to markets and festivals. Small humans, in their poor vocabulary, only describe this as “weather forecast”.
 「でも、貴方は情け深く、十分な量の雨を降らせたいが、マーケットや祭りのある日に晴れてやりたい。」

You are in charge of a small country, called Paccimc. This country is constituted of 4x4 square areas, denoted by their numbers.
 「4x4正方形の国が任せられた。」

Your cloud is of size 2x2, and may not cross the borders of the country.
 「雲の大きさは2x2。しかも国境から出てはいけない。」

You are given the schedule of markets and festivals in each area for a period of time. On the first day of the period, it is raining in the central areas (6-7-10-11), independently of the schedule.
 「ある期間内の、マーケットや祭りのスケジュール表はもらえる。最初の日には、スケジュールと関係なく、中央地区(6-7-10-11)は雨になっている。」

On each of the following days, you may move your cloud by 1 or 2 squares in one of the four cardinal directions (North, West, South, and East), or leave it in the same position. Diagonal moves are not allowed. All moves occur at the beginning of the day.
 「その後の日には、上下左右4方向に、1地区、または2地区、雨雲を動かすことができる。同じ場所に留めることもできる。対角線方向の移動はできない。一日の始まりの時刻に移動する。」

You should not leave an area without rain for a full week (that is, you are allowed at most 6 consecutive days without rain). You don’t have to care about rain on days outside the period you were given: i.e. you can assume it rains on the whole country the day before the period, and the day after it finishes.
 「1週間雨の降らない地区があってはいけない、つまり、雨の降らない日は個々の地区では最大6日間。期間外の日に雨の心配はしなくていい。つまり、期間前後の日に全国的に雨が降ると仮定してもいい。」

Input

The input is a sequence of data sets, followed by a terminating line containing only a zero.
 「入力は複数のデータセットが入る。入力の終了として、0の行が入る。」

A data set gives the number N of days (no more than 365) in the period on a single line, followed by N lines giving the schedule for markets and festivals. The i-th line gives the schedule for the i-th day. It is composed of 16 numbers, either 0 or 1, 0 standing for a normal day, and 1 a market or festival day. The numbers are separated by one or more spaces.
 「データセットに、期間の日数N(365以下)が与えられ、その後にN行が続き、マーケットと祭りのスケジュールを表す。i行目はi日目のスケジュール。1行に16個の数字があり、0は普通の日、1はマーケットや祭りのある日を示す。」

Output

The answer is a 0 or 1 on a single line for each data set, 1 if you can satisfy everybody, 0 if there is no way to do it.
 「それぞれのデータセットに対し、0か1を1行ずつ出力すること。すべての要望に満足させることができるならば1、ダメなら0にすること。」

Sample Input

1
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
7
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 1 0 0 0 0 1 1 0 0 1
0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1
0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0
0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0
7
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0
0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0
0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0
15
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0
0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0
0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0
0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0
1 0 0 1 1 0 0 0 0 1 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0
0

Output for the Sample Input

0
1
0
1

Problem C
Area of Polygons
---- 2003年 会津大会 ----

Yoko’s math homework today was to calculate areas of polygons in the xy-plane. Vertices are all aligned to grid points (i.e. they have integer coordinates).
 「Yokoさんの数学宿題はxy平面上の多角形の面積を求めるものだ。各頂点はすべてグリッド点にある、すなわち、整数座標上にある。」

Your job is to help Yoko, not good either at math or at computer programming, get her homework done. A polygon is given by listing the coordinates of its vertices. Your program should approximate its area by counting the number of unit squares (whose vertices are also grid points) intersecting the polygon. Precisely, a unit square “intersects the polygon” if and only if the intersection of the two has non-zero area. In the figure below, dashed horizontal and vertical lines are grid lines, and solid lines are edges of the polygon. Shaded unit squares are considered intersecting the polygon. Your program should output 55 for this polygon (as you see, the number of shaded unit squares is 55).
 「Yokoさんの宿題に手伝って欲しい。多角形は頂点の座標リストとして与えられる。多角形と共通する単位正方形の数を数えることで面積を見積もって欲しい。共通するとは、つまり、多角形と単位正方形との共有面積が0以上のことだ。下図では、ダッシュの線は縦横のグリッド線を表し、実線は多角形の輪郭を表す。影のかかっている単位正方形は多角形との共通部分だ。共通部分の単位正方形の数が55なので、55と教えること。」


Figure 1: A polygon and unit squares intersecting it

Input

The input file describes polygons one after another, followed by a terminating line that only contains a single zero.
 「入力ファイルに複数の多角形のデータが入る。入力の終了として最終行に0が入る。」

A description of a polygon begins with a line containing a single integer, m (>= 3), that gives the number of its vertices. It is followed by m lines, each containing two integers x and y, the coordinates of a vertex. The x and y are separated by a single space. The i-th of these m lines gives the coordinates of the i-th vertex (i = 1, ..., m). For each i = 1, ..., m-1, the i-th vertex and the (i + 1)-th vertex are connected by an edge. The m-th vertex and the first vertex are also connected by an edge (i.e., the curve is closed). Edges intersect only at vertices. No three edges share a single vertex (i.e., the curve is simple). The number of polygons is no more than 100. For each polygon, the number of vertices (m) is no more than 100. All coordinates x and y satisfy -2000<= x <= 2000 and -2000 <= y <= 2000.
 「各多角形のデータは頂点を示す整数m(>=3)の行から始まる。続くm行に、頂点の座標を表す2つの整数x, yが入る。i番目の行はi番目の頂点の座標。i+1番目の頂点とi番目の頂点とはエッジ(腺分)でつなぐ。最後のm番目の頂点は最初の1番目の頂点とエッジで結んでいる。エッジ同士は頂点でしかぶつからない。1つの頂点からエッジ3本出ることはない。個々の多角形の頂点の数は100以下と考えてよい。x, y座標の値は-2000から2000の間。」

Output

The output should consist of as many lines as the number of polygons. The k-th output line should print an integer which is the area of the k-th polygon, approximated in the way described above. No other characters, including whitespaces, should be printed.
 「出力には多角形の数だけの行にすること。k行目にk番目の多角形の面積を表す整数にすること。スペースを含め、他の文字はいっさい、出力に入れてはいけない。」

Sample Input

4
5 -3
1 0
1 7
-7 -1
3
5 5
18 5
5 10
3
-5 -5
-5 -10
-18 -10
5
0 0
20 2
11 1
21 2
2 0
0

Output for the Sample Input

55
41
41
23

Problem B
Lagrange’s Four-Square Theorem
---- 2003年 会津大会 ----

The fact that any positive integer has a representation as the sum of at most four positive squares (i.e. squares of positive integers) is known as Lagrange’s Four-Square Theorem. The first published proof of the theorem was given by Joseph-Louis Lagrange in 1770. Your mission however is not to explain the original proof nor to discover a new proof but to show that the theorem holds for some specific numbers by counting how many such possible representations there are.
 「任意の正の整数が最大4つの平方数の和で表すことができる。そのことは Lagrange の4平方定理として知られている。その証明は1770年 J. L. Lagrange によって既になされたが、ここで、いくつかの数字について定理が成り立つことを、数式の個数を数えあげることで示して欲しい。」

For a given positive integer n, you should report the number of all representations of n as the sum of at most four positive squares. The order of addition does not matter, e.g. you should consider 42 + 32 and 32 + 42 are the same representation.
 「ある正の整数 n について、最大4つの平方数の和として成り立つ数式すべての数を知らせること。加算の順序は問題にしない。つまり、42 + 32 と 32 + 42は同じものだ。」

For example, let’s check the case of 25. This integer has just three representations 12+22+22+42, 32 + 42, and 52. Thus you should report 3 in this case. Be careful not to count 42 + 32 and 32 + 42 separately.
 「例えば、25について確認しよう。25は3つの数式で表すことができる。したがって、3と報告しないといけない。」

Input

The input is composed of at most 255 lines, each containing a single positive integer less than 215, followed by a line containing a single zero. The last line is not a part of the input data.
 「入力は最大255行ある。各行に215未満の正の整数が1つ書かれている。入力の最後の行に0が入るが、入力データではない。」

Output

The output should be composed of lines, each containing a single integer. No other characters should appear in the output.
 「出力の各行に整数1つにすること。ほかの文字を入れてはいけない。」

The output integer corresponding to the input integer n is the number of all representations of n as the sum of at most four positive squares.
 「この整数は、入力のnに対し、nを最大4つの平方数の和で表現する数式の個数のことだ。」

Sample Input

1
25
2003
211
20007
0

Output for the Sample Input

1
3
48
7
738

パネルを覆うカーペットの最小枚数を決定する問題。

プログラムを楽しく書いている。実用性のありそうな問題なので、本当に楽しい。多くのテキストにあるような、意味不明な四則演算で言語学習するよりも、そういう面白い実例があれば、学習の動機付けに効果的だろう。

Square Carpets --- 2003年 会津大会 国内予選 問題E

[ Problem ]
 Mr. Frugal bought a new house. He feels deeply in love with his new house because it has a comfortable living room in which he can put himself completely at ease. He thinks his new house is a really good buy.
 「新しく住宅を買った。使いやすいリビングルームを見て、満足している。」

 But, to his disappointment, the floor of its living room has some scratches on it.
 「ただ、リビングルームは床にキズが何箇所にある。」

 The floor has a rectangle shape, covered with square panels. He wants to replace all the scratched panels with flawless panels, but he cannot afford to do so. Then, he decides to cover all the scratched panels with carpets.
 「床は四角い形だが、正方形のパネルに覆われている。キズのあるパネルを取り替える経済的余裕がないので、カーペットを敷くことにした。」
 
 The features of the carpets he can use are as follows.
 「使えるカーペットに、つぎの条件がついている。」

   1. Carpets are square-shaped.
   2. Carpets may overlap each other.
   3. Carpets cannot be folded.
   4. Different sizes of carpets are available. Lengths of sides of carpets are multiples of that of the panels.
  「1.正方形。
   2.互いにオーバーラップできる。
   3.折り曲げることはできない。
   4.さまざまなサイズのものが使えるが、それぞれのサイズはパネルの整数倍と考えてよい。」
 
 The carpets must cover all the scratched panels, but must not cover any of the flawless ones.
 「キズのあるパネルはカーペットで覆わなければいけないが、キズのないパネルは覆ってはいけない。」

 For example, if the scratched panels are as shown in Figure 1, at least 6 carpets are needed.
 「例えば、図1のキズに対し、最低6枚のカーペットが必要。」


Figure 1: Example Covering

 As carpets cost the same irrespective of their sizes, Mr. Frugal would like to use as few number of carpets as possible.
 「サイズに関係なく、カーペットは皆同じ値段で買える。したがって、できるだけ少ない枚数にすべきだ。」

 Your job is to write a program which tells the minimum number of the carpets to cover all the scratched panels.
 「キズのついたパネルを覆うカーペットの最小枚数を決めてくれ。」

[ Input ]
 The input consists of multiple data sets. As in the following, the end of the input is indicated by a line containing two zeros.
 「入力に複数のデータセットが含まれる。入力の終了として、最終行に0が2つ入る。」

   DataSet1
   DataSet2
   ...
   DataSetn
   0 0

 Each data set (DataSeti) represents the state of a floor. The format of a data set is as follows.
 「それぞれのデータセットは床の状態を示す。データセットのフォーマットはつぎの通り。」

   W H
   P11 P12 P13 ... P1W
   P21 P22 P23 ... P2W
   ...
   PH1 PH2 PH3 ... PHW

 The positive integers W and H are the numbers of panels on the living room in the x- and y- direction, respectively. The values of W and H are no more than 10. The integer Pyx represents the state of the panel. The value of Pyx means,
 「W, H (10以下の正整数)、リビングルームのx, y方向のパネルの数。Pyx (整数)、パネルの状態を示す。」

   0: flawless panel (must not be covered),
   1: scratched panel (must be covered).
   「Pyxの値が0のものは、キズのないパネルを示す。覆ってはいけない。
    値が1のものは、キズのついたパネルを示す。覆うべきだ。」

[ Output ]
 For each data set, your program should output a line containing one integer which represents the minimum number of the carpets to cover all of the scratched panels.
 「それぞれのデータセットに対し、キズのついたパネルを覆うカーペットの最小枚数を整数1行に出力せよ。」

[ Sample Input ]
4 3
0 1 1 1
1 1 1 1
1 1 1 1
8 5
0 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 0 1 1 1 1
0 1 1 1 0 1 1 1
8 8
0 1 1 0 0 1 1 0
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
0 1 1 0 0 1 1 0
0 1 1 0 0 1 1 0
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
0 1 1 0 0 1 1 0
10 10
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 0 1 1 0 1 1 0 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 0 1 1 0 1 1 0 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 0 1 1 0 1 1 0 1
1 1 1 1 1 1 1 1 1 1
0 0

[ Output for the Sample Input ]
2
6
14
29

宇宙ステーションの連結通路の全長を最短にする問題。

Building a Space Station --- 2003年 会津大会 国内予選 問題D

[ Problem ]
 You are a member of the space station engineering team, and are assigned a task in the construction process of the station. You are expected to write a computer program to complete the task.
 「宇宙ステーションのエンジニアとしてプログラムの作成に期待されている。」

 The space station is made up with a number of units, called cells. All cells are sphere-shaped, but their sizes are not necessarily uniform. Each cell is fixed at its predetermined position shortly after the station is successfully put into its orbit. It is quite strange that two cells may be touching each other, or even may be overlapping. In an extreme case, a cell may be totally enclosing another one. I do not know how such arrangements are possible.
 「宇宙ステーションはセルと呼ばれている複数のユニットによってつくられている。すべてのセルは球の形をしているが、サイズは様ざま。周回軌道に入った後に、セルが予定した位置に固定させるが、セル同士がくっ付いたり、オーバーラップしたり、極端の場合ほかのセルに入れられたりすることもできる。」

 All the cells must be connected, since crew members should be able to walk from any cell to any other cell. They can walk from a cell A to another cell B, if, (1) A and B are touching each other or overlapping, (2) A and B are connected by a `corridor', or (3) there is a cell C such that walking from A to C, and also from B to C are both possible. Note that the condition (3) should be interpreted transitively.
 「クルー達が移動できるために、すべてのセルは繋がるべきだ。セルAからセルBに移動できる条件とは、(1) AとBとがくっ付いているか、オーバーラップしている。(2) AとBとが通路によって繋いでいる。(3) 間にセルCがあって、AからCへ、BからCへ移動できる場合。(3)のケースでは通過のためと解釈する。」

 You are expected to design a configuration, namely, which pairs of cells are to be connected with corridors. There is some freedom in the corridor configuration. For example, if there are three cells A, B and C, not touching nor overlapping each other, at least three plans are possible in order to connect all three cells. The first is to build corridors A-B and A-C, the second B-C and B-A, the third C-A and C-B. The cost of building a corridor is proportional to its length. Therefore, you should choose a plan with the shortest total length of the corridors.
 「セルペア同士を通路によって繋げる配置をデザインして欲しい。通路の配置に自由度がある。例えば、くっ付いたり、オーバーラップしていないセル3つA、B、Cがあるとすると、少なくとも3つのプランが考えられる。つまり、A-BとA-Cの繋ぐ通路をつくるプラン、B-CとB-Aのプラン、C-AとC-Bのプラン。通路の建設費用は長さに依存する。したがって、すべての通路の総長が最短となる通路の建設プランを選ぶべきだ。」

 You can ignore the width of a corridor. A corridor is built between points on two cells' surfaces. It can be made arbitrarily long, but of course the shortest one is chosen. Even if two corridors A-B and C-D intersect in space, they are not considered to form a connection path between (for example) A and C. In other words, you may consider that two corridors never intersect.
 「通路の幅は無視してよい。通路はセルの表面からつくる。通路の長さに制限はないが、短いほうにすべきだろう。A-BとC-Dとの通路が空中で交叉しても、AとCの間に通路があるとは考えない、つまり、交叉は起きないと考えてもいい。」

[ Input ]
 The input consists of multiple data sets. Each data set is given in the following format.
 「入力に複数のデータセットが含まれる。各データセットは以下のフォーマット。」

   n
   x1 y1 z1 r1
   x2 y2 z2 r2
   ...
   xn yn zn rn

 The first line of a data set contains an integer n, which is the number of cells. n is positive, and does not exceed 100.
 「n (100以下の正整数)、セルの数。」

 The following n lines are descriptions of cells. Four values in a line are x-, y- and z-coordinates of the center, and radius (called r in the rest of the problem) of the sphere, in this order. Each value is given by a decimal fraction, with 3 digits after the decimal point. Values are separated by a space character.
 「セルの記述にn行がつぎに続く。4つの値 x, y, z, r はそれぞれ、セル中心のx, y, z座標、および半径。各値は小数点以下3桁の数字となる。

 Each of x, y, z and r is positive and is less than 100.0.
 「x, y, z, r は100未満の正数。」

 The end of the input is indicated by a line containing a zero.
 「入力の終了として、最終行に0が入る。」

[ Output ]
 For each data set, the shortest total length of the corridors should be printed, each in a separate line. The printed values should have 3 digits after the decimal point. They may not have an error greater than 0.001.
 「各データセットに対し、通路の全長の最短長さを表示せよ。小数点以下3桁の数字で表示すること。0.001以上の誤差を越えないこと。」

 Note that if no corridors are necessary, that is, if all the cells are connected without corridors, the shortest total length of the corridors is 0.000.
 「通路が必要なければ、つまりすべてのセルが通路なしでも繋いでいる場合には、通路の長さを0.000とせよ。」

[ Sample Input ]
3
10.000 10.000 50.000 10.000
40.000 10.000 50.000 10.000
40.000 40.000 50.000 10.000
2
30.000 30.000 30.000 20.000
40.000 40.000 40.000 20.000
5
5.729 15.143 3.996 25.837
6.013 14.372 4.818 10.671
80.115 63.292 84.477 15.120
64.095 80.924 70.029 14.881
39.472 85.116 71.369 5.553
0

[ Output for the Sample Input ]
20.000
0.000
73.834

The Secret Number --- 2003年 会津大会 国内予選 問題C

[ Problem ]
 Your job is to find out the secret number hidden in a matrix, each of whose element is a digit ('0'-'9') or a letter ('A'-'Z'). You can see an example matrix in Figure 1.
 「マトリックスに隠されているシクレットナンバーを見つけ出しなさい。マトリックスの各要素は数字か文字。」


Figure 1: A Matrix

 The secret number and other non-secret ones are coded in a matrix as sequences of digits in a decimal format. You should only consider sequences of digits D1 D2 ... Dn such that Dk+1 (1 <= k < n) is either right next to or immediately below Dk in the matrix. The secret you are seeking is the largest number coded in this manner.
 「シクレットナンバーとそうでないものは、10進数の列としてマトリックスに埋め込まれている。数字列の D1 D2 ... Dn において、Dk+1はDkのすぐ右隣か真下にある。この方法で見つけ出す最大の数字がクレジットナンバーだ。」

 Four coded numbers in the matrix in Figure 1, i.e., 908820, 23140037, 23900037, and 9930, are depicted in Figure 2. As you may see, in general, two or more coded numbers may share a common subsequence. In this case, the secret number is 23900037, which is the largest among the set of all coded numbers in the matrix.
 「図1に4つの数字 908820、23140037、23900037、及び 9930 が、図2の通り、マトリックスにある。一般的に、複数の数字列が一部共有することもありえる。すべての数字の中から、最大の 23900037 がクレジットナンバーになる。」


Figure 2: Coded Numbers

 In contrast, the sequences illustrated in Figure 3 should be excluded: 908A2 includes a letter; the fifth digit of 23149930 is above the fourth; the third digit of 90037 is below right of the second.
 「一方、図3のものは除外しないといけない。908A2は文字を含むし、23149930は5番目の数字が4番目の上に来ているし、90037は3文字目が2文字目の右下にあるから。」


Figure 3: Inappropriate Sequences

[ Input ]
 The input consists of multiple data sets, each data set representing a matrix. The format of each data set is as follows.
 「入力に複数のデータセットが含まれる。各データセットがマトリックスを表す。」

   W H
   C11C12 ... C1W
   C21C22 ... C2W
   ...
   CH1CH2 ... CHW

 In the first line of a data set, two positive integers W and H are given. W indicates the width (the number of columns) of the matrix, and H indicates the height (the number of rows) of the matrix. W+H is less than or equal to 70.
 「W, H (それぞれ70以下の正整数)、マトリックスの横幅と高さ。」

 H lines follow the first line, each of which corresponds to a row of the matrix in top to bottom order. The i-th row consists of W characters Ci1Ci2 ... CiW in left to right order. You may assume that the matrix includes at least one non-zero digit.
 「H行がつぎに続く。各行は上から下までのマトリックス各行を示す。マトリックスには少なくとも0以外の数字を1つ含むと仮定してよい。」

 Following the last data set, two zeros in a line indicate the end of the input.
 「入力の終了として、最後の行に0二つが入る。」

[ Output ]
 For each data set, print the secret number on a line. Leading zeros should be suppressed.
 「各データセットに対し、1行ずつクレジットナンバーを表示せよ。先頭の0は表示してはいけない。」

[ Sample Input ]
7 4
9R2A993
0E314A0
8A900DE
820R037
6 7
JH03HE
ID7722
0DA1AH
30C9G5
99971A
CA7EAI
AHLBEM
20 2
A1234567891234CBDEGH
BDEDF908034265091499
0 0

[ Output for the Sample Input ]
23900037
771971
12345908034265091499

Get Many Persimmon Trees --- 2003年 会津大会 国内予選 問題B

[ Problem ]
 Seiji Hayashi had been a professor of the Nisshinkan Samurai School in the domain of Aizu for a long time in the 18th century. In order to reward him for his meritorious career in education, Katanobu Matsudaira, the lord of the domain of Aizu, had decided to grant him a rectangular estate within a large field in the Aizu Basin. Although the size (width and height) of the estate was strictly specified by the lord, he was allowed to choose any location for the estate in the field. Inside the field which had also a rectangular shape, many Japanese persimmon trees, whose fruit was one of the famous products of the Aizu region known as 'Mishirazu Persimmon', were planted. Since persimmon was Hayashi's favorite fruit, he wanted to have as many persimmon trees as possible in the estate given by the lord.
 「教育における功績のご褒美として、会津の大名から四角い土地をもらえることになった。サイズは大名が決めるが、土地の場所はブロック内ならどこでもいいらしい。ブロック内に、会津名物の柿木があちこちに植えてあったので、できるだけ多くの木を囲む土地を選びたい。」

 For example, in Figure 1, the entire field is a rectangular grid whose width and height are 10 and 8 respectively. Each asterisk (*) represents a place of a persimmon tree. If the specified width and height of the estate are 4 and 3 respectively, the area surrounded by the solid line contains the most persimmon trees. Similarly, if the estate's width is 6 and its height is 4, the area surrounded by the dashed line has the most, and if the estate's width and height are 3 and 4 respectively, the area surrounded by the dotted line contains the most persimmon trees. Note that the width and height cannot be swapped; the sizes 4 by 3 and 3 by 4 are different, as shown in Figure 1.
 「例えば、図1に横10縦8のブロックを表す。アスタリスク (*) は木の植えてある場所を示す。横幅4高さ3サイズの土地なら、実線で囲んだ土地に木が最も多い。横幅6高さ4の土地ならダッシュで示したものが最も木が多い。横幅3高さ4の土地なら点線の土地が最も理想的だ。ただし、注意して欲しいのは、横幅と高さを入れ替えてはいけないこと。つまり、3x4と4x3は違うサイズ。」


Figure 1: Examples of Rectangular Estates

 Your task is to find the estate of a given size (width and height) that contains the largest number of persimmon trees.
 「与えられたサイズ(横幅と高さ)に対し、最も多くの柿木を囲む土地の場所を決めてくれ。」

[ Input ]
 The input consists of multiple data sets. Each data set is given in the following format.
 「入力に複数のデータセットを含む。各データセットのフォーマットは以下の通り。」

   N
   W H
   x1 y1
   x2 y2
   ...
   xN yN
   S T

 N is the number of persimmon trees, which is a positive integer less than 500. W and H are the width and the height of the entire field respectively. You can assume that both W and H are positive integers whose values are less than 100. For each i (1 <= i <= N), xi and yi are coordinates of the i-th persimmon tree in the grid. Note that the origin of each coordinate is 1. You can assume that 1 <= xi <= W and 1 <= yi <= H, and no two trees have the same positions. But you should not assume that the persimmon trees are sorted in some order according to their positions. Lastly, S and T are positive integers of the width and height respectively of the estate given by the lord. You can also assume that 1 <= S <= W and 1 <= T <= H.
 「N (500未満の正の整数)、柿木の数。W, H (それぞれ100未満の正の整数)、ブロックの横幅と高さ。xi, yi、i番目の木の位置。座標の原点は1であることに注意。同じ座標に木が2本以上あることはないが、座標の順番はソートされていない。S, T、大名から与えられた土地の横幅と高さ。」

 The end of the input is indicated by a line that solely contains a zero.
 「入力の終了として、最後の行に0が入る。」

[ Output ]
 For each data set, you are requested to print one line containing the maximum possible number of persimmon trees that can be included in an estate of the given size.
 「それぞれのデータセットに対し、与えられたサイズの土地で囲める最大の柿木の本数を1行ずつ出力せよ。」

[ Sample Input ]
16
10 8
2 2
2 5
2 7
3 3
3 8
4 2
4 5
4 8
6 4
6 7
7 5
7 8
8 1
8 4
9 6
10 3
4 3
8
6 4
1 2
2 1
2 4
3 4
4 2
5 3
6 1
6 2
3 2
0

[ Output for the Sample Input ]
4
3