問題０１ お化け屋敷 （ ６点）

会津学園高等学校では、毎年学園祭をおこなっています。その中でも一番人気はお化け屋敷です。一番人気の理由は、お化け屋敷をおこなうクラスが 1クラスや 2クラスではなく、9クラスがお化け屋敷をおこなうことです。それぞれが工夫することより、それぞれが個性的なお化け屋敷になっています。そのため、最近では近隣から多くの来場者があり、様々なお化け屋敷をはしごすることがブームになっています。
そこで、学園祭実行委員会では、お化け屋敷の入場料金を下表のように校内で統一し、これにもとづき各クラスごとに入場者総数と収入の集計をおこなうことにしました。各クラス毎の午前と午後の入場者数を入力とし、各クラス毎の入場者総数及び収入の一覧表を作成するプログラムを作成してください。ただし、クラス名は数字とアルファベットを含む1文字以上 15文字以下の半角文字列です。また、入場者数は各時間帯とも安全面を考慮して400人を上限とします。
入場料金表（入場者 1人あたりの入場料）
午前

午後200円

300円入力
1行目
2行目
：
9行目

第1のクラス名 午前の入場者数 午後の入場者数(半角文字列 整数 整数；半角空白区切り)
第2のクラス名 午前の入場者数 午後の入場者数(半角文字列 整数 整数；半角空白区切り)
第9のクラス名 午前の入場者数 午後の入場者数(半角文字列 整数 整数；半角空白区切り)

出力
1行目
2行目
：
9行目

第1のクラス名 入場者総数 料金収入
(半角文字列 整数 整数；半角空白区切り)
第2のクラス名 入場者総数 料金収入
(半角文字列 整数 整数；半角空白区切り)
第9のクラス名 入場者総数 料金収入
(半角文字列 整数 整数；半角空白区切り)

入力例

出力例

1a 132 243
1c 324 183
1f 93 199
2b 372 163
2c 229 293
2e 391 206
3a 118 168
3b 263 293
3d 281 102

1a 375 99300
1c 507 119700
1f 292 78300
2b 535 123300
2c 522 133700
2e 597 140000
3a 286 74000
3b 556 140500
3d 383 86800
パソコン甲子園２００８予選問題

問題０２ バドミントン （ ６点）

Ａ君、Ｂさん、Ｃ君で久しぶりに遊ぶことになりました。
Ａ君とＢさんがプレイヤー、Ｃ君が審判になりバドミントンのシングルスのゲームをしました。3人で決めたルールは以下の通りです。
3ゲームを行います。
z 11点を先取した人が、そのゲームの勝者となります。
z 第1ゲームの最初のサーブはＡ君から始まりますが、次のサーブは直前のポイントを取った人が行います。
z 第2ゲーム、第3ゲームは前のゲームを取った人が最初のサーブを行います。
z 10－10 になって以降は 2 点差をつけた人が勝者となります。
z全てのゲームが終わり、得点を見ようとしたのですが、審判のＣ君が得点を記録するのを忘れていました。しかし、サーブを打った人をきちんと記録していました。サーブ順の記録から得点を計算するプログラムを作成してください。ただし、二人が打ったサーブの回数の合計は100以下とし、サーブ順の記録は、サーブを打った人を表す "A" または "B" の文字の配列で表されます。

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

第1ゲームのサーブ順（半角文字列）
第2ゲームのサーブ順（半角文字列）
第3ゲームのサーブ順（半角文字列）

出力
入力データセット毎に各ゲーム毎のＡ君の得点とＢさんの得点を以下のとおり出力します。
1行目
2行目
3行目

第1ゲームのＡ君の得点 第1ゲームのＢさんの得点（整数 整数；半角空白区切り）
第2ゲームのＡ君の得点 第2ゲームのＢさんの得点（整数 整数；半角空白区切り）
第3ゲームのＡ君の得点 第3ゲームのＢさんの得点（整数 整数；半角空白区切り）

入力例

出力例

ABAABBBAABABAAABBAAAABBBABBABBAAABABABAABBABAABAABABABBAAABAABABAAABBAABBBABAAAAAAAAAAAAAABBBBBBBBBB
011 8
10 12
11 7
11 8
11 00 11

パソコン甲子園２００８予選問題

問題０３ ハワイ好きの王様 （ ６点）

この夏、王様は初めてハワイに行き、たいへん気に入りました。
あまりに気に入ってしまったため、着るものをすべてアロハシャツにしたり、踊り子に無理矢理フラダンスを踊らせたりして周りの人は苦笑い。そんな王様の耳に「昔ハワイでは魚やタロイモを指にはさんで数えていたので、10進数ではなく4進数を使っていた」という情報が入りました。記数法なんて言葉を聞いたこともなかった王様でしたが、いてもたってもいられなくなり大臣に身の回りの数字を全て4進数にするように命じました。大臣も記数法という言葉を聞いたことがありませんでしたが、勉強してみた結果、以下のようなことがわかりました。
大臣の勉強ノート
10進数・現在使われている一般的な記数法。
・0、1、2、3、4、5、6、7、8、9 の 10個の記号を用いて全ての数字を表す。
z 2進数
・コンピュータの世界でよく使われる記数法。
・0 と 1 の二つの記号を用いて全ての数字を表す。
z 4進数
・4進数で用いられるのは 0、1、2、3 の 4つの数字だけ。
・4進数では 0 から順に数を増やしていったときに 4 まで来たら次の位に桁上がりします。
そのため、10進数の4は桁上がりして「10」という表現になります。
z10進数01234562進数

01

1011100

101

4進数

0123

101178910 ...

110111 1000 1001

1010 ...

1213202122 ...

以上の大臣の勉強成果をもとに、10進数で入力される数字nを4進数に変換し出力するプログラムを作成してください。ただし、入力される数字は 0 以上 1000000 以下の整数とします。

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

n（整数）

出力
入力データセット毎に4進数に変換した結果を出力します。

入力例

出力例

740121010000-11310030222130100

パソコン甲子園２００８予選問題

問題０４ どんな色？ （ ６点）

ウェブデザイナーを目指す太郎君はただいま修行中。事務所の先輩から「このページの背景色は#ffe085で」と、ウェブデザイン特有の色番号で指示されるのですが、それがどんな色かパッと思い浮かべることができません。
この色番号は光の三原色である赤、緑、青それぞれの強さを表わしています。具体的には 2桁の16進数を 3つ組み合わせたもので、色番号を“#RGB”とするとき、R は赤の強さ、G は緑の強さ、Bは青の強さを表します。それぞれ00からffまでの値になります。
色番号にまだ不慣れな太郎君のために、色番号を入力とし、色の表の中からもっとも近い色の名前を出力するプログラムを作成してください。使用する色の表は以下の通りです。
＼ 色の名前 赤の強さ 緑の強さ 青の強さ
black00

00

00

blue0000

ff

lime00ff00

aqua00

ff

ffred

ff00

00

fuchsia

ff00

ffyellow

ff

ff00

white

ff

ff

ff

「もっとも近い色」とは、以下のように定義します。与えられた色番号での赤、緑、青の強さをそれぞれ R、G、B とし、表の k 番目の色の赤、緑、青の強さをそれぞれ Rk、Gk、Bkとするとき、次の式で計算する dk の値が最も小さい色がもっとも近い色とします。

なお、dkの値が同じになる色が複数存在する場合は表の中でより上にある色がもっとも近い色になります。

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

色番号 #RGB（半角文字列）

出力
入力データセット毎に最も近い色の名前を出力します。

入力例

出力例

#ffe085#787878#decade#ff55ff0

whiteblackwhitefuchsia

パソコン甲子園２００８予選問題

問題０５ 都市間の距離 （ ８点）

地球上の 2都市の北緯と東経を入力とし、地表距離を計算して出力するプログラムを作成してください。ただし、地球は半径6,378.1km の球とし、2点間の地表距離とはこの球面に沿った最短距離です。また、南半球でも南緯は用いずに北緯 0～-90 度を用い、グリニッジ子午線の西でも西経は用いずに東経 180～360度を用いることとします。地表距離は km単位で求め、小数点以下は四捨五入し、整数値として出力してください。
以下に主要都市の北緯、東経の例を示します。
地名

北緯（度） 東経（度）

東京

35.68

139.77

シンガポール

1.37

103.92シドニー-33.95151.18シカゴ

41.78

272.25

ブエノスアイレス-34.58301.52

ロンドン

51.15

359.82

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

a b c d（実数 実数 実数 実数；半角空白区切り）
各記号の意味は以下のとおりです。
a：第1の都市の北緯b：第1の都市の東経
c：第2の都市の北緯d：第2の都市の東経

出力
入力データセット毎に2都市の地表距離を出力します。

入力例

出力例

35.68 139.77 51.15 359.82
1.37 103.92 41.78 272.25
51.15 359.82 -34.58 301.52-1 -1 -1 -1

9609
15092
11112

パソコン甲子園２００８予選問題

問題０６ テトリス （ ８点）

テトリスは、落ちてくるブロックを盤面上に並べて消すゲームです。ここでは、それを少しアレンジしたゲー
ムを考えましょう。
本問題のテトリスは盤面の大きさは横5コマで、出現するブロックがすべて入るだけの高さがあります。落ちてくるブロックは直線状で、横向き、縦向きの2種類があり、長さは 1 から 5 までの 5種類です。
以下に例を示します。Step(イ) からStep(ホ)までの図はブロックが落ちて消えていく様子を表したものです。
Step(イ)から順にStep(ロ)、Step(ハ)と順に進んでいきます。
ブロックを落とすときに、Step(イ)のようにブロックのどこかが下に積んであるブロックに引っかかったときには、Step(ロ)のように落ちたブロックはその場所で止まります。また、ブロックを落とした結果、盤面の横一行の全てのコマにブロックが詰まった場合には、Step(ニ)で示されるように、その行のブロックが消えます。この後、消えた行の上にあるブロックが、そのままの形で1行下にしずみます（Step(ホ)）。

1ゲームは1000個以内のブロックが順に落ちてくることとします。例えば、落ちるブロックの長さが順番に横向
き 4コマ, 横向き 3コマ, 縦向き 2コマ, 縦向き 3コマで、落ちる場所が左端から 1コマ目、1コマ目、4コマ目、5コマ目であった場合には、下図のStep(イ)～(ト)のように落ち、最後に残るブロックは 2コマになります。

順番に落ちてくるブロックの情報を入力とし、全てのブロックが落ちた時に残るコマ数を出力するプログラムを作成してください。ただし、ブロックの数 n は 1 から 1000 までの整数とします。ブロックの向き d は整数で、1 は横向きを、2 は縦向きを表します。長さ p は 1 から 5 までの整数とします。ブロックの位置 q は盤面上の左端から 1～5 までの整数とし、横向きのブロックの場合は左端のコマの落ちる位置とします。

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

3行目
：
n+1行目

ブロックの数 n（整数）第1のブロックの情報 d p q（整数 整数 整数；半角空白区切り）
各記号の意味は以下のとおりです。
d：ブロックの向き
p：ブロックの長さ
q：ブロックの位置
第2のブロックの情報
第nのブロックの情報

出力
入力データセット毎に最後に残るブロックの占めるコマ数を出力します。

入力例

出力例

41 4 11 3 1
2 2 42 3 51
1 5 1
72 2 2
1 4 1
2 1 3
1 4 1
1 1 1
2 5 5
1 4 20206

パソコン甲子園２００８予選問題

問題０７ ふしぎな虫 （２０点） ※この問題はカラーで見てください

会津生物学研究所のＡ博士は、とある南の島でふしぎな虫を発見しました。形は芋虫のように細長いのですが、ひとつの体節が玉のような形をしているので、糸でつないだビーズ玉のように見えます。ふしぎなのは体の色に様々なバリエーションがあることと、なかには時間がたつにつれて体の色が変っていく虫がいることでした。どの虫の体節の色も赤か緑か青のどれかに限られるようですが、1秒ごとに体節の色が変わっていき、最後にはすべての体節が同じ色になって落ち着く場合もあれば、いつまで待ってもずっと色が変わりつづける場合もあるようでした。
調べていくうちに、ふだんはすべての体節が同じ色をしているのですが、何かに驚いたりして興奮した後は体節の色が勝手に変わってしまうことがわかりました。一度体節の色が変わってしまうと、ふたたびすべての体節が同じ色になるまではずっと色が変わり続けることがわかりました。
Ａ博士はこの虫を何匹も捕まえて興奮させてみては、色が変わる様子を興味深く観察していましたが、やがて色が変化している最中の色の変わり方には次のような規則性があることに気がつきました。
色が変わるのは、隣り合っている色違いの 2つの体節のペア 1組だけが変わり、他の体節の色は変わらない。ただし、そのようなペアが複数あるときに、どのペアの色が変わるかはあらかじめ予測できない。
z そのようなペアは、2つの体節の色のどちらでもない色に同時に変わる(たとえば、緑と赤の体節が隣り合っているときは、それらが同時に青に変わる)。
z

虫の色の変化を、2秒後まですべて書いたものが上の図です。図の上段のような色をした虫がいるとします。このとき、隣り合った色違いの体節のペアは 3組あるので、1秒後には中段に並べて描いた 3通りの色のどれかに変わります。1秒後に中段左側の 2つのように変わったときには、2秒後にすべての体節が緑色になることができます(図の下段の左側から 2番目)。 それに対して、1秒後に中段の1番右のように変わったときには、2秒後にすべての体節が同じ色に変わることはありません。
博士はコンピュータを持っていなかったので、目の前にいる虫の体節がすべて同じ色になる可能性があるのか、あるとしたらそうなるのは最短で何秒後なのかを予測することはできませんでした。
博士の代りに、それを予測するプログラムを書いてください。目の前にいる虫の体節の色の並びを入力とし、その虫の体節がすべて同じ色になるのに要する最短の時間を秒単位で出力するプログラムを作成してください。ただし、同じ色になる可能性がないときは「NA(半角英大文字)」と出力してください。また、虫の体節の色の並びは 2以上 10以下のr(赤)、g(緑)、b(青)からなる文字列で表されます。

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

虫の体節の情報（半角文字列）

出力
入力データセット毎に以下の形式で出力します。
1行目 すべての体節の色が同じになるまでに要する最小時間(秒単位の整数)またはNA

入力例

出力例

rbgrg
rbbgbbrbgr
bgrbrgbr
bggrgbgrr
gbrggrbggr
rrrrr
bgbr
057
16
NA
804

パソコン甲子園２００８予選問題

問題０８ デブンキー一家の大活躍 （２０点）

水の国ウォーターデブンには n 個の都市があります。各都市は水に囲まれており、島国のようになっています。ウォーターデブンには全部で m 本の橋があり、都市間の交通はそれらの橋によって行われ、全ての都市に行き来することができます。最近、道路特定財源の見直しにより橋の維持費の削減が決定されました。全部の橋を維持することができなくなってしまい、いくつかの橋を取り壊すことになりました。そこで、ウォーターデブンはどの都市にでも行くことができるように橋を残しつつ、橋の維持費を最小化することが課題となりました。

都市の数、橋の数、各橋の維持費を入力とし、橋を利用してどの都市にも行けるようにしつつ、橋を取り壊した場合の維持費の最小値を出力するプログラムを作成してください。なお、橋の取り壊しはウォーターデブンの優秀な解体屋（デブンキー一家）により容易に行われ、取り壊しには費用が掛からないものとします。ただし、各都市は 1 から n まで順番に番号が付けられているものとし、さらに、都市の数は 2以上 100以下、橋の維持費は 1以上 100以下とします。

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

都市の数n 橋の数m（整数 整数；半角空白区切り）
第1の橋の情報 a b cost（整数 整数 整数；半角空白区切り）
各記号の意味は以下のようになります。
a b：橋がつないでいる都市の番号
cost：橋にかかる維持費
3行目 第2の橋の情報
4行目 第3の橋の情報：
m+1行目 第mの橋の情報

出力
入力データセット毎に橋の維持費の合計を出力します。

入力例

出力例

5 61 3 13 2 33 4 82 4 24 5 52 5 43 32 3 3
3 1 3
1 2 30 0106

パソコン甲子園２００８予選問題

問題０９ こだわり （２０点）

人には様々なこだわりがあります。例えば、本に関することでも「本は読むと汚れるのでカバーを外して読む様にし、カバーはクリアファイルなどにとっておく」や「本は 1巻から並んでいないと気が済まない」など様々はこだわりがあります。
太郎君もその一人で、本はきちんと 1巻から順に並んでいないと気が済まないようです。そんな太郎君はとある小説にはまっています。その小説は全部で n 巻あり、各巻で本の厚さが異なります。太郎君はこの小説が大変気に入ったので、その小説専用の本棚を買おうと思っています。しかし、部屋に大きな本棚を置くとかなり狭くなってしまうので、出来るだけ本棚の幅が小さくなるように工夫しなければなりません。床から天井の高さを測ったところ、どうやら m 段の本棚なら置けることが分かりました。そこで、小説 ｎ 巻をどのように分ければ m 段の本棚の幅を最小に出来るでしょうか？もちろん、各段に納める小説は巻の番号順に並んでいなければなりません。
本棚の段数、小説の巻数、各本の厚さを入力として、全巻を 1巻から順に収めることができる本棚の中で幅が最小となるものの幅を求めるプログラムを作成してください。ただし、本棚の幅は 100000 を超えないものとします。本
棚の段数 m は 1以上 20以下、本の巻数は 1以上 100以下とし、一冊の本の厚さは 1以上 10000以下とします。また、本棚の枠の大きさは幅に含めないこととします。

入力
複数のデータセットの並びが入力として与えられます。入力の終わりはゼロふたつの行で示されます。各データセッ
トは以下のとおりです。
1行目 部屋に置くことができる本棚の段数 m 小説の巻数 n（整数 整数；半角空白区切り）
2行目 第1巻の本の厚さ（整数）
3行目 第2巻の本の厚さ（整数）：
n+1行目 第n巻の本の厚さ（整数）

出力
入力データセット毎に最小となる本棚の幅を出力します。

入力例

出力例

3 9500300800200100600900700400
4 3100010001000
0 018001000

パソコン甲子園２００８予選問題

問題１０ ビーカー （２０点）

いろいろな容量のビーカーが与えられています。はじめに、その中の一番容量の大きなビーカーを一個選び、蛇口から水をいっぱいになるまで注ぎます。つぎに、次のルールにしたがいながら、ビーカーの水を他のビーカーに移し替えていきます。
ビーカーに入っている水は，残さずにすべて他のビーカーに移さなければならない。ただし、一個のビーカーに水を全部移せないときは、複数のビーカーに分けて移してもよい。
z ビーカーに水を入れるとき、いっぱいになるまで水を注がなければならない。また、水をこぼしてはならない。
z 複数のビーカーから同じビーカーに一度に水を注いではならない。
z 同じビーカーには一度しか水を注いではならない。
z

このルールにしたがったとき、ビーカーの個数 n と各ビーカーの容量を入力とし、すべてのビーカーに水を注ぐことができるかどうかを判定して出力するプログラムを作成してください。すべてのビーカーに水を注ぐことができるときは YES (半角英大文字)、できないときは NO (半角英大文字) を出力してください。ただし、ビーカーの個数 n は 1 以上 50 以下の整数とし、ビーカーの容量は 1以上 100 以下の整数で表すこととします。

入力
複数のデータセットの並びが入力として与えられます。入力の終わりはゼロひとつの行で示されます。各データセットは以下のとおりです。
1 行目 ビーカーの個数 n (整数)
2 行目 第1のビーカーの容量 ･･･

第 n のビーカーの容量 (整数 整数 ･･･ ; 半角空白区切り)

出力
入力データセット毎に判定結果を出力します。

入力例

出力例

1011 2 23 4 2 12 8 5 2 108
2 1 3 11 2 3 1 495 9 1 2 4 8 17 1 88
3 38 9 4 18 14 19 5110YESYESYESNOYES

パソコン甲子園２００８予選問題