全国高等学校パソコンコンクールプログラミング部門 予選問題
平成２４年 ９月 ８日(土)午後１時３０分～午後４時３０分

全国高等学校パソコンコンクール実行委員会

問題 1

10 問解いたら何点取れる？

（4 点）

選手の皆さん、パソコン甲子園にようこそ。パソコン甲子園は今年で 10 周年になりますが、出題される問題数や合計得点は年によって異なります。各問題には難易度に応じて得点が決められています。問
題数が 10 問で、それぞれの問題の得点が与えられるとき、それらの合計を出力するプログラムを作成して下さい。

入力
入力は以下の形式で与えられる。
s1
s2.
.
s 10
入力は10行からなり、i行目に問題iの得点を表す整数s i (0≦s i ≦100)が与えられる。

出力
合計得点を１行に出力する。

入出力例
入力例 112345678910出力例 155

入力例 2448881010121620出力例 2100

問題 2乗車券（4 点）

新幹線に乗るためには、「乗車券」「特急券」の2枚の切符が必要です。経路の一部で新幹線を利用しない場合があるため、これらは別々の切符となっていますが、新幹線のみを利用する経路では、1枚で乗車券と特急券を兼ねる「乗車・特急券」が発行されることもあります。
自動改札機では、これらの切符を読み込んで、正しい切符が投入されたときだけゲートを開けなければなりません。「乗車券」と「特急券」それぞれ１枚、または、その両方、または、「乗車・特急券」が１枚投入されたかどうかを判定し、自動改札機の扉の開閉を判断するプログラムを作成して下さい。

入力
入力は以下の形式で与えられる。
b1 b2 b3
入力は１行からなり、１つの空白で区切られた３つの整数を含む。b 1 は「乗車券」の投入状態、b 2 は「特急券」の投入状態、b 3 は「乗車・特急券」の投入状態を示す。投入状態は0または1で表され、0の場合は投入されていない状態、1の場合は投入されている状態を表す。ただし、想定される投入状態の組み合わせは以下の場合のみとする。
入力

投入状態

投入に対する扉の動作

100「乗車券」のみ投入

Close

010

「特急券」のみ投入

Close

110

「乗車券」と「特急券」投入

Open

001

「乗車・特急券」投入

Open000

投入なし

Close

出力
自動改札機の開閉を表す Open または Close を１行に出力する。

入出力例
入力例 10 0 1

出力例 1Open

入力例 20 1 0

出力例 2
Close

問題 3

家庭菜園

（8 点）

家庭菜園に野菜を植えることにしました。n粒の種があったので1日に1粒ずつ、n日かけてn粒の種をまきました。どの種からも芽が出て、すくすくと育っています。収穫の時期が待ち遠しいものです。
ある日、いつものように苗に水やりをしていると、おかしなことに気づきました。n本の野菜の苗があるはずなのに、1本多いのです。雑草が生えてきてしまいました。直ちに引っこ抜きたいのですが、困ったことにどの苗もよく似ていて、野菜と雑草の見分けがつきません。
手がかりになるのは、野菜の成長速度です。この野菜は、種をまいてからずっと、1日に決まった長さだけ伸び続けるのです。しかし、この「決まった長さ」というのが何センチメートルなのかはわかりません。また、最初の種を何日前にまいたのかも忘れてしまいました。苗は一列に並んでいますが、唯一覚えているのは、種をまくとき毎日一粒ずつ右から順にまいていったことだけです。
n＋１本の苗の長さを入力し、雑草の長さを出力するプログラムを作成して下さい。

入力
入力は複数のデータセットからなる。入力の終わりはゼロ１つの行で示される。各データセットは以下の形式で与えられる。
nh1 h2 h3 ... hn+1
１行目のn(4≦n≦100)は野菜の苗の数を表す整数である。２行目は１つの空白で区切られたn+1個の整数を含み、hi(1≦hi≦109)は左からi番目の苗の長さを示す。
データセットの数は500を超えない。

出力
各データセットごとに雑草の長さを１行に出力する。

入出力例
入力例
51 2 3 6 4 56
1 3 6 9 12 15 184
5 7 9 11 120

出力例
6112※ 「パソコン甲子園２０１２予選プログラミング部門解説」の“問３ 家庭菜園 お知らせ”にて、上記の問題文を補足する情報を掲載していますので、あわせてご確認ください。

問題 4

すべての数は６１７４に通ず（8 点）

0 から 9 の数字からなる四桁の数 N に対して以下の操作を行う。
1. N の桁それぞれの数値を大きい順に並べた結果得た数を L とする
2. N の桁それぞれの数値を小さい順に並べた結果得た数を S とする
3. 差 L-S を新しい N とする(1 回分の操作終了)
4. 新しい N に対して 1.から繰り返す
このとき、全桁が同じ数字(0000,1111 など)である場合を除き、あらゆる四桁の数はいつかは 6174 になることが知られている。例えば N = 2012 の場合
1 回目 (N=2012): L = 2210, S = 0122, L-S = 2088
2 回目 (N=2088): L = 8820, S = 0288, L-S = 8532
3 回目 (N=8532): L = 8532, S = 2358, L-S = 6174となり、3 回の操作で 6174 に到達する。
0 から 9 の数字からなる四桁の数が与えられたとき、何回の操作で 6174 に到達するか計算するプログラ
ムを作成して下さい。

入力
入力は複数のデータセットからなる。入力の終わりは 0000 が１つの行で示される。各データセットは以下の形式で与えられる。
N
データセットは１行であり、N(1≦N≦9999)は四桁の数を示す。N < 1000の場合は上の桁は0で埋められている。
データセットの数は10000を超えない。

出力
各データセットごとに何回の操作で 6174 に到達したかを１行に出力する。ただし全桁が同じ数字である数が入力として与えられた場合は NA と出力する。

入出力例
入力例
6174
201233330000

出力例
03NA問題 5

パイプつなぎ職人の給料（8 点）

ぼくはパイプつなぎ職人です。パイプをつなぐジョイントとパイプさえもらえれば、どんなパイプだってつないでみせます。ぼくは毎日、親方からパイプとジョイントを渡されて、それをつないで親方に渡します。でも、パイプの数が多すぎるときは、１日でそれを全部つなげることはできません。そんなときでも親方はにっこり笑って、ぼくに給料を渡してくれます。
ところで、あるとき変なことに気がつきました。全部のパイプをつなげられたときより、つなげられなかったときの方が給料が多いことがしょっちゅうあるんです。あんまり変なので、ある日、親方が来たときに、給料の計算方法が書いてあるメモをこっそり見ちゃいました。そしたら、なんと給料は「パイプの本数×パイプの長さの総和」で支払う。
ただし、ジョイントでつなげて、ひとつながりになったものは、それを１本のパイプとみなす。って書いてありました。これで全部つなげた方が給料が安くなることがある理由がわかりました。たとえば下図のように、長さ 1 のパイプ 3 本と長さ 2 のジョイント 2 本を全部つなげると長さ 1+2+1+2+1=7のパイプが 1 本できるので、1×(7)=7 です。でも、ジョイントを一つだけ使って長さ 1+2+1=4 のパイ
プと長さ 1 のパイプの 2 本にすると 2×(4+1)=10 なので、全部つなげるよりいっぱい給料がもらえます。
作業前
パイプ

ジョイント

長さ１
長さ２

作業後
＝給料

７

長さ７＝給料 １０
長さ４

長さ１

親方がなんでこんな方法で給料を決めてるかわからないけど、これでぼくもどうすればもらえる給料を多くできるかわかりました！
それでは、パイプの本数が与えられたとき、もらえる給料の最大の金額を計算するプログラムを作成してください。

入力
入力は複数のデータセットからなる。入力の終わりはゼロ１つの行で示される。各データセットは以下の形式で与えられる。
np 1 ... p n
j 1 ... j n-1

１行目にパイプの本数n (2≦n≦65000)が与えられる。２行目は１つの空白で区切られたn個の整数からなる。p i (1≦p i ≦1000)はi番目のパイプの長さを示す。３行目は１つの空白で区切られたn-1 個の整数からなる。j i (1≦j i ≦1000)はi番目のジョイントの長さを示す。
i番目のジョイントは、i番目とi+1番目のパイプだけをつなげることができる。つなげたパイプの長さは、p i +j i +p i+1 になる。
データセットの数は100を超えない。

出力
各データセットごとに、得られる給料の最大の金額を 1 行に出力する。入力として与えられるデータセットでは、出力される値は必ず３２ビット符号無し整数の範囲に収まるものとする。

入出力例
入力例
31 1 1

出力例12483 37643 3 3 31 1 151 2 3 4 54 3 2 10

問題 6マヤの大予言（10 点）真也君はテレビで「マヤの大予言！2012 年で世界が終る？」という番組を見ました。結局、世界が終るかどうかはよくわかりませんでしたが、番組で紹介されていたマヤの「長期暦」という暦に興味を持ちました。その番組では以下のような説明をしていました。
マヤ長期暦は、右の表のような単位からなる、全部で 13 バクト
ゥン(187 万 2000 日)で構成される非常に長い暦である。ある計算法では、この暦は紀元前 3114 年 8 月 11 日に始まり 2012 年12 月 21 日に終わると考えられていて、このため今年の 12 月21 日で世界が終るという説が唱えられている。しかし、13 バク

トゥンで１サイクルとなり、今の暦が終わったら新しいサイクルに入るだけという考えもある。

１キン＝１日
１ウィナル＝２０キン
１トゥン＝１８ウィナル
１カトゥン＝２０トゥン
１バクトゥン＝２０カトゥン「ぼくの二十歳の誕生日はマヤ暦だと何日になるのかな？」真也君はいろいろな日をマヤ長期暦で表してみたくなりました。
では、真也君の代わりに、西暦とマヤ長期暦とを相互変換するプログラムを作成してください。

入力
入力は複数のデータセットからなる。入力の終わりは#１つの行で示される。各データセットは以下の形式で与えられる。
b.ka.t.w.ki

または
y.m.d

データセットは１つの文字列を含む１行からなる。b.ka.t.w.ki はマヤ長期暦の日付、y.m.d は西暦の日付である。与えられる単位は以下の通りである。
西暦

マヤ長期暦
bバクトゥン(0≦b＜13)y年(2012≦y≦10,000,000)

kaカトゥン(0≦ka＜20)m月(1≦m≦12)tトゥン(0≦t＜20)d日(1≦d≦31)w

ウィナル(0≦w＜18)kiキン(0≦ki＜20)

西暦の日の最大値は、大の月、小の月、うるう年かどうかで変わる(うるう年は 4 の倍数の年のうち、100 で割り切れない年か、400 で割り切れる年である)。マヤ長期暦の日付の範囲は 0.0.0.0.0 から12.19.19.17.19 までとする。ただし、マヤ長期暦の 0.0.0.0.0 は西暦の 2012.12.21 に対応する。また、西暦の日付の範囲は 2012.12.21 から 10000000.12.31 までとする。
データセットの数は 500 を超えない。

出力
入力が西暦のときはマヤ長期暦を、マヤ長期暦のときは西暦を、それぞれ入力と同じ形式で出力する。
入力された西暦を換算した結果、マヤ長期暦の次のサイクルに入った場合でも b.ka.t.w.ki の形式で出力してよい。

入出力例
入力例
2012.12.31

出力例
0.0.0.0.10

2.12.16.14.14
7138.5.13

3054.8.15
0.0.0.0.10

10.5.2.1.5

6056.2.29

10000000.12.31#8.19.3.13.2

問題 7

すごろくを作る（10 点）

太郎君は、子供会の催しでみんなで遊べるようにすごろくを作りました。ゲームをおもしろくするために、「ふりだし」と「あがり」以外のすごろくのマスのいくつかに「６つ進む」、「５つ戻る」のように指示を書き込んでいきました。ルーレットを回して出た数だけ進み、止まったマスに指示が書き込んであれば、その指示に従って移動します。ただし、指示に従って進んだ先のマスの指示には従いません。
ルーレットは１からある数までの間の数を等確率で出すことができるものとします。また、「あがり」に達するより大きな数が出たときや、指示に従うと「あがり」より先に進んでしまうときは「あがり」に移動します。指示に従って戻るときに「ふりだし」より前に戻ってしまうときは「ふりだし」に戻ることにします。
ところが、ルーレットとマスの指示によっては「あがり」にたどりつけない場合が出てきてしまいます。たとえば、図のようなすごろくを作ったとしましょう。１と２しか出ないルーレットを使うと、１，２の順に出れば「あがり」に行けますが、はじめに２が出たらその後は何が出ても永久に「あがり」にはたどり着けません。太郎君は、そうとは知らずに調子に乗ってあちこちのマスに指示を書き込んでしまいました。
そこで、太郎君に代わって、ルーレットとマスの指示によっては、「あがり」にたどり着けない場合が生じるかどうか判定するプログラムを作成してください。

入力
入力は複数のデータセットからなる。入力の終わりはゼロ１つの行で示される。各データセットは以下の形式で与えられる。
maxn
d1
d2.
.
.
dn

１行目にルーレットが出す数の最大値max(2≦max≦250)が与えられ、２行目に「ふりだし」と「あがり」以外のマスの数n(2≦n≦250)が与えられる。続くn行に各マスの指示を表す数d i (-n≦d i ≦n)が与えられる。d i がゼロのときは指示が書いていないことを、正の数のときは|d i |進む指示を、負の数のときは|d i |戻る指示を表す（ここで、|x|はxの絶対値を表す）。入力される値はすべて整数である。
データセットの数は 100 を超えない。

出力
各データセットごとに判定結果を１行に出力する。ルーレットとマスの指示によっては、「あがり」にたどり着けない場合が生じるときは「NG」、そうでなければ「OK」を出力する。

入出力例
入力例
33-2102420-1-222-2-20

出力例
OKNGNG

問題 8

ビートパネル（12 点）

遊太君は、近所のゲームセンターで人気のゲーム「ビートパネル」にはまっています。このゲームは図のようなグリッド状に並べられた 4×4 の計16 個のパネル型のボタンからなります。
図のように、左上から右下にボタン 1, ボタン 2, …, ボタン 16 の順にボタンが並んでいます。ゲームでは一定間隔でビート音が鳴り最後に終了音が鳴ります。ビート音が鳴ると同時に複数のボタンが光ります。１個も光らない場合もあります。プレイヤーは、ビート音が鳴った直後から次の音が鳴るまでの間に両手の指を使って複数のボタンを１度だけ同時に押すことができます。何も押さないということも可能です。終了音が鳴ったと同時にゲームは終了します。
遊太君は c 通りの押し方を習得しており、ビート音が鳴る度に、それらの押し方の中から１つ決めてボタンを押します。押したボタンが光っていれば、それらのボタンの光は消え、消えたボタンの数がプレイヤーのスコアに加算されます。また、一度光ったボタンはそのボタンが押されるまで光は消えることはありません。
ビート音が n 回鳴るときのボタンの光り方と遊太君が習得している c 通りのボタンの押し方を入力とし、遊太君が獲得することのできる得点の最大値を出力するプログラムを作成してください。

入力
入力は複数のデータセットからなる。入力の終わりはゼロ２つの行で示される。各データセットは以下の形式で与えられる。

n ca 1,1 a 1,2 … a 1,16a 2,1 a 2,2 … a 2,16…
a n,1 a n,2 … a n,16
b 1,1 b 1,2 … b 1,16b 2,1 b 2,2 … b 2,16…
b c,1 b c,2 … b c,16
１行目は１つの空白で区切られた２つの整数からなる。n (1≦n≦30) はビート音の数、c (1≦c≦30) は習得しているボタンの押し方の数を示す。続くn＋c行にボタンの光り方とボタンの押し方が与えられる。
行中の入力項目の区切りは１つの空白である。a k,i はk回目のビート音が鳴ったときのボタンiの光り方を、b j,i はc通り中j番目の押し方でボタンiが押されるかどうかを表す。a k,i の値は 0 が「光らない」、1が「光る」を表す。b j,i の値は 0 が「押さない」、1 が「押す」を表す。
データセットの数は 20 を超えない。

出力
各データセットごとに、得点の最大値を１行に出力する。

入出力例
入力例
2 20 0 0 1 0 0 0 1 0 0 0 1 0 0 0 11 0 0 0 1 0 0 0 1 0 0 0 1 0 0 00 0 0 1 0 0 0 1 0 0 0 1 0 0 0 11 0 0 0 1 0 0 0 1 0 0 0 1 0 0 02 20 0 1 0 1 1 1 1 0 0 1 0 0 0 1 0
0 1 0 1 0 1 1 1 0 1 0 1 0 0 0 0
0 0 1 0 1 0 0 0 0 0 1 0 0 0 1 00 0 0 0 0 1 1 1 0 0 0 0 0 0 0 05 30 0 0 0 0 1 1 0 0 1 1 0 0 0 0 0
1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 10 0 0 0 0 0 0 1 0 0 0 1 0 0 0 00 0 0 0 1 0 0 0 1 0 0 0 0 0 0 00 1 1 0 0 0 0 0 0 0 0 0 0 1 1 00 0 0 0 0 1 1 0 0 1 1 0 0 0 0 0
1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 00 0 0 1 0 0 0 1 0 0 0 1 0 0 0 10 0

出力例8716問題 9有限体電卓（16 点）

0 以外のすべての実数の逆数は実数になりますが、整数の逆数が整数になるとは限りません。Ｃ言語などで 3.0/2.0*2.0 = 3.0 なのに 3/2*2 = 2 になってしまうのはこのためです。ですが、素数で割った余りが等しい整数を同じものとみなすと、0 以外のすべての整数が逆数をもつようにできます。
整数 x と y を p で割った余りが等しいとき、x ≡ y (mod p) と書きます。p が素数のとき、このような x と y を同じものとみなすなら、すべての整数 n は 0 から p–1 までのどれかの整数 x に対して x≡ n (mod p) となるので、けっきょく { 0, 1, 2, ..., p–1 } という集合だけからなる世界を考えればよいことがわかります。
この世界での加減乗除は以下のようになります。


加算 x+y の値は、x+y ≡ z (mod p) となる 0 から p–1 までの数 z になります。
減算 x–y の値は、y+m ≡ 0 (mod p) となる 0 から p–1 までの数 m（これが –y に相当します）
について、x–y ≡ x + m (mod p) となることから得られます。たとえば、p=5 のとき、4+1 ≡ 0
(mod 5) となります。このとき、2–4 ≡ 2+1 ≡ 3 (mod 5) より、2–4 の値は 3 になります。
乗算 x*y の値は、x*y ≡ z (mod p) となる 0 から p–1 までの数 z になります。

除算 x/y の値は、y*d ≡ 1 (mod p)となる 0 から p–1 までの数 d（これが y の逆数になります）について、x/y ≡ x*d (mod p) となることから得られます。たとえば、p = 5 のとき、2*3 ≡ 1 (mod5) より 3 は 2 の逆数になります。このとき、1/2 ≡ 1*3 ≡ 3 (mod 5) より、1/2 の値は 3 になります。
このようにして加減乗除の四則演算がすべて 0 から p–1 の範囲に収まります。このとき、集合{ 0,1,...,p–1 } を p の有限体といいます。この有限体の中で、加減乗除、0 から p–1 までの数、カッコを使って 算術式を構成することができます。
p の有限体の 0 以外のすべての要素が逆数をもつことは、フェルマーの小定理と呼ばれる有名な定理
ap-1 ≡ 1 (mod p) からわかります（ただし、pは素数、aとpは互いに素）。p の有限体のすべての要素xはpと互いに素なので、この定理からx*xp-2 ≡ 1 (mod p) となり xp-2 がxの逆数になるからです。
では、素数と式が与えられたときに、その素数の有限体で式を計算する電卓プログラムを作成してください。

入力
入力は複数のデータセットからなる。入力の終わりは 0 の後にコロンが１つ続くだけの行 0: で示される。各データセットは以下の形式で与えられる。

p:exp

データセットは１行であり、p (2≦n≦46000) は素数、exp は算術式を示す。exp は加減乗除（それぞれ +, -, *, /）とカッコ、0 から p-1 までの数から構成される。演算子、数、カッコなどの前後には 1つ以上の空白が現れる可能性がある。exp の長さは 100,000 を超えない。
データセットの数は 1000 を超えない。

出力
データセットごとに、計算結果を出力する。出力形式は以下の通りである。

exp = val (mod p)

val は、p の有限体での算術式 exp の計算結果である。ただし、0 での除算が含まれるときは NG と出力する。また、exp に現れる加減乗除、カッコ、数の前後には空白を空けないこと。ただし、= の前後には空白を一つずつ空ける。また、val と開きカッコの間、mod と p の間にも空白を一つずつ空ける。

入出力例
入力例

出力例

5: 2 - 3

2-3 = 4 (mod 5)

17: 1 + 3 * (2 + 3 / 5 * 2) + 7

1+3*(2+3/5*2)+7 = 4 (mod 17)

11: 1 / 8 - 5 - 8 * 2

1/8-5-8*2 = 8 (mod 11)

19: 8 / (2 - 3 * 7)

NG1153: 10 * 3 / 7 + ( 50 + 81 / 22 ) + 11

10*3/7+(50+81/22)+11 = 915 (mod 1153)0:

問題 10 ねこまっしぐら（20 点）

あるところに、高い塀に囲まれた大きなお屋敷がありました。そのお屋敷の主人は猫がとても大好きで、時折やってくる猫たちのために、いつもおいしいごはんを用意していました。お腹を空かせた猫たちは、高い塀をひょいと飛び越え、お屋敷の至る所に置いてあるごはんにまっしぐらに駆け寄るのでした。
ある日主人は、屋敷の中で何匹かの猫が倒れているのを見つけました。猫たちはごはんを探して屋敷の中を縦横無尽に走り回ったので、ぶつかったり転んだりしてしまったのです。主人は猫たちの安全を考えて、ごはんの置き場所を工夫することにしました。
ごはん

ごはん

上空から見ると、このお屋敷の塀は多角形をなしています。主人は猫たちがごはんを見つけやすいように、敷地内の中でも、多角形の頂点にあたる場所だけにごはんを置くことにしました。また猫たちは気まぐれなので、多角形の周上のどの点からお屋敷に入ってくるかは予想できません。そこで主人は、猫がどの点から入ったとしても、その点から直進していずれかのごはんにたどり着けるように、ごはんを配置することも決めました。
すべての頂点にごはんを配置すれば、この条件を満たすことができます。しかし、ごはんを補充して回るのは大変なので、主人はできるだけ少ない数の頂点にごはんを配置したいと思いました。さて、主人は最低何箇所にごはんを配置する必要があるでしょうか。
お屋敷の塀を表す多角形を入力とし、ごはんを配置する頂点の数の最小値を求めるプログラムを作成して下さい。ただし、猫は多角形の内部のみを直進できるものとします（辺は多角形の内部に含めるものとします）。

入力
入力は複数のデータセットからなる。入力の終わりはゼロ１つの行で示される。各データセットは以下の形式で与えられる。

nx1 y1x2 y2...

xn yn
１行目に多角形の頂点の数n (3≦n≦16)が与えられる。続くn行に多角形の頂点の座標が与えられる。n行のそれぞれは、１つの空白で区切られた２つの整数からなる。x i (-1000≦x i ≦1000)はi番目の頂点のx座標、y i (-1000≦y i ≦1000) はi番目の頂点のy座標を示す。多角形の頂点は、隣り合った頂点を反時計回りに訪問するような順番で与えられる。
データセットの数は 20 を超えない。

出力
各データセットごとに、ご飯を配置する頂点の数を１行に出力する。

入出力例
入力例
8出力例
10 03 26 228 66 57 70 43 480 05 35 24 16 18 66 42 40