▶ 問題番号【０１】じゃんけん

配 点 : １５

問 題
仲良し 5 人組でじゃんけんをすることになりました。じゃんけんとは、グー、チョキ、パーという 3つの手があり、グーとチョキの勝負ならグーが「勝ち」・チョキが「負け」、チョキとパーなら、チョキが「勝ち」・パーが「負け」、パーとグーならパーが「勝ち」・グーが「負け」というルールです。全員が同じ手、またはグー、チョキ、パー全てが出た場合は「あいこ」となります。
5 人のじゃんけんの手を入力とし、それぞれの人の勝敗を出力するプログラムを作成してください。
じゃんけんの手は、グーは 1、チョキは 2、パーは 3 の数字で表します。勝敗は「勝ち」を 1、「負け」を 2、「あいこ」を 3 の数字で表し、入力順に従って出力します。

入 力
複数のデータセットの並びが入力として与えられます。入力の終わりはゼロひとつの行で示されます。
各データセットの並びは以下のとおりです。
1 行目
2 行目
3 行目
4 行目
5 行目

1 人目の手 （整数）
2 人目の手3 人目の手4 人目の手5 人目の手出 力
入力データセットごとに、5 人の勝敗を出力します。

パソコン甲子園２００９本選問題 問題番号０１【１／２ページ】

出力例

入力例
12321122210

パソコン甲子園２００９本選問題 問題番号０１3333
312221【２／２ページ】

▶ 問題番号【０２】

旅行はいつ？

配 点 : １５問 題
あなたは友人と旅行に行きたいと考えています。ところが、浪費癖のある友人はなかなか旅行費用を貯めることができません。友人が今の生活を続けていると、旅行に行くのはいつになってしまうか分かりません。そこで、早く旅行に行きたいあなたは、友人が計画的に貯蓄することを助けるプログラムを作成することにしました。
友人のある月のお小遣いを M 円、その月に使うお金を N 円とすると、その月は（M-N）円貯蓄されます。毎月の収支情報 M 、 N を入力とし、貯蓄額が旅行費用 L に達するのにかかる月数を出力するプログラムを作成してください。ただし、12 ヶ月を過ぎても貯蓄額が旅行費用に達しなかった場合はNA と出力してください。
なお、 L は 1 以上 1,000,000 以下の整数とし、M、N はそれぞれ 0 以上 100,000 以下の整数とします。
ただし、N は同じ月の M を超えないものとします。

入 力
複数のデータセットの並びが入力として与えられます。入力の終わりはゼロひとつの行で示されます。
各データセットは以下の通りです。
1 行目 旅行費用 L（整数）
2 行目 1 月目の収支情報 M N (整数 整数；半角空白区切り)
3 行目 2 月目の収支情報：
13 行目 12 月目の収支情報

出 力
入力データセットごとに、貯蓄額が旅行費用に達するのにかかる月数を出力します。

パソコン甲子園２００９本選問題 問題番号０２【１／２ページ】

出力例

入力例
100005000 3150
5000 5000
0 06NA

5000 1050
5000 3980
5000 210
5000 5000
5000 5000
0 05000 2100
5000 2100
5000 2100
29170
100000 100000
100000 100000
100000 100000
100000 100000
100000 100000
100000 100000
100000 100000
100000 100000
100000 100000
100000 100000
100000 100000
100000 70831
0

パソコン甲子園２００９本選問題 問題番号０２【２／２ページ】

▶ 問題番号【０３】ブロック

配 点 : ４０

問 題
A さんの家に親戚の B 君がやってきました。彼は 3 歳でブロックが大好きです。彼が持っているブロックは図 1 のような形をしています。

図１
B 君はボードの上にブロックを敷き詰めています。彼に「何を作っているの？」と聞くと、彼は「迷路！！」と元気よく答えました。彼の言う迷路とは、スタートからゴールまで側面が接している、同じ色のブロックだけでたどることができるブロックの配置のことだそうです。図 2 は黄色のブロックにより、左上（スタート）から右下（ゴール）へ迷路ができていることを表しています。
スタート横縦ゴール

図２
無邪気に遊んでいる B 君を横目に、冷静なプログラマーであるあなたは、ブロックの並びが迷路となっているかを確かめてみることにしました。
ブロックの情報とスタート、ゴールの座標を入力とし、ブロックが迷路となっていれば OK 、なっていなければ NG を出力するプログラムを作成してください。
ボードは横方向に w 、縦方向に h（それぞれ 4 以上 100 以下の整数）の大きさをもち、 左上の座標は（ 1 , 1 ）、右下の座標は( w , h )とします。ブロックは 2 × 4 の長方形ですべて同じ大きさです。ブロックの色 c は 1 （白）、 2 （黄）、3（緑）、4（青）、5（赤）、のいずれかです。ブロックのボード上での向き d は 横方向に長い場合 0 、 縦方向に長い場合 1 とします。ブロックの位置はブロックの左上の座標（ x , y ）によって表されます。なお、ブロックの位置は他のブロックと重なることは無く、ボードからはみ出すこともありません。

パソコン甲子園２００９本選問題 問題番号０３【１／３ページ】

入 力
複数のデータセットの並びが入力として与えられます。入力の終わりはゼロふたつの行で示されます。
各データセットは以下のとおりです。
1 行目
2 行目
3 行目
4 行目
5 行目

ボードの大きさ w h （整数 整数；半角空白区切り）
スタートの座標 xs ys（整数 整数；半角空白区切り）
ゴールの座標 xg yg（整数 整数；半角空白区切り）
ブロックの個数 n（整数）
第 1 のブロックの情報 c d x y (整数 整数 整数 整数；半角空白区切り)
各記号の意味は以下のとおりです。
c ：ブロックの色
d ：ブロックの向き
x , y ：ブロックの位置
6 行目 第 2 のブロックの情報：n+4 行目 第 n のブロックの情報

出 力
入力データセットごとに、判別結果を出力します。

パソコン甲子園２００９本選問題 問題番号０３【２／３ページ】

出力例

入力例
20 20
1 19 972 0 1 15 1 1 32 1 3 3
1 1 5 25 1 7 32 0 2 7
2 0 6 820 20
9 9
1 1OKNG6
2 0 1 1
1 0 5 12 1 1 35 0 1 73 1 5 54 1 8 50 0

パソコン甲子園２００９本選問題 問題番号０３【３／３ページ】

▶ 問題番号【０４】

病院の部屋番号

配 点 : ４０

問 題
ウォーターデブンに住む建築家のデブンキーさんのもとに、古い大病院を改装する仕事の依頼が舞い込んできました。
国によっては忌み数（いみかず）として嫌われる数字を部屋番号に用いたくない人がいます（日本では 4 と 9 が有名です）。しかし、この病院の部屋番号は忌み数に関係なく、1 から順番に付けられていました。
それが気になったデブンキーさんは、機材やベッドの入れ替えが全て終わる前にウォーターデブンの忌み数である「4」と「6」を除いた数字で部屋番号を付けなおしてしまいました。しかし、入れ替え作業は旧部屋番号で計画していたので、残りの作業を確実に行うには旧部屋番号を新部屋番号に変換する必要があります。計算が苦手なデブンキーさんはこのことに気づいて愕然としています。
そんなデブンキーさんのために、旧部屋番号を入力とし対応する新部屋番号を出力するプログラムを作成してください。ただし、旧部屋番号は 1 以上 1,000,000,000 以下の整数とします。
15 番目までの部屋番号の対応表は以下のようになります。

旧部屋番号
新部屋番号

1
1223345576879810911101211131215131714181519

入 力
複数のデータセットの並びが入力として与えられます。入力の終わりはゼロひとつの行で示されます。
各データセットは以下の通りです。
1 行目 旧部屋番号 n（整数）

出 力
入力データセットごとに、新部屋番号を出力します。

パソコン甲子園２００９本選問題 問題番号０４【１／２ページ】

出力例

入力例
151001000000000
30

パソコン甲子園２００９本選問題 問題番号０４191559358757000
3【２／２ページ】

▶ 問題番号【０５】

写真に写っている景色は？

配 点 : ４０問 題
A 君は会津に観光にやってきました。宿泊したホテルの窓からは会津盆地が一望できます。景色を眺めていると、床に写真の切れ端が落ちているのに気がつきました。どうやら窓から外の景色を撮ったようです。
「どの辺りを撮ったのかな」と、A 君は窓の外の景色と写真が同じ大きさになるように写真をかざして、写真と窓の外の景色が一致する場所を探し始めました。
それでは、A 君がやっていることをコンピュータでやってみましょう。窓の外の景色を n × n マスの正方形に分割します（ n を景色の大きさと呼びます）。各マスには、そのマスの画像の情報を表す 0以上の整数が書かれています。マスの位置は座標（x , y）で表します。各マスの座標は以下の通りになります。

(1,1) (2,1) … (n,1)(1,2) (2,2) … (n,2):::(1,n) (2,n) … (n,n)
写真の切れ端は、m × m マスの正方形で表されます（ m を写真の切れ2 -1 -1 -1端の大きさと呼びます）。この正方形の中で、切れ端の部分のマスには画0 3 -1 -1像の情報が、切れ端に含まれない部分のマスには -1 が書かれています。
-1 2 2 4
たとえば、右の図では、色が塗られている部分が実際の写真の切れ端の形-1 1 -1 1を表しています。切れ端に穴が開いていることはありますが、必ず 1 つにつながっています。
（0 以上の値をもつマスが頂点だけで接しているときは、つながっていないものとみなします。
）また、値 -1 のマスが縦または横 1 列に端から端まで並ぶことはありません。
窓から見える景色の中で、写真の切れ端を 0、90、180、270 度
2 1 3 1 1 5 1 3回転させたいずれかと一致する領域を探します。たとえば、景色が右図のように表わせるとき、上図の切れ端を反時計回りに90 度回転させると、色が塗られた領域に一致します。
窓から見える景色と写真の切れ端の情報を入力とし、景色の中で、切れ端を 0、90、180、270 度回転させたいずれかと一致する領域の最も上端に近いマスのうち、最も左端に近いマスの座標を出力するプログラムを作成してください。
一致する領域が複数ある場合は、それらの領域内にある

2 3 2 4 1 0 210 3 1 2 1 1 421 2 3 2 1 1 540 2 0 1 2 3 211 3 1 2 1 3 325 1 2 1 4 2 244 1 1 0 1 1 21

マスの中で、最も上端に近いマスのうち、最も左端に近いマスの座標を出力してください。一致する領域がないときは、NA と出力します。
ただし、n は 1 以上 100 以下の整数、m は 1 以上 50 以下の整数、画像の情報を表す整数は 0 以上 15以下とします。窓から見える景色と写真の切れ端のデータは、各行ごとに左から右の順にマスの値が与えられます。また、m は n を超えない大きさとします。

パソコン甲子園２００９本選問題 問題番号０５【１／３ページ】

入 力
複数のデータセットの並びが入力として与えられます。入力の終わりはゼロふたつの行で示されます。各データセットは以下のとおりです。
1 行目 n m（整数 整数；半角空白区切り）
2 行目 窓から見える景色の 1 行目のデータ（n 個の整数 ; 半角空白区切り）
3 行目 窓から見える景色の 2 行目のデータ：
n+1 行目 窓から見える景色の n 行目のデータ
n+2 行目 写真の切れ端の 1 行目のデータ（m 個の整数 ; 半角空白区切り）
n+3 行目 写真の切れ端の 2 行目のデータ：
n+m+1 行目 写真の切れ端の m 行目のデータ

出 力
入力データセットごとに、マスの位置の座標を出力します。

パソコン甲子園２００９本選問題 問題番号０５【２／３ページ】

出力例

入力例
8 42 1 3 1 1 5 1 32 3 2 4 1 0 2 10 3 1 2 1 1 4 2
1 2 3 2 1 1 5 40 2 0 1 1 3 2 1
1 3 1 2 2 4 3 25 1 2 1 4 1 1 54 1 1 0 1 2 2 12 -1 -1 -1
0 3 -1 -1-1 2 2 4-1 1 -1 1
5 34 2NA1 0 2 3 5
2 3 7 2 1
2 5 4 2 2
8 9 0 3 3
3 6 0 4 7-1 -1 2-1 3 50 4 -10 0

パソコン甲子園２００９本選問題 問題番号０５【３／３ページ】

▶ 問題番号【０６】ザ・スクエアーズ

配 点 : ５０

問 題
この度、有名なテーマパークに、巨大迷路ザ・スクエアーズが新しく完成しました。
消防署の指導により避難訓練をしなければなりませんが、巨大迷路なだけに訓練にかかる時間を予測することができません。そこで、あなたは以下の仕様をもとに避難訓練シミュレータを開発することになりました。
巨大迷路は図 1 に示すように、横 W 、縦 H の W × H 個のマス目で表わされます。各マス目は、通路（白いマス目）、壁（茶色いマス目）、非常口（ ）のいずれかです。図中の○は人を表し、その中のアルファベット（E、W、S、N）はその人が向いている方角（東西南北）を表しています。図は上方向が北になるように描かれています。
N

図１

巨大迷路内にいる人は最初、東西南北のいずれかの方向を向いて立っています。各人は 1 秒単位で同時に次に示す手順で移動を試みます。
① 現在向いている方向の、右、前、左、後のマス目を順番に調べ、最初に見つけた、空いている通路または非常口の方向に向きを変えます。そのようなマス目が無い場合は向きを変えません。
② 目の前のマス目が空いていて、他の人の目の前のマス目になっていない場合は移動します。同じマス目を目の前のマスとする人が複数いる場合は、そのマス目の、東、北、西、南のマス目にいる人の順で選択された 1 人が移動します。
移動後に非常口に到着した人は、無事避難し迷路内から消えます。
与えられた巨大迷路と人の位置情報を入力とし、全ての人が避難し終える時間を出力するプログラ
ムを作成してください。脱出に 180 秒より長い時間を要する場合は NA と出力して下さい。迷路と人の位置情報は、 H 行 W 列の文字によって与えられます。ただし、 H 、 W は 1 以上 30 以下の整数とします。各文字の意味は以下のとおりです。
# 壁.（ピリオド）床X 非常口E 東を向いている人
N 北を向いている人
W 西を向いている人
S 南を向いている人
なお、迷路と外部との境界は壁 # または非常口 X のいずれかです。

パソコン甲子園２００９本選問題 問題番号０６【１／３ページ】

入 力
複数のデータセットの並びが入力として与えられます。入力の終わりはゼロふたつの行で示されます。
各データセットは以下のとおりです。
1 行目 迷路の大きさ横 W 縦 H （整数 整数 ; 半角空白区切り）
2 行目 迷路の 1 行目の情報 (半角英文字列)：
H+1 行目 迷路の H 行目の情報

出 力
入力データセットごとに、全ての人が避難し終える時間を出力します。

パソコン甲子園２００９本選問題 問題番号０６【２／３ページ】

出力例

入力例
10 3###########E.......X##########
4 4####
#N.#
#..X
####
5 5#####
#N..#
###.X
#S..#

8NA
916
10#####
6 6#######..#X##.EE.#####N##....#######
8 8##X######....E.######.###.#...###.W.#..##.#.N#.X#X##.#.#########
0 0

パソコン甲子園２００９本選問題 問題番号０６【３／３ページ】

▶ 問題番号【０７】みんなでジョギング

配 点 : ５０

問 題
赤ベコ小学校では、生徒全員が参加してちょっと変わったジョギングをします。生徒は、それぞれ独自の周回コースを、自分のペースで走ります。それぞれ自分のコースを 1 周すると小学校に戻ってきます。全員が小学校を同時にスタートしてから、全員が同時に小学校で最初に出会うのは、それぞれ何周したときでしょうか？
生徒の人数 n、各生徒のコースの 1 周の距離 d（km）、各生徒の走る速さ v（km/時間）を入力とし、全員が小学校を同時にスタートしてから次に同時に小学校に位置するのは、各生徒がそれぞれ何周したときかを出力するプログラムを作成してください。また、生徒の人数 n は 2 以上 10 以下、各生徒のコースの 1 周の距離 d と走る速さ v はともに 1 以上 10000 以下の整数とします。なお、各生徒は231-1 周を超えて走ることはありません。各生徒の周回数は入力の順番に従って出力してください。

入 力
複数のデータセットの並びが入力として与えられます。入力の終わりはゼロひとつの行で示されます。
各データセットは以下のとおりです。
1 行目 生徒の人数 n（整数）2 行目 1 人目の情報 d v （整数 整数；半角空白区切り）
3 行目 2 人目の情報：
n+1 行目 n 人目の情報

出 力
入力データセットごとに、各生徒の周回数を出力します。

パソコン甲子園２００９本選問題 問題番号０７【１／２ページ】

出力例

入力例
243545789 289
166 4694617 252
972 30315161598397732
1209243492
1939462992
1782294192
1360317793
1128532 200

パソコン甲子園２００９本選問題 問題番号０７【２／２ページ】

▶ 問題番号【０８】高速バス

配 点 : ５０

問 題
A 君は高校の休みを利用して、高速バス（以下、「バス」）で一人旅をする計画を立てています。まず、A 君は一番行ってみたい町を選んでそこを目的地にしました。次に出発地から目的地までバスを乗り継いでいくルートを決めなければなりません。乗り継ぎをするときは、バスを降りてから別のバスに乗り換えるので、それぞれのバスの乗車券が必要になります。
A 君は親戚のおじさんからバスの割引券を何枚かもらいました。この券を 1 枚使うと乗車券 1 枚を半額で購入できます。例えば、図 1 の出発地５から目的地１へ行く場合には、５→４→６→２→１と５→３→１の二つの経路が考えられます。割引券が 2 枚あるとすると、交通費を最も安くするには５→４→６→２→１の経路をたどった場合、４→６と６→２の路線に割引を利用し、合計料金は 4600円となります。一方、５→３→１の経路をたどった場合、５→３と３→１の路線に割引を利用し、合計料金は 3750 円となります。
A 君は観光にお金を回したいので、交通費はできるだけ少なくしようと考えています。そこで A 君は、出発地から目的地までの最も安い交通費を求めるプログラムを作成することにしました。

目的地

22000 円

1500 円

62200 円

414500 円

1000 円
33000 円

5出発地

図１
割引券の枚数、バスがつなぐ町の数、バスの路線数、各バスの路線情報を入力とし、出発地から目的地までの最も安い交通費を出力するプログラムを作成してください。ただし、割引券の枚数 c は 1以上 10 以下、バスがつなぐ町の数 n は 2 以上 100 以下、バスの路線数 m は 1 以上 500 以下の整数とします。各バスは双方向に同一料金で運行しており、料金 f は 1000 以上 10000 以下の 100刻みの整数です。また、町は、それぞれ異なる 1 から n までの番号が振られています。出発地 s と目的地 d は別の町ですが、経路は必ずあるものとします。

パソコン甲子園２００９本選問題 問題番号０８【１／３ページ】

入 力
複数のデータセットの並びが入力として与えられます。入力の終わりはゼロいつつの行で示されます。
各データセットは以下のとおりです。
1 行目 c n m s d (それぞれ整数 ; 半角空白区切り)
2 行目 第 1 のバスの路線情報 a b f （整数 整数 整数；半角空白区切り）
各記号の意味は以下のとおりです。
a b：バスの路線の始点と終点の町番号
f：この路線の料金
3 行目 第 2 のバスの路線情報:m+1 行目 第 m のバスの路線情報

出 力
入力データセットごとに、最も安い交通費を出力します。

パソコン甲子園２００９本選問題 問題番号０８【２／３ページ】

出力例

入力例
1 3 3 1 3
1 3 2000
1 2 1000
2 3 1000
2 3 3 1 3
1 3 2300
1 2 1000
2 3 1200
2 6 6 5 1
1 2 1500
1 3 4500
2 6 2000
5 4 1000
6 4 2200

1000
11003750

3 5 30000 0 0 0 0

パソコン甲子園２００９本選問題 問題番号０８【３／３ページ】

▶ 問題番号【０９】土地分割

配 点 : ５０

問 題
ハウジングメーカーで順調に業績をあげている山田ハウスが、新たな目玉商品として、学校や病院など環境が充実している緑ホームタウンの分譲地を売り出しました。この分譲地は複数の区画に分割されており、好きなだけ購入できますが、購入する区画を合わせた土地の形状は長方形（正方形を含む）でなければなりません。
山田ハウスは、全区画が完売した分譲地を管理するため購入者ごとに境界線を引き、その区画の 1つに購入者番号を書いた看板を設置しておきました。境界線は地面に木の枝で線を引いただけのものであったため、数日後の豪雨により消えてしまい看板だけが残りました。図 1 は看板のあった区画に、その区画を買った購入者番号を記したものです。これでは分譲地がどのように買われたか分かりません。救いは事務所の引き出しにあった購入者番号 b と購入区画数 k のメモ（図 2）が見つかったことです。

図１

看板の配置

図２ メモ

プログラマーであるあなたは、プログラムを書いて山田ハウスを助けることになりました。分譲地の大きさ X × Y 、購入者数 n 、メモの情報 b , k 、及び看板の位置情報 s を入力とし、図 3 に示すように各区画の購入者を出力するプログラムを作成してください。

図３

各区画の購入者与えられた情報について、以下の場合は NA と出力します。
● 区画を区別する方法が存在しない場合●

区画を区別する方法が複数存在する場合

X 、 Y 、は 1 以上 10 以下、 n は 1 以上 100 以下の整数とします。 b は 1 以上 n 以下、 k は1 以上の整数とします。看板の位置情報 s は、各区画について看板が無い区画は 0 、看板がある区
画はその区画の購入者番号 b が入力されます。

パソコン甲子園２００９本選問題 問題番号０９【１／３ページ】

入 力
複数のデータセットの並びが入力として与えられます。入力の終わりはゼロみっつの行で示されます。各データセットは以下のとおりです。
1 行目 X Y n (整数 整数 整数；半角空白区切り)
2 行目 メモ情報の 1 行目 b k（整数 整数；半角空白区切り）
3 行目 メモ情報の 2 行目
：n+1 行目 メモ情報の n 行目
n+2 行目 区画情報の１行目 s1 s2 ･･････ sX（すべて半角数字；半角空白区切り）
si は区画（1, i ）の看板情報
n+3 行目 区画情報の 2 行目：
n+Y+1 行目 区画情報の Y 行目

出 力
入力データセットごとに、購入者情報を出力します。

パソコン甲子園２００９本選問題 問題番号０９【２／３ページ】

出力例

入力例
5 4 61 62 43 34 45 1
6 20 0 1 0 0
0 0 0 2 00 0 0 3 00 4 5 0 6
3 3 1
1 90 0 1

1 1 1 2 2
1 1 1 2 24 4 3 3 34 4 5 6 6
1 1 1
1 1 1
1 1 1
NA0 0 00 0 0
4 4 4
1 62 23 44 4
0 1 0 00 0 0 20 0 3 0
0 4 0 00 0 0

パソコン甲子園２００９本選問題 問題番号０９【３／３ページ】

▶ 問題番号【１０】秋のイルミネーション

配 点 : ７５

問 題
四角形が大好きな人が多く住む四角町では、四角形の電光板を組み合わせたイルミネーションで町中を彩るお祭りが開催されます。このイルミネーションには四角大学で開発された特殊な電光板を使います。この電光板は電気を流すと発光し、発光している板に接している板も発光します。したがって、電光板を何枚使っても、すべてがひとかたまりに接していれば電源がひとつで済むという優れものです。お祭り実行委員会では、四角形を組み合わせたデザインを町民から募集し多数のイルミネーションを作成します。各イルミネーションは、デザインを構成する四角形の配置によって必要となる電源の個数が変わるため、必要な電源の個数を把握する作業に毎年大きな手間がかかっています。今年は例年より多くのデザインが集まったため、お祭りまでに準備が間に合わない恐れが出てきました。
そこで、お祭り好きなあなたは四角形の配置を調べ、必要な電源の個数を計算するプログラムを作成して実行委員会を手助けすることにしました。

イルミネーションの個数 N 、各イルミネーションを構成する四角形の情報を入力とし、イルミネーションごとに必要な電源の個数を出力するプログラムを作成してください。イルミネーションを構成する四角形の情報は四角形の数 M 、各四角形の頂点座標(xa, ya), (xb, yb), (xc, yc), (xd, yd)で与えられます。ただし、N は 1 以上 100 以下の整数、M は 1 以上 100 以下の整数とします。各四角形の頂点座標はそれぞれ -1000 以上 1000 以下の整数とします。出力する電源の個数は各イルミネーションが入力された順番に従ってください。
重なっていたり接していたりする四角形を 1 つのまとまりと考え、1 つのまとまりに対して電源の個数は 1 つと数えてください。また、入力される四角形の頂点座標は、時計回りの順に従って入力されます。ただし、入力データの四角形はすべて凸な四角形とします（凸な四角形とは、内角がすべて180°未満である四角形のことを指します）。

パソコン甲子園２００９本選問題 問題番号１０【１／３ページ】

入 力
複数のデータセットの並びが入力として与えられます。入力の終わりはゼロひとつの行で示されます。各データセットは以下のとおりです。
1 行目 イルミネーションの個数 N（整数）
2 行目 第 1 のイルミネーションを構成する四角形の個数 M1（整数）
3 行目 第 1 のイルミネーションを構成する 1 個目の四角形の頂点
xa ya xb yb xc yc xd yd（すべて整数；半角空白区切り）
4 行目 第 1 のイルミネーションを構成する 2 個目の四角形の頂点：
M1+2 行目 第 1 のイルミネーションを構成する M1 個目の四角形の頂点
M1+3 行目 第 2 のイルミネーションを構成する四角形の個数：

出 力
入力データセットごとに、イルミネーションごとに必要な電源の個数を出力します。

パソコン甲子園２００９本選問題 問題番号１０【２／３ページ】

出力例入力例
310 0 0 1 1 1 1 0
20 0 0 1 1 1 1 0
100 100 100 200 200 200 200 100
20 0 0 100 100 100 100 010 10 10 20 20 20 20 102130 40 40 50 40 20 20 10
130 40 40 50 40 20 20 10121110

パソコン甲子園２００９本選問題 問題番号１０【３／３ページ】

▶ 問題番号【１１】パチモンクリーチャー

配 点 : ７５

問 題
某国で爆発的大人気のゲーム、パチモンクリーチャーが日本でリメイクされて発売されました。
ゲームが大好きなあなたは、このゲームを今まで貯めたお小遣いで購入し、何度もプレイしました。
そして、何度もプレイするうちにどうしたら最速でクリアできるのか考えるようになりました。しかし、いくら考えても最速の攻略方法がわからなかったあなたは、どれだけ早くゲームクリアできるかを求めるプログラムを作成することにしました。
ゲームの詳細は以下の通りです。
パチモンクリーチャー（以下、パチクリ）という生物が多く存在する世界がゲームの舞台です。各パチクリは、火属性、氷属性、木属性、土属性、水属性の 5 種類の属性のいずれか一属性を持ちます。
ゲームの主人公である E 君は、近所に住んでいる親切なおじさんから好きな属性のパチクリ一匹を冒険のパートナーとして受け取ります。そのパチクリと共にゴールを目指し、ゴールにいるライバルを倒してパチクリマスターになることが主人公の夢であり、ゲームクリアでもあります。
しかし、ライバルを倒すためには全属性のパチクリがいないと勝てないので、途中で全属性のパチクリを捕まえなければなりません。パチクリを捕まえるには属性がカギとなります。火属性のパチクリは氷属性のパチクリを捕まえることができ、同様に、氷属性は木属性、木属性は土属性、土属性は水属性、水属性は火属性を捕まえることができます。属性の関連は以下の図のようになります。

→次ページへつづきます

パソコン甲子園２００９本選問題 問題番号１１【１／４ページ】

以下の図はゲームが行われるマップの一例を表しています。

主人公はパチクリを一つもってスタート地点である「S」から出発し、一マスずつ移動しながらゴール地点である「G」を目指します。その途中で、最初に持っているパチクリ以外の 4 つの属性のパチクリを捕まえ、ゴール地点であるマス目に移動するとゲーム終了となります。主人公は、今いるマス目から、辺を共有する隣のマス目に移動することができ、それを一回の移動と数えます。主人公がパチクリのいるマスに移動した場合、そのパチクリを捕まえられる属性のパチクリを持っていればそのパチクリを捕まえたことになります。そのマスにいるパチクリを捕まえられるかの可否にかかわらず、すべてのマスに何度でも移動することができます。
マップの大きさ x、y （横方向の列数、縦方向の行数）とマップの初期状態 t を入力とし、初めに選んだパチクリの属性と、それ以外の 4 つの属性のパチクリを捕まえるのにかかる、スタート地点からゴール地点に至る最小移動数を出力するプログラムを作成してください。なお、どのように初めのパチクリを選んでも、どのような経路で移動してもそれら 4 つの属性のパチクリを捕まえることができない場合は NA と出力してください。また、最小移動数が同じになるような最初のパチクリの選び方が複数ある場合は、属性の数字が小さいものを出力してください。マップの大きさ x, y はそれぞれ 2以上 1000 以下の整数、各属性のパチクリの数はそれぞれ 0 以上 1000 以下の整数とします。 また、入力されるマップには各マスの状態が与えられます。「S」は主人公のスタート地点を、「G」はゴール地点を、「1」、「2」、「3」、「4」、「5」はそこにいるパチクリの属性を、「.（ピリオド）」は何もないマスをそれぞれ表します。
（ 1：火属性、 2：氷属性、3：木属性、 4：土属性、 5：水属性 をそれぞれ表します。
）

パソコン甲子園２００９本選問題 問題番号１１【２／４ページ】

入 力
複数のデータセットの並びが入力として与えられます。入力の終りはゼロふたつの行で示されます。
各データセットは以下のとおりです。
1 行目 マップの大きさ x y （整数 整数；半角空白区切り）
2 行目 マップの 1 行目の情報
3 行目 マップの 2 行目の情報：

t1t2t3…tx （半角英数文字列）

y+1 行目 マップの y 行目の情報

出 力
入力データセットごとに、最初に選んだパチクリの属性と最小移動数を出力します。

パソコン甲子園２００９本選問題 問題番号１１【３／４ページ】

出力例

入力例
6 6
S.1..43..5..
..4.1.
4....5.2.32.
5.1..G
3 2...
S.G
0 0

パソコン甲子園２００９本選問題 問題番号１１2 10NA

【４／４ページ】