問題１

パソコン甲子園の参加者数（３点）

選手のみなさん、パソコン甲子園にようこそ。パソコン甲子園では、現在、プログラミング部門、モバイル部門、そして、いちまいの絵ＣＧ部門、計３部門の競技が開催されています。大会の運営に当たって参加者の総数を求める必要がありますが、参加者数は部門ごとに集計されているので全体の人数がわかりません。

課題各部門の参加者数が与えられたとき、参加者の総数を計算するプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
p m c
入力は１行であり、プログラミング部門の参加者数p(0≦p≦10000)、モバイル部門の参加者数m(0≦m≦10000)、いちまいの絵ＣＧ部門の参加者数c(0≦c≦10000)が与えられる。

出力
参加者の総数を１行に出力する。

入出力例
入力例１10 10 20

出力例１40

入力例２100 0 0

出力例２100

入力例３1000 1000 1000

出力例３3000

問題２

猪苗代湖の魚釣り競争（４点）

浩と健次郎の兄弟は猪苗代湖に魚釣りをしに来ました。二人は以下のように点数を決め、釣り上げた魚の合計得点で勝負することにしました。


イワナは１匹 a 点

ヤマメは１匹 b 点
イワナ１０匹ごとに c 点追加

ヤマメ２０匹ごとにｄ点追加

課題
浩と健次郎が釣り上げた魚の数をもとに、どちらが勝ちか、あるいは引き分けか判定するプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
h1 h2
k1 k2a b c d
１行目には、浩が釣り上げたイワナの数h 1 (0≦h 1 ≦100)とヤマメの数h 2 (0≦h 2 ≦100)が与えられる。２行目には、健次郎が釣り上げたイワナの数k 1 (0≦k 1 ≦100)とヤマメの数k 2 (0≦k 2 ≦100)が与えられる。
３行目には、イワナ１匹ごとの点数a(1≦a≦100)、ヤマメ１匹ごとの点数b(1≦b≦100)、イワナ１０匹ごとの追加点数c(0≦c≦100)、ヤマメ２０匹ごとの追加点数d(0≦d≦100)が与えられる。

出力
浩が勝ちなら hiroshi、健次郎が勝ちなら kenjiro、引き分けなら even と１行に出力する。

入出力例
入力例１5 13 1
1 2 5 5

出力例１hiroshi

入力例２5 14 2
1 2 5 5

出力例２kenjiro

入力例３0 2010 0
1 1 10 0

出力例３even問題３

カエルはまっすぐ帰る（６点）

一匹のカエルが巣穴に帰ろうとしています。巣穴はカエルの D センチメートル前方にあって、カエルは巣穴に向かってまっすぐ進みます。カエルができる行動は、以下の２つだけです。
大ジャンプ（L センチメートル前方に進む）

小ジャンプ（１センチメートル前方に進む）

カエルは巣穴を跳び越すことなく、ちょうど巣穴に着地することをねらっています。

課題
カエルが巣穴に帰るために、最低何回跳ぶ必要があるかを求めるプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
D L
入力は１行であり、巣穴までの距離D(1≦D≦10000)と大ジャンプでカエルが進む距離L(2≦L≦10000)が与えられる。

出力
カエルが最低何回跳ぶ必要があるかを、１行に出力する。

入出力例
入力例１10 5

出力例１2

入力例２7 4

出力例２4

問題４ＡＺＡＳ（８点）

秘密の組織アイヅアナリティクス(AiZu AnalyticS)は、極秘の調査を開始した。ターゲットになっている人物は N 人いて、1 から N の識別番号が付けられている。AZAS 情報戦略担当調査員であるあなたは、ターゲットの中から、以下の条件を少なくとも一つ満たす人物の数を割り出すことにした。


組織Ａに属さず、かつ、商品Ｃを所持している者。
組織Ｂに属し、かつ、商品Ｃを所持している者。

課題
組織Ａに属している者、組織Ｂに属している者、商品Ｃを所持している者の識別番号が入力として与えられたとき、条件を満たす人物の数を割り出すプログラムを作成せよ。ただし、どちらの条件も満たす人物を重複して数えないように注意せよ。
（補足：上記の条件について）
１からＮまでの自然数の集合から、いくつかの要素を選んだ集� ∩ C) ∪合をＡ，Ｂ，Ｃとする。条件を満たす人物の数は、(A(B ∩ C)（図の塗られた部分)を満たす要素の個数である。ただし、
� は集合Ａの補集合とする。
A入力

ＡＢＣ

入力は以下の形式で与えられる。
NX a1 a2 … aX
Y b1 b2 … bY
Z c1 c2 … cZ
入力は４行であり、１行目に調査対象の人数N(1≦N≦100)が与えられる。２行目に、組織Ａに属している者の数X(0≦X≦N)と、それに続いて組織Ａに属している者の識別番号a i (1≦a i ≦N)が与えられる。３行目に、組織Ｂに属している者の数Y(0≦Y≦N)と、それに続いて組織Ｂに属している者の識別番号b i (1≦b i ≦N)が与えられる。４行目に、商品Ｃを所持している者の数Z(0≦Z≦N)と、それに続いて商品Ｃを所持している者の識別番号c i (1≦c i ≦N)が与えられる。

出力
条件を満たす人物の数を１行に出力する。

入出力例
入力例１53 1 2 32 4 52 3 4

出力例１1

入力例２100
3 1 100 402 2 3

出力例２2問題５プログラミングコンテスト（９点）

今年も白虎大学でプログラミングコンテストが開催されることになりました。コンテストではいくつかの問題が出題され、それぞれ難易度に応じた得点が割り当てられています。
実行委員会は、解いた問題の数とそれらの得点の両方を考慮し、次のルールに基づいて各チームのスコアを計算することにしました。
「あるチームが正解した問題のうち、得点がＡ以上であるものがＡ問以上あることを満たすような最大のＡを、そのチームのスコアとする」

課題あるチームが正解した問題の数と、それらの問題の得点から、チームのスコアを計算するプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
Np1 p2 … pN
１行目にチームが正解した問題の数 N(1≦N≦100)が与えられる。２行目に正解した各問題の得点 p i (1≦p i ≦100)が与えられる。

出力
チームのスコアを１行に出力する。

入出力例
入力例１75 4 3 10 2 4 1

出力例１4

得点が4以上の問題を4問以上正解しているので、スコアは4となる。
入力例２3
1 1 100

出力例２
1

得点が1以上の問題を1問以上正解しているので、スコアは1となる。
入力例３411 15 58 1

出力例３
3

得点が3以上の問題を3問以上正解しているので、スコアは3となる。

問題６品質管理（１２点）

会津タカダ市が生産販売する布製コースターは、対称なデザインでとても美しいことで知られている。
会津タカダ市では品質管理の一環として、製造ラインにカメラを設置し、各コースターを撮影して得られた画像が対称になっているかを自動で検証している。各コースターは N×N ピクセルの正方形の白黒画像として表される。各ピクセルは白または黒の画像に対応して、0 または 1 の値をとる。
この度、生産ラインの機器更新にともなって、画像解析システムのソフトウェアを更新することになった。新システムでは、通信データ量を削減する工夫がなされ、以下の方法でカメラから解析システムにデータが送られてくる。


ラインに流れてくる最初のコースターの情報は、N×N ピクセルの画像としてシステムに送られてくる。



２枚目以降のコースターの情報は、１つ前に送られた画像との差分だけが送られてくる。差分は、「0 から 1」または「1 から 0」へと変化したピクセルの位置の集合として与えられる。

課題
C 枚のコースターについて、１枚目の画像のピクセル情報と続く C–1 枚分の差分情報を入力し、上下対称かつ左右対称となっているコースターの枚数を報告するプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
C N
p 11 p 12 …p 1N
p 21 p 22 …p 2N:
p N1 p N2 …p NN
diff 1
diff 2:diff C-1
１行目にコースターの枚数 C(1≦C≦10000)と画像の縦と横のピクセル数 N(2≦N≦1000 かつ N は偶数)が与えられる。
２行目から N+1 行目に最初のコースターの画像のピクセルを表す N 行×N 列の数字 p ij (p ijは 0 または 1)が与えられる。
N+2 行目以降に、２枚目以降のコースターの情報を表す差分 diff i が次の形式で与えられる。
D
r1 c1
r2 c2
:
rD cD
１行目に変化したピクセルの数D(0≦D≦100)が与えられる。続くD行に変化したピクセルの行と列の番号をそれぞれ表すr i とc i (1≦r i ,c i ≦N)が与えられる。diff i の中に、同じ位置は２回以上与えられない。

時間制限
入力に対して、実行時間が５秒を超えてはならない。

出力
上下対称かつ左右対称となっているコースターの枚数を１行に出力する。

入出力例
入力例１7 80010000000011000
10111101
0110011001000110
10111101
00011000
00100100
25 3
1 616 836 83 3
3 626 36 6023 86 8

出力例１3

入力例１のコースターの画像を以下に示す。この場合、２枚目、５枚目、６枚目のコースターが上下対称かつ左右対称となるため、3と報告する。

入力例２1 6000000
000000010010010010000000000000

出力例２1

入力例３2 20000
41 1
1 22 1
2 2

出力例３2問題７

部活動調査

（１３点）

A 高校の生徒会長である明は、A 高校の生徒がどの部活動に所属しているかを調査することにした。A
高校には 1 から N の番号が付けられた N 人の生徒と、1 から M の番号が付けられた M 種類の部活動がある。各部活動に人数制限はなく、０人の部活動もありえる。ただし、A 高校の校則では生徒はひとつの部活動までしか所属できない。生徒は全員この校則を守っている。
明は生徒会員に調査を依頼し、各行が次のいずれかであるような K 行の記録を入手した。
生徒 a と生徒 b は同じ部活動に所属している。

生徒 c は部活動 x に所属している。

しかし、この記録には誰かが校則違反になってしまうような矛盾があるかもしれない。明は１行目から順に見ていき、矛盾があると判断できる最初の行を探すことにした。

課題
K 行の記録が与えられたとき、矛盾があると判断できる最初の行の番号を求めるプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
N M K
record 1
record 2:
record K
１行目に生徒の人数 N(1≦N≦100000)、部活動の種類の数 M(1≦M≦100000)、記録の行数 K(1≦K≦200000)が与えられる。続く K 行に記録の各行 record i が、以下のいずれかの形式で与えられる。
1 a bまたは2 c x
先頭の数字が「1」のとき、生徒a(1≦a≦N)と生徒b(1≦b≦N)が同じ部活動に所属していることを示す。
ただし、a≠bである。
先頭の数字が「2」のとき、生徒c(1≦c≦N)が部活動x(1≦x≦M)に所属していることを示す。

時間制限
入力に対して、実行時間が３秒を超えてはならない。

出力
矛盾があると判断できる最初の行の番号を１行に出力する。見つからない場合は 0 を１行に出力する。

入出力例
入力例１3 2 5
1 1 2
1 2 3
2 1 1
2 3 22 2 1

出力例１4入力例２3 2 4
1 1 22 1 1
2 3 22 2 1

出力例２0

入力例３3 2 2
1 1 22 1 1

出力例３0

問題８

石版

（１５点）

古代国家イワシロの遺跡から無数の石版が発見された。研究者の調査によって、各石版には一つの単語が刻まれていることが分かった。しかし、長年の風化によって、以下の理由で解読が困難な石版もあるようだ。


こけ

石版に書かれている単語の一つの文字だけが 苔 で覆われている場合があり、その文字を把握するAEことができない。


石版の左側が欠けており、そこに何か文字列が書かれていたかもしれない（石版の左側０文字以上を把握することができない）。



石版の右側が欠けており、そこに何か文字列が書かれていたかもしれない（石版の右側０文字以上を把握することができない）。

石版に苔が生えている場所は多くても一か所しかない。また、欠けた石版に苔が生えていることはあるが、石版の両側が同時に欠けていることはない。

研究者は、石版発見以前の調査でわかっている単語をまとめた辞書を持っている。しかし、風化の影響による苔と欠けがある石版から元の単語を推測したとき、辞書の中の単語に当てはまるものがいくつあるか、すぐには分からない。

課題
石版の情報が与えられたとき、与えられた辞書の中に当てはまりそうな単語がいくつあるかを数えるプ
ログラムを作成せよ。

入力
入力は以下の形式で与えられる。
N M
word 1word 2:
word Nslate 1slate 2:slate M
１行目に辞書に載っている単語の数N(1≦N≦50000)、石版の数M(1≦M≦100000)が与えられる。続くN行に単語word i が与えられる。単語は英小文字のみを含む長さが1以上200以下の文字列である。ただし、N個の単語は全て異なる。続くM行に、各石版の情報を表す文字列slate i が与えられる。slate i は英小文字、「?」、「*」を含む長さが1以上200以下の文字列である。?は苔に覆われた文字を表す。?は一つの文字列に、多くとも一つしか現れない。文字列の先頭が*の場合、石版の左側が欠けていることを示す。文字列の末尾が*の場合、石版の右側が欠けていることを示す。*は、文字列の先頭か末尾以外には現れず、同時に両側に現れることはない。*が一つだけの文字列が与えられることはない。時間制限
入力に対して、実行時間が１０秒を超えてはならない。

出力
各石版について、単語の数を１行に出力する。

入出力例
入力例１5 4aloe
apple
apricot
cactuscat
apple
ap**eca?*

出力例１1222問題９ヒバラ海に沈む遺跡（１５点）

アイヅ考古学会は、ヒバラ海に沈む古代国家イワシロの遺跡調査に乗り出した。遺跡はヒバラ海のどこか一か所に存在する。そこで、探査レーダを使い、海岸線からのレーダ探査で遺跡の位置のおおよその目星を付け、海岸線から最大何メートル離れた位置まで調査しなければならないかを見積もることにした。

海側

観測点１のレーダが示す範囲
観測点３のレーダが示す範囲

観測点２のレーダが示す範囲
調査する
最大距離x

海岸線
観測点１

観測点２

観測点３

陸側

上図のような直線で表された海岸線上に観測点を設置し、探査レーダを置く。探査レーダでは、観測点を中心とする、ある大きさの半円の範囲に遺跡があるということしかわからない。しかし、複数の観測データを組み合わせることで、より狭い範囲に絞り込むことができる。

課題
観測点の位置と探査レーダが示す半径からなるいくつかの観測データが与えられたとき、海岸線から最大でどのくらいの距離まで調査する必要があるかを求めるプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
Nx1 r1x2 r2:xN rN
１行目に探査レーダによって測定されたデータの数N(1≦N≦100000)が与えられる。続くN行に、観測データiの海岸線上での位置をメートル単位で表す整数x i (0≦x i ≦1,000,000)と、その位置から半径何メートル以内に遺跡が存在するかを表す整数r i (1≦r i ≦1,000,000)が与えられる。観測点が同じ観測データが２つ以上与えられることもある。
与えられた観測データが複数の場合、それらすべての半円に含まれる点が必ず存在すると考えてよい。

時間制限
入力に対して、実行時間が５秒を超えてはならない。

出力
海岸線から最大で何メートルまで調査する必要があるかを実数で出力する。ただし、誤差がプラスマイ
ナス 0.001 メートルを超えてはならない。この条件を満たせば小数点以下は何桁表示してもよい。

入出力例
入力例１20 21 2

出力例１1.936

入力例２30 3
1 22 1

出力例２1.0

入力例３20 13 2

出力例３0.0

問題１０ 滑降競技

（１５点）

あなたは磐梯山で開催されるスキー競技に参加します。この競技では、ゲレンデを各選手が２回滑降し、その合計時間の短さを競います。ゲレンデにはいくつもの旗が立っていて、それらの間には選手が通るラインが設定されています。選手はスタート地点からゴール地点まで、ラインをたどりながら滑降します。ラインは以下のように設定されています。


ゴール地点以外の旗からは一本以上のラインが延びている。



ある旗とある旗を直接結ぶラインは多くても一つしかない。
ラインは決まった方向にしか滑降できない。
どの旗にも必ずスタートからたどり着くことができ、どの旗からもゴールにたどり着ける。



どのようにラインをたどっていっても、同じ旗に戻ることはない。

選手は現在いる旗から延びているラインを選んで次に行く旗を決めることができます。ラインの選び方は自由なので、選手は滑降ごとに異なるラインを通ってゴールに向かうことができます。
競技前夜、スポーツドクターのソルト君が、あなたが滑るときのゲレンデの状態を予想してくれました。
それによると、１回目の滑降で通ったラインは通過の影響で雪質が変わってしまうため、２回目の滑降で同じラインを通ると、かかる時間が変わることがあるそうです。ソルト君は、それぞれのラインを１回目に通るときの時間と、２回目に通るときの時間を教えてくれました。あなたはこの情報をたよりに、２回の滑降の合計時間を最短にする滑り方を朝までに見つけなければなりません。

課題
ゲレンデの状態が与えられたとき、２回の滑降の合計時間でもっとも短い値を計算するプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
N P
s 1 e 1 t 1,1 t 1,2s 2 e 2 t 2,1 t 2,2:s P e P t P,1 t P,2
１行目に、旗の数N(2≦N≦1000)と２つの旗を結ぶラインの数P(1≦P≦2000)が与えられる。旗には1からNまでの番号が振られていて、スタート地点の旗の番号が1、ゴール地点の旗の番号がNである。続くP行に、２つの旗を結ぶラインの情報が与えられる。各行には、ラインの始点である旗の番号s i (1≦s i ＜N)、終点である旗の番号e i (1＜e i ≦N)、１回目に通るときの所要時間t i,1 (1≦t i,1 ≦100000)、同じラインを２回目に通ったときの所要時間(1≦t i,2 ≦100000)が与えられる。

時間制限
入力に対して、実行時間が５秒を超えてはならない。

出力
２回の滑降の合計時間でもっとも短い値を１行に出力する。

入出力例
入力例１3 31 2 1 22 3 1 2
1 3 1 3

出力例１3入力例２3 31 2 1 2
2 3 1 21 3 1 1

出力例２2

入力例３4 51 2 3 5
1 3 1 33 2 2 52 4 6 1
3 4 5 5

出力例３13