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

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

解答にあたっての注意事項
特に断りがない限り、以下のことを前提とします。
１． 入力
・ 入力フォーマットは、問題中の入力および入力例を参考にしてください。例えば、入力例に12とあった場合、キーボードの「1」を押して、「Enter」キーを押し、「2」を押して「Enter」キーを押して入力するという意味です。
・ 入力データに全角文字はありません。
・ 行頭行末に空白は含まれません。
・ 不正なデータは入力されませんので、エラー処理を記述する必要はありません。
・ 同じ行に複数のデータが与えられる場合、それぞれのデータは半角空白１文字で区切られています。
・ 特に断りがない入力データは整数です。
２． 出力
・ 出力フォーマットは、問題中の出力及び出力例を参考にしてください。例えば、出力
例に123とあった場合、1行目に１を、2行目に2を、3行目に3を出力するという意味です。
・ 問題で求められているとおりに出力してください。余計な文字(英数字、記号、空白、改行)を出力した場合や、必要な空白や改行を出力しない場合も不正解となります。
・ 出力に全角文字は含めないでください。
３． 入出力例について
・ 各問題には、入出力例が示されていますので、よく確認してから解答してください。

問題１

アカ・ベコと４０人の盗賊（7 点）（※この問題は審査員特別賞対象問題です）
40 人の盗賊から逃れようとしているアカ・ベコは、A 市の街中で道に迷ってしまった。アカ・ベコは新しいアジトがある B 市に行きたいのだが地図を盗賊に盗まれてしまった。
盗賊の一人であるコボー氏はアカ・ベコに同情し、気の毒に思っていた。そこで、密かにアカ・ベコに、「あなたが B 市に行くお手伝いをしたいが、仲間にばれない様にしなければならないので、直接道順を教えたいが教えることができない。しかし、あなたの質問には答えられる。」と伝言を送った。
コボー氏は、「○○という道順はどうか。」という質問をアカ・ベコから受け取ると、それが A 市から B市までちょうどたどり付ける道順なら Yes、そうでなければ No という答えを伝える。道順のチェックは
以下の地図に従って行う。

各都市は一方通行の道でつながっており、それぞれの道には、0 か 1 の数字が付いている。アカ・ベコ
は数字の並びで道順を指定する。例えば、0100 は A 市から X、Z、W 市を経由して B 市にちょうどたどり着く道順である。地図にない道順を選ぶと砂漠に迷い込んでしまい、決して B 市にたどり着くことはない。アカ・ベコは自分がいる都市の名前を知ることはできないため、道順をたどり終えたときにちょう
ど B 市に到達する必要がある。
コボー氏はアカ・ベコからの質問に答えるために、あなたを密かに雇いプログラムの作成を依頼した。
アカ・ベコからの質問を入力すると、それが A 市から B 市にちょうどたどり付ける道順なら Yes、そうでなければ No と出力するプログラムを作成してほしい。

入力
入力は複数のデータセットからなる。入力の終わりは#（シャープ）１つの行で示される。各データセ
ットは以下の形式で与えられる。
p

１行に道順を示す数字 0,1 の並び p が与えられる。p は100文字を超えない文字列である。

データセットの数は 100 を超えない。

出力
データセットごとに、Yes または No を１行に出力する。

入出力例
入力例
0100

出力例
Yes

0101

No

10100

Yes

01000

No

0101011

Yes

0011

No

011111Yes#
４つ目のデータセットでは、B 市を通りすぎて Y 市に到達する道順なので No と出力する。
５つ目のデータセットでは、同じ都市を何度か通っているが、B 市にちょうどたどり着く道順なので Yesと出力する。
６つ目のデータセットでは、X 市から砂漠に迷い込んでしまい B 市にはたどり着けないので No と出力する。
最後のデータセットでは、B 市をいったん通り過ぎてから、X 市と Z 市を経由して B 市にちょうどたど
り着く道順なので Yes と出力する。

問題２

ブロックの三角形（7 点）

図 a のように積まれたブロックに対し、以下の並べ替え操作を繰り返す。
(1) 一番下のブロック全て（図 a 中の白のブロック）を右端に新しく積み上げる（残りのブロックは自動的に１段下に落ち、図 b のようになる）。
(2) ブロックの間に隙間ができたら、左に詰めて隙間をなくす（図 b から図 c のようになる）。
1 以上の整数 k に対して、k×(k＋1)/ 2 で表される数 (例:1, 3, 6, 10, ...)を三角数という。ブロッ
クの総数が三角数の場合、上記の並べ替えを繰り返すと、左端の高さが 1 で右に向かって１つずつ高くなっていくような三角形になると予想されている（図 d は総数が 15 個の場合）。

…
a

b

c

d

ブロックの最初の並びが与えられたとき、あらかじめ決められた回数以下の操作で、上で説明したようなブロックの三角形ができるとき、三角形が得られるまでの最小の操作回数を出力するプログラムを作成してください。

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

各データセットは２行であり、ブロックの最初の並びを表す。N(1≦N≦100)は、一番下の段にあるブロックの数を示す。bi(1≦bi≦10000)は左からi番目の位置に積まれているブロックの数を示す。ただし、ブロックの総数は 3 以上である。
データセットの数は 20 を超えない。

出力
データセットごとに、三角形ができるまでに行った並べ替え操作の回数を１行に出力する。ただし、三角形が作れない場合や、操作回数が 10000 回を超える場合は -1 を出力する。

入出力例
入力例
6

出力例
24

1 4 1 3 2 4

0

5

10

1 2 3 4 5

-1

10

48

1 1 1 1 1 1 1 1 1 1

5049

9

-1

1 1 1 1 1 1 1 1 1
12
1 4 1 3 2 4 3 3 2 1 2 2
15050
310000 10000 100
0
最初のデータセットが、図に示した場合に対応する。
４つ目のデータセットが、ブロックの総数が三角数でないため、三角形が作れない場合に対応する。
最後のデータセットが、ブロックの総数は三角数だが、操作回数が10000回を超える場合に対応する。

問題３

金剛の型

(7 点)

以下のように、右から 7 ビット分が小数部、続く 24 ビット分が整数部で、一番左の 1 ビット分を符号部とする 32 ビット実数型を考える(b1,...,b32 は 0 か 1 を表す）。
1 ビット
(符号部)
32

31

24 ビット
(整数部)
30

29

28

27

26

25

24

23

22

21

20

7 ビット
(小数部)

19

18

17

16

15

14

13

12

11

10

9

8

7

6

5

4

3

2

1

b32 b31 b30 b29 b28 b27 b26 b25 b24 b23 b22 b21 b20 b19 b18 b17 b16 b15 b14 b13 b12 b11 b10 b9 b8 b7 b6 b5 b4 b3 b2 b1

この形式を、人が理解しやすい 10 進数表現に直すときは、以下のように解釈する。

 1符号部  (整数部  小数部)上の表現で、整数部の値は b8＋21×b9＋22×b10＋…＋223×b31 になる。例えば整数部が
31

30

29

28

27

26

25

24

23

22

21

20

19

18

17

16

15

14

13

12

11

10

9

8

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

1

0

1

1

のようになっていた場合、整数部の値は以下のように計算される。

1  21  23  1  2  8  11
一方、小数部の値は(0.5)1×b7＋(0.5)2×b6＋…＋(0.5)7×b1 になる。例えば小数部が
7

6

5

4

3

2

1

1

0

1

0

0

0

0

のようになっていた場合、小数部は以下のように計算される。

0.51  0.53  0.5  0.125  0.625
さらに、符号部、整数部、小数部を合わせた以下のようなビット列の場合、
32

31

30

29

28

27

26

25

24

23

22

21

20

19

18

17

16

15

14

13

12

11

10

9

8

7

6

5

4

3

2

1

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

1

0

1

1

1

0

1

0

0

0

0

ビット列全体が表す 10 進数は、以下のようになる(ただし、-1 の 0 乗は 1)。

 10  (1  2  8  0.5  0.125)  1 (11.625)  11.625
32 ビットのビット列を Q 個入力すると、それらのビット列が表す実数の 10 進表記を一切の誤差無く出力するプログラムを作成してください。

入力
入力は１つのデータセットからなる。入力データは以下の形式で与えられる。
Q
s1
s2
:
sQ

1 行目にビット列の数 Q(1≦Q≦10000)が与えられる。続く Q 行に入力ビット列 si が与えられる。 入力

ビット列は 16 進数表記で与えられるとする (例: 0111 1111 1000 1000 0000 0000 0000 0000 は 7f880000と与えられる) 。つまり、Q 行のそれぞれには、2 進数を 4 ビット分ずつまとめた 16 進数が 8 個、空白をはさまずに並んでいる。10 進数、2 進数、16 進数の対応は以下の表のとおりである。
10 進数

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

2 進数 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
16 進数

0

1

2

3

4

5

6

7

8

9

a

b

c

d

e

f

16 進数の英字 a から f までは小文字で与えられる。

出力
各ビット列が表す実数の 10 進表記を 1 行ずつ出力する。ただし、小数部において、ある桁以下がすべて 0 の場合、その桁以下は省略するものとするが、例外として小数部が 0 の場合は小数部には 0 ひとつを出力する。

入出力例
入力例
8

出力例
0.0

00000000-0.0

80000000

1.0

00000080

0.500000040

1.5000000c0

2.000000100-15.0

80000780-30.875

80000f70

問題４

風よ、私の梅の香りを届けておくれ！

（10 点）

引っ越しが決まり、この地を去ることになった。この土地自体に未練は無いが、１つだけ気になることがある。それは、庭に植えた梅の木のことだ。私は毎年、この梅が花を咲かすことを楽しみにしていた。
ここを離れた後は春の楽しみが１つ減ってしまう。私の梅の香りだけでも風に乗って引っ越し先の家まで届き、春を楽しませてはくれないものか。
日本には春を象徴する３つの花がある。梅・桃・桜の３つだ。引っ越し先には、私の梅以外にも、これらの花の香りが届くだろう。しかし、私の梅の香りだけが届く日数が最も多い家に住みたい。
図のように、花の香りは扇状に広がり、その領域は風の向かう方向と強さによって決まる。扇形は風の向かう方向 w を中心にして対称に広がり、風の強さ a を半径とする領域をもつ。香りが広がる角度 d は花の種類によって決まっているが、風の向かう方向と強さは日によって異なる。ただし、同じ日では、すべての場所で風の向かう方向と強さは同じである。
手元には、私の梅以外の梅・桃・桜の位置と花の種類ごとの香りが広がる角度、引っ越し先の家の候補のデータがある。さらに、数日分の風の向かう方向と強さのデータもある。私の梅以外の梅・桃・桜の木と家の位置は、私の梅の位置を原点とした座標で示されている。
これらのデータを使って、私の梅の香りだけが届く日数の最も多い家を探すためのプログラムを書いてみることとしよう。私は有能なプログラマーなのだから！

入力
入力は複数のデータセットからなる。入力の終わりはゼロ２つの行で示される。各データセットは以下の形式で与えられる。
H R
hx1 hy1hx2 hy2:hxH hyHU M S du dm ds
ux1 uy1ux2 uy2:uxU uyUmx1 my1mx2 my2:mxM myMsx1 sy1sx2 sy2:sxS syS
w1 a1
w2 a2
:
wR aR

１行目に引っ越し先の家の候補の数 H(1≦H≦100)と風の記録の数 R(1≦R≦100)が与えられる。続く H行に引っ越し先の家の位置が与えられる。hxi と hyi は i 番目の家の x 座標と y 座標を示す-1000 以上 1000
以下の整数である。
続く１行に、私の梅以外の梅の木の数 U と、桃・桜の木の数 M、S、梅・桃・桜の香りが広がる角度 du、dm、ds が与えられる。U、M、S の範囲は 0 以上 10 以下である。角度の単位は度であり、1 以上 180 未満の整数である。
続く U 行に私の梅以外の梅の木の位置、続く M 行に桃の木の位置、続く S 行に桜の木の位置が与えられる。uxi と uyi、mxi と myi、sxi と syi はそれぞれ、i 番目の梅・桃・桜の木の x 座標と y 座標を示す、-1000
以上 1000 以下の整数である。
続く R 行に風の記録が与えられる。wi(0≦wi＜360)と ai(0＜ai≦100)は i 日目の風の向かう方向と強さを表す整数である。風の向かう方向は、x 軸の正の向きから反時計回りに測った角度で表し、単位は度とする。
入力は以下の条件を満たすと考えてよい。


入力される座標はすべて異なるものとする。



原点には私の梅以外無い。



どの花についても、花の香りが届く領域の境界から距離が 0.001 以内には家は無い。

データセットの数は 50 を超えない。

出力
データセットごとに、私の梅の香りだけが届く日数の最も多い全ての家の番号を、小さい順に１行に出力する。家の番号の間は空白１つで区切る。行の終わりには空白文字を出力しない。
ただし、どの家についても、私の梅の花の香りだけが届く日が１日もなければ、NA と出力する。

入出力例
入力例
6 3
2 1
1 2
5 2
1 3
1 5
-2 3
1 1 1 90 30 45
3 -4
-3 0
2 -2
45 6
90 6
135 6
2 1
1 3
5 2
0 1 1 90 30 45
-3 0
2 -2
45 6
0 0

出力例
5 6
NA

問題５

モジュロ・クエリ（10 点）

あなたに N 枚のカードを渡します。どのカードにも一つだけ自然数が書いてあります。ただし、同じ数が書いてあることはありません。
これから質問として、適当な自然数を言います。あなたが持っているカードに書いてある数を私が言った数で割ったときに得られる余りのうち最も大きなものを答えてください。
たとえば、あなたは 3 枚のカードを持っていて、それぞれ 9、3、8 と書いてあるとします。私が「4」と言ったら、9 と 3 と 8 をそれぞれ 4 で割った余りを求めてください。余りはそれぞれ 1、3、0 ですが、この中でもっとも大きな余りは 3 なので、3 が正しい答えになります。
では始めましょうか。え？

カードがいっぱいあるとたいへんだ？

しょうがないですね。それではコンピュータを使って最大の余りを見つけることにしましょう。
カードに書いてある数を、質問された数で割った余りのうち、最大のものを見つけるプログラムを作成
してください。なお、質問は１回だけでなく何度もしますが、同じ数を 2 回以上質問することはありません。

入力
入力は１つのデータセットからなる。入力データは以下の形式で与えられる。
N Q
c1 c2 ... cN
q1
q2
:
qQ

１行目にカードの枚数 N(2≦N≦300000)と質問の回数 Q(2≦Q≦100000)が与えられ、２行目にカードに書かれた数 ci(1≦ci≦300000) が与えられる。続く Q 行に質問として与えられる数 qi(1≦qi≦300000)が与えられる。

出力
質問ごとに最大の余りを１行に出力する。

入出力例
入力例
3 3

出力例
3

9 3 8

3

4

4

6
5

問題６ イヅア国語辞典（10 点）

あなたはイヅア国の公用語であるイヅア語の国語辞典と、イヅア語のアルファベット（文字の一覧表）
を手に入れました。イヅア語のアルファベットには N 種類の文字があります。イヅア語の国語辞典に現れる単語の順番は、イヅア語のアルファベット順に並んでいます。
辞典を見ると、載っているどの単語も N 文字で、しかも、N 種類の文字をひとつずつ含んでいることがわかりました。さらに調べてみると、辞典には N 種類の文字の可能な並び方がすべて書かれていることを発見しました。
この発見から、あなたはある単語が辞典の何番目に出てくるかわかるようになりました。この知識を利用してイヅア国の人を驚かせてみましょう。まず、N 種類の文字をひとつずつアルファベット順に並べます。次に、任意の２文字の順番を入れ替える操作を R 回繰り返してもらいます。あなたは、出来上がった単語がイヅア国語辞典の何番目に出てくるか当てて見せます。そのための準備として、国語辞典中の単語の場所を求めるプログラムを作成してください。ただし、アルファベット順で最初の単語を 0 番目の単語とします。

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

１行目にアルファベットを構成する文字の数 N(1≦N≦100000)が与えられ、２行目に文字を入れ替えてもらう回数 R(0≦R≦50)が与えられる。続く R 行に、入れ替えられる文字の位置の組が与えられる。siと ti (1≦si＜ti≦N)は、先頭から数えて si 番目と ti 番目の文字を i 回目に入れ替えることを表す。
データセットの数は 100 を超えない。

出力
データセットごとに、入れ替えが終わった時点で得られた単語が国語辞典の何番目に現れるかを示す数を１行に出力する。ただし、出力すべき値は非常に大きくなりうるので、代わりに 1,000,000,007 で割った余りを出力する。

入出力例
入力例
3

出力例
3

2

4

1 2
2 3
4
2
2 3
2 4
0
入出力例の最初のデータセットについて説明する。説明のため、アルファベットは小さい方から順番に、'A', 'B', 'C' の３文字からなるとする。これらの文字をアルファベット順に並べると "ABC" という文字列が得られる。この文字列の１番目の文字 'A' と２番目の文字 'B' を入れ替えると、"BAC" という文字列が得られる。次に、得られた文字列の２番目の文字 'A' と３番目の文字 'C' を入れ替えると、
単語 "BCA" が得られる。辞典には、先頭から順に "ABC", "ACB", "BAC", "BCA", "CAB", "CBA" の６
種類の単語が載っている。"BCA" はこの中で３番目（最初の"ABC"が０番目であることに注意）に現れるので、3 を 1,000,000,007 で割った余りである 3 が答えになる。

問題７

寂しがり屋のついた嘘（10 点）

パケットモンスターというゲームがあります。モンスターを捕まえ、育て、戦わせたり交換したりするゲームで、日本中で大流行しています。もちろん、わたしのクラスでも。だからわたしもこのゲームでみんなと遊べるようにモンスターを育てているけど、悲しいことに対戦する相手がいません。わたしは積極的に人に話しかけるのが得意なタイプではないからです。だから今日も、クラスメイトが誘ってくれるのを待ちながら、独り寂しくモンスターのレベルを上げています。
そしてついに、待ち望んでいた瞬間が訪れました。クラスメイトの一人が対戦しないかとわたしに話を持ちかけてきたのでした。彼女は自慢気に、彼女のモンスターたちを見せてくれました。
一般的なパケットモンスターの対戦ルールでは、各プレイヤーがそれぞれ N 匹のモンスターを用意し、互いに 1 匹ずつ戦わせます。各モンスターには成長の度合いを示す「レベル」という数値があり、レベルが大きいモンスターが必ず勝ちます。同レベルのときは引き分けです。一度戦ったモンスターは、それ以上戦わせることができません。こうして一対一の戦いを N 回行ったあと、過半数の勝利を収めたプ
レイヤーが勝者となります。
わたしは、彼女のモンスターを見た瞬間、嫌な予感がしました。彼女のモンスターはどれも、とても強そうなのです。わたしと戦ってくれるのなら負けてもかまいません。でも、あまりにもひどい負け方をしたら、『こいつと戦っても面白くないな』とか思われて、もう遊んでくれなくなるんじゃないかな。
それは、とても嫌です。だから、「ごめん、わたしまだモンスターを N 匹持ってなくて」
嘘をつきました。
N 回勝負では勝ち目がなくても、それより少ない数のモンスターで勝負する特別ルールなら、もしかしたら勝てるかもしれません。さっきは負けたってかまわないと言ったけど、やっぱり勝てたら嬉しいです。
彼女はこの特別ルールを受け入れてくれました。つまり、二人が持っているモンスターからお互いに k
匹選んで一匹ずつ順番に戦わせ、過半数の(つまり、k/2 より大きな数の) 勝利を収めた方が勝ちとなります。
さっきわたしは、彼女のモンスターのレベルを知ってしまいました。彼女がどのモンスターを選び、どんな順番で出してくるのかはわかりません。でも、対戦させるモンスターの数kをわたしがうまく決めれば、彼女がどんな選択をしようとわたしが勝つことができるかもしれません。
皆さんにお願いです。モンスターの数 N と、二人が持っているモンスターのレベルを入力すると、彼女がどんな選択をしようとわたしが勝てるような最小のモンスターの数 k を出力するプログラムを作成して下さい。

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

１行目にモンスターの数 N(1≦N≦40000)が与えられる。２行目に自分のモンスターのレベル ai(1≦ai≦100000)が与えられる。３行目にクラスメイトのモンスターのレベル bi(1≦bi≦100000)が与えられる。
データセットの数は 50 を超えない。

出力
データセットごとに、k(1≦k＜N)が存在すれば最小値を１行に出力する。もし、k が存在しないか、kが N に等しければ NA と出力する。

入出力例
入力例
10
4 9 1 9 5 9 2 3 2 1
8 7 6 5 10 5 5 4 7 65
4 3 2 5 1
4 4 4 4 44
4 1 3 24 3 2 1
0

出力例
3
1
NA

１つ目のデータセットでは、わたしは３匹での対戦を提案し、レベルが [9, 9, 9] のモンスターを選べば良い。相手のレベル 10 以外のどのモンスターにも勝てるので、少なくとも２勝できる。２匹での対戦では １勝１敗になる可能性があり、これは過半数の勝利とは言えないので、2 は答えにならない。
２つ目のデータセットでは、わたしは最強のモンスターを１匹選べば良い。
３つ目のデータセットでは、わたしがどの k 匹を選び、どの順番で出したとしても、彼女が全く同じモンスターを同じ順番で出してきて引き分けになる可能性がある。したがって、「彼女がどんな選択をしようとわたしが勝つことができる」とは言い切れない。

問題８

ねこまっしぐら２（13 点）

あるところに大きな古いお屋敷があり、１匹のねこが住み着いていました。図のように、お屋
敷は上空から見ると凸多角形になっており、まっすぐな壁で囲まれたいくつかの部屋で造られています。１枚の壁はその両端にある柱によっ柱て支えられています。お屋敷はとても古いため、どの壁にもねこが通ることができるくらいの穴

壁が１つ空いています。ねこは壁の穴を通ってお屋敷の部屋と部屋または部屋と外を行き来することができます。
お屋敷のご主人は、ねこに餌をあげるために、口笛を吹いてねこをお屋敷の外へ呼び出します。ねこはとても賢く、ご主人が口笛を吹くと、「最良の選択」でお屋敷の外へ抜け出します。つまり、最も少な
い回数だけ穴を通って外へ出ます。
ねこはとても気まぐれで、どの部屋にいるか分かりません。そのため、ねこがお屋敷の外へ出るのにかかる時間は日によって異なり、ご主人はどれだけ待てばよいかわからず困っていました。ある時ご主人
は、ねこが穴を通り抜けるときに、とても時間がかかっていることに気が付きました。ということは、ねこが外に出るのにかかる時間は穴を通る回数によって決まることになります。ご主人は、ねこが「最良の選択」をした場合の穴を通る回数の最大値が分かれば、ねこがどの部屋にいたとしても、最大どれだけ待てばよいか分かるのではないかと考えました。ご主人はお屋敷の間取りを知っていますが、お屋敷はとても大きく、自分では計算することができません・・・。
お屋敷の間取りを読み込み、ねこが「最良の選択」をした場合、外に出るまでに通る穴の数の最大値を出力するプログラムを作成して下さい。

入力
入力は複数のデータセットからなる。入力の終わりはゼロ２つの行で示される。各データセットは以下の形式で与えられる。
C W
x1 y1
x2 y2
:
xC yC
s1 t1
s2 t2
:
sW tW

１行目に柱の数 C(3≦C≦100)と壁の数 W(3≦W≦300)が与えられる。続く C行に柱の座標が与えられる。
xi(-1000≦xi≦1000)はi番目の柱の x座標、yi(-1000≦yi≦1000)はi番目の柱の y座標をそれぞれ示す整数である。柱にはそれぞれ1からCまでの番号が割り当てられている。 続くW行に壁の情報が与えられる。

si(1≦si≦C)、ti(1≦ti≦C)は壁の両端を支える柱の番号を示す。
入力は以下の条件を満たすと考えてよい。


異なる柱が同じ位置を占めることはない。



異なる壁が重なったり、柱以外で交差することはない。



１つの柱は２つ以上の壁を支えている。



壁の長さは 0 より大きい。



柱は壁の両端だけにある。つまり、柱が壁の途中にあることはない。



壁は異なる２つの部屋、あるいは部屋と外とを仕切る。



任意の異なる２つの柱を選んだとき、互いの柱には壁をたどって到達できる。

データセットの数は 50 を超えない。

出力
データセットごとに、ねこが「最良の選択」をした場合、外に出るまでに通る穴の数の最大値を１行に
出力する。

入出力例
入力例
4 4
0 0
1 0
1 1
0 1
1 2
1 4
2 3
3 4
12 22
2 0
4 0
8 0
4 2
6 2
8 2
2 4
4 4
6 4
0 6
8 6
0 8
1 2
2 3
1 4
1 7
1 10
2 4
2 5

出力例
1
3

3 5
3 6
4 5
4 8
5 6
5 9
6 9
6 11
7 10
7 8
8 9
9 11
10 11
10 12
11 12
0 0
２つ目のデータセットが、冒頭の図に示したお屋敷の間取りに対応する。図のように、薄く色が塗られた部屋にねこがいるときは、「最良の選択」で外に出るまでに通り抜ける穴の数は３つである。それ以外の部屋にねこがいるときは、２つ以下で外に出られる。したがって、ねこが「最良の選択」をしたとき、外に出るまでに通り抜ける穴の数の最大値は 3 になる。

問題９

図画工作

（13 点）

イヅア大学附属小学校は日本有数の競技プログラマー養成校として有名です。この学校の教員は幅広い
アルゴリズムの知識を持ち、日々それを活用しています。教員であるあなたは、今年は図画工作の授業を担当することになりました。この授業では、児童全員がそれぞれ１年間で一つの課題を完成させることになっています。授業の概要は以下のとおりです。


１年間で授業は D 回（同じ日に 2 回以上授業はない）あり、その全てが課題制作に充てられる。



制作する課題は M 種類用意されている。



それぞれの児童に、M 種類の中から課題を１つずつ割り当てる。



児童は N 人であり、N 人それぞれに異なる課題が割り当てられる。

児童は、K 種類ある部品のうちいくつかの種類の部品を使用して課題を完成させます。課題の制作の概要は以下のとおりです。


課題ごとに、使用すべき部品の種類と数はあらかじめ決められている。



課題が完成するまでに使用する部品の種類と数は、その課題で使用すべき部品の種類と数に、過不足なく一致していなければならない。



異なる課題でも、使われる部品の種類と数がすべて同じ場合もある。



どの課題も、同じ種類の部品は２個までしか使用できない。



部品を使用する順序は課題の完成に影響を与えない。



いくつかの部品が入っている袋が事前に P 個用意されている。ただし、異なる袋でも、入っている部品の種類と数がすべて同じ場合もある。



教員は、児童１人につき袋を１つだけ渡すことができる（袋を渡さない児童がいてもよい）。



２人以上の児童に同じ袋を渡すことはできない（反対に、誰にも渡されない袋があってもよい）。



袋を渡された児童は、袋の中に入っている部品をすべて、自分が制作する課題に使わなければならない。

袋に入っている部品以外で課題に使用する部品は、別途購入する必要があります。部品の購入に関する条件は以下のとおりです。


部品は授業の日だけ購入でき、その日にしか使えない。



それぞれの課題について、１回の授業でＬ個までの部品を購入することができる。



部品の種類によって価格が設定されており、購入する日によって価格が変動する。ただし、どの種類も品切れになることはない。

あなたは、このような条件下で、授業にかかる経費をなるべく抑えたいと考えています。そこで、児童全員の部品購入費の合計の最小値を計算するプログラムを作成することにしました。

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

D K Lc1,1 c1,2 ... c1,K
c2,1 c2,2 ... c2,K:
cD,1 cD,2 ... cD,K
M N P
r1,1 r1,2 ... r1,K
r2,1 r2,2 ... r2,K:
rM,1 rM,2 ... rM,K
t1,1 t1,2 ... t1,K
t2,1 t2,2 ... t2,K:
tP,1 tP,2 ... tP,K

D（1≦D≦8）は授業の回数、K（1≦K≦8）は部品の種類の数、L（1≦L≦8）は１日に購入することができる部品の数を示す。cd,k （1≦cd,k≦100）は d 日目の部品 k の価格を示す。
M（1≦M≦200）は課題の種類の数、N（1≦N≦M）は生徒の人数、P（1≦P≦200）は袋の数を示す。
rm,k （0≦rm,k≦2）は課題 m に必要な部品 k の個数、tp,k （0≦tp,k≦2）は袋 p に入っている部品 k の個数を示す。
部品を１つも必要としない課題や、空の袋は与えられないものとする。
データセットの数は 20 を超えない。

出力
データセットごとに、生徒全員の部品購入費の合計の最小値を１行に出力する。Ｎ種類の作品を完成させることができない場合は -1 を出力する。

入出力例
入力例
2 2 1
5 3
2 2
3 3 1
2 0
1 2
2 2
1 1
2 2 1
5 3
2 2
3 2 1
2 0
1 2
2 2
1 1
2 2 2
5 3
2 2
3 2 1
2 0
1 2
2 2
1 1
4 3 1
2 2 1
3 2 2
2 3 3
1 2 2
5 4 3
1 1 0
1 0 1
1 0 2
1 1 2
2 2 2
1 0 1
2 0 2
1 1 1
0 0 0

出力例
-1
9
6
7

問題１０

鉄道路線（13 点）

ある国の鉄道網に、自動改札を導入することになりました。導入にあたって難しい問題の一つは、与えられた切符で、指定された駅の間を移動できるかどうかを判定することです。それぞれの切符には乗車駅と降車駅が記載されています。この切符でできるのは、「乗車駅で乗って、降車駅で降りる」ことだ
けではなく、途中乗車や途中下車も許されています。
この鉄道網には S 個の駅があり、そのうち R 組の駅は隣り合っていて、他の駅を経由せずに双方向に鉄道で移動することができます。隣り合った駅を結ぶ線路はひとつしかありません。隣り合った駅の間の距離は、この線路に沿って測った距離です。ある駅からある駅までの経路は鉄道網の形状によっては複数通り考えられますが、そのうち最も距離が短くなるような経路を最短経路と呼ぶことにします。そのような経路が複数ある場合、どちらも最短経路として認められます。
乗車駅 a、降車駅 b の切符で駅 c から駅 d まで移動できるのは、以下の条件をすべて満たす経路 p が存在するときです。


経路 p は、駅 a から駅 b への最短経路である。



経路 p は、駅 a から出発し、駅 c、駅 d の順に経由し、駅 b で終わる経路である。また、駅c から駅 d の区間はこの 2 駅の最短経路になっている。

路線図と切符の情報が与えられます。次に、始点と終点の組がいくつか与えられるので、その切符で始点から終点へ移動できるかどうかを判定するプログラムを作成してください。

入力
入力は１つのデータセットからなる。入力データは以下の形式で与えられる。

S R
u1 v1 w1
u2 v2 w2:uR vR wR
a b Q
c1 d1
:
cQ dQ

１行目は２つの整数からなる。S (2≦S≦100000) は鉄道路線図に現れる駅の数、R (1≦R≦200000) は隣り合った駅の組の数である。続く R 行に、隣り合った駅の間を直接つなぐ線路の情報が与えられる。
ui と vi(1≦ui,vi≦S)は i 番目の線路の両端の駅の番号を示す。wi(1≦wi≦1000)はこれらの駅の間の距離を表す整数である。ただし、各駅には 1 から S までの番号が重複なく割り振られており、ui≠vi とする。
続く１行は３つの整数からなる。最初の２つの整数は切符の区間を表し、a は乗車駅、b は降車駅
(1≦a,b≦S)である。３つ目の整数 Q(1≦Q≦40000)は質問の数を示す。続く Q 行に質問が与えられる。
ci と di(1≦ci,di≦S)は i 番目の質問の乗車駅と降車駅を示す。ただし、a≠b、ci≠di とする。

出力
質問ごとに、与えられた切符で移動できるなら Yes を、できないなら No を１行に出力する。

入出力例
入力例
6 7

出力例
Yes

1 2 3

Yes

1 4 1

Yes

2 3 5

Yes

4 3 1

No

3 6 2

No

4 5 2
5 6 1
1 6 6
1 6
4 3
4 6
5 6
2 6
2 5