問題文

チーム対抗早解きリレーは、10 人のメンバーからなる 20 個のチームに分かれて行うプログラミングコンテストです。

チーム分けは、参加者の本戦の順位を使って以下のような手順で決めます。

• 1 ～ 20 位の人は、順に 1 ～ 20 のチームに入る。
• 21 ～ 40 位の人は、逆順に 1 ～ 20 のチームに入る。
• 41 ～ 60 位の人は、順に 1 ～ 20 のチームに入る。
• ...

例えばチーム 1 のメンバーの本戦での順位は、それぞれ 1,40,41,80,81,120,121,160,161,200 位となります。

チーム番号が与えられるので、そのチームのメンバーの本戦の順位の和を求めてください。

入力例1

1

出力例1

1005

1 + 40 + 41 + 80 + 81 + 120 + 121 + 160 + 161 + 200 = 1005 なので 1005 と出力します。

問題文

チーム戦では協力が大切である。現在あなたはチーム対抗早解きリレーに参加している。目指すはもちろん全完（全問完答）だ。

リレーは 10 人のチームで行い、 問題 1 から問題 10 までの 10 問が与えられる。必ず一人 1 問を担当しなければならず、複数の問題を同じ人が解くことはできない。各チームメンバーについて解くことの出来る問題のリストが与えられるので、チーム全体で全ての問題に正答出来るかを判定せよ。ただし各チームメンバーは、自分が解けない問題もその問題を解くことの出来るメンバーに解法を教えてもらうことによって必ず解くことが出来るようになる。また実際のリレーには時間制限があるが、この問題では無視する。

入力例1

oxxxxxxxxx
xoxxxxxxxx
xxoxxxxxxx
xxxoxxxxxx
xxxxoxxxxx
xxxxxoxxxx
xxxxxxoxxx
xxxxxxxoxx
xxxxxxxxox
xxxxxxxxxo

出力例1

Yes

それぞれのメンバーが自分の解ける問題を担当すれば全完できる。

入力例2

xxxxxxxxxx
xxxxxxxxxx
xxxxxxxxxx
xxxxxxxxxx
xxxxxxxxxx
xxxxxxxxxx
xxxxxxxxxx
xxxxxxxxxx
xxxxxxxxxx
oooooooooo

出力例2

Yes

10 人目のメンバーが他のメンバーに 1 問ずつ解法を教えることで全完できる。

入力例3

oxxxxxxxxx
ooxxxxxxxx
ooxoxxxxxx
oooxoxxxxx
oxxxxooxxx
ooxoxxoxxx
oooooxxxxx
ooooxxoxxx
ooooxoxxox
oooooooxxo

出力例3

No

問題 8 を解ける人がいないため全完出来ない。

問題文

数字 N が与えられるので、N が円周率の小数点以下何桁目に出てくるか答えてください。 ただし、3 は円周率の小数点以下 0 桁目に出てくるとみなします。

入力例1

0

出力例1

32

入力例2

1

出力例2

1

入力例3

2

出力例3

6

入力例4

3

出力例4

0

問題文

二等辺三角形の形をしたピザを切って N 人に配分します。 ピザは底辺と平行な等間隔の直線で切ります。 すると各ピースの面積比は 1:3:5:... となります。 それぞれの人にいくつかのピースを配って同じ面積になるようにした時、ピザは少なくともいくつのピースに分割する必要があるか求めてください。

入力例1

1

出力例1

1

1 人に配る場合は、1 つのピースのままで良いです。

入力例2

2

出力例2

4

1 人目に面積比が 3 と 5 のピースを、2 人目に面積比が 1 と 7 のピースを配ると、面積が等しくなります。

入力例3

3

出力例3

6

問題文

あなたはあさプロに寝坊してしまった！ しかしまだ慌てるのは早い。あなたは魔法の道具「反転時計」で時間を操ることが出来るのだ。

時間を操ることが出来るといっても自由に時間を戻せるわけではない。 反転時計は盤に数字が書かれていない 12 時間制のアナログ時計で、180 度回転させることによって回転後の針が指す時間に移動することが出来る。具体的には、午前 h 時 m 分に反転時計を回転させると、同日の午前 ((h+6)%12) 時 ((m+30)%60) 分に移動する。例えば午前 9 時 30 分に反転時計を使うとその日の午前 3 時 00 分に戻ることが出来る。（どうやら短針の細かい位置は気にしなくてよいらしい。）

ただし反転時計の力は 1 日に 1 回しか使うことが出来ない。 また、一旦正午を過ぎてしまうと午前に戻ることはできなくなってしまうので、あまりのんびりしている時間はない。 急いであさプロが始まる時間に戻れるかどうかを考えよう。

入力例1

9 0
10 30

出力例1

Yes

午前 10 時 30 分に起きてすぐ反転時計を使うと午前 4 時 00 分に戻ることができ、あさプロに間に合う。

入力例2

3 0
10 30

出力例2

No

いつ反転時計を使っても 4 時より前に戻ることは出来ない。

入力例3

5 0
11 0

出力例3

Yes

午前 11 時 30 分まで待ってから反転時計を使うことによって午前 5 時 00 分に戻ることができる。

入力例4

9 0
8 30

出力例4

Yes

どうやら時計を見間違えたようだ。

問題文

頂点の個数と辺の本数がどちらも N であるような、無向連結グラフが何種類あるかを N=3～6 についてそれぞれ求めてください。ただし、自己ループや多重辺があってはいけません。頂点どうしや辺どうしは区別しません。

例えば N=4 のときは、下図のような 2 種類のグラフがあります。

N が大きくなっても、出来るグラフは サイクルがちょうど 1 つ含まれる グラフになります。

問題文

N 種類の主菜と M 種類の副菜から料理を選んでコースを作ります。 主菜は 1 種類しか選ぶことができませんが、副菜は何種類でも選ぶことができます。 また、副菜は 1 つも選ばなくても構いません。 主菜・副菜ともにコースに入れられるのは 1 種類につき 1 つまでです。

• i 番目の主菜は値段が A_i で、お客さんの評価が B_i です。
• i 番目の副菜は値段が C_i で、お客さんの評価が D_i です。

コース全体の値段と評価は、主菜と副菜の合計で決まります。 コースの値段を L 以下にする時、コースの評価は最大でいくつになるか求めてください。

入力例1

2 2 10
2 3
3 6
3 5
5 5

出力例1

13

入力例2

3 3 10
1 1
2 3
3 5
4 8
5 10
6 12

出力例2

19

入力例3

3 3 10
1 1
11 11
11 11
11 11
11 11
11 11

出力例3

1

問題文

縦 H 行、横 W 列のマス目があり、左上のマスを (1, 1) 、右下のマスを (H, W) という座標で表す。それぞれのマスには色 1 から色 9 の 9 色のうちいずれかの色が塗られている。

あなたはこのマス目に対して、9 色のうちのいずれかで「塗りつぶす」操作を何回か行うことが出来る。塗りつぶす操作とは、 (1, 1) から連結している同じ色のマスを全て選んだ色に変える操作である。 2 つのマスが連結しているとは、辺を共有する同じ色のマスを通じてお互いに到達できることである。以下に塗りつぶす操作の例を示す。（図は入力例1に対応している。）

H \times W のマス目の初期状態が与えられるので、 (1, 1) と (H, W) を連結にするために必要な塗りつぶす操作の回数の最小値を答えよ。

入力例1

3 3
122
131
322

出力例1

2

色 3 -> 色 2 の順に塗りつぶすと (1, 1) と (3, 3) が連結になる。

入力例2

3 3
111
231
321

出力例2

0

最初から (1, 1) と (3, 3) は連結である。

入力例3

4 5
12334
41123
43214
21344

出力例3

5

問題文

最近ある街の若者の間では Platoon Match （小隊バトル） というハイカラな遊びが流行っている。 水鉄砲を携えレインコートに身を包み、フィールド内を駆け回って敵に水を当てた回数を競うチーム戦である。

以下に詳細なルールを記す。まず N 人の参加者が（人数が均等とは限らない） 2 つのチームに分かれる。全員それぞれのチームの本陣から一斉に出発し、用意されたフィールド内を移動して敵チームのメンバーに水鉄砲を当てることを目指す。ゲーム中に敵チームのメンバーに水鉄砲で撃たれた人は一時的にゲームから抜け、即座に自分のチームの本陣に戻って再びゲームに参加する。ゲーム終了時にそれぞれの参加者は自分が敵に撃たれた回数と敵を撃った回数を自己申告し、ゲームの勝敗を決定する。

さて、あなたはこれまでの Platoon Match の記録を取っていたのだが、それぞれのゲームのチーム分けを記録し忘れており、各参加者が何回撃ったか・撃たれたかしか分からないようになっていた。そもそもこの記録はつじつまが合っているのだろうか？ひとまずあなたは記録されている各参加者の成績を実現するようなチーム分けが存在するかどうか確かめることにした。

入力例1

3
7 2
1 3
1 4

出力例1

valid

1 番目の参加者をチーム 1 、 2, 3 番目の参加者をチーム 2 とすると矛盾は起きない。（参加者 1 が参加者 2 を 3 回、参加者 3 を 4 回撃ち、参加者 2 と 3 が参加者 1 を 1 回ずつ撃ったと考えることが出来る。）

入力例2

3
2 5
3 2
4 2

出力例2

invalid

どのようにチーム分けしても矛盾が生じる。

入力例3

3
4 1
2 1
1 1

出力例3

invalid

全員の撃った回数の和と撃たれた回数の和が一致しない。

入力例4

4
0 0
0 0
0 0
0 0

出力例4

valid

どのようにチーム分けしても矛盾しない。

問題文

すぬけくんとりんごさんは、よくゲームをして遊びます。今日は石を使った以下のようなゲームをするようです。

• 2 つの石の山を作る。それぞれの山に含まれる石の個数は X 個、Y 個にする。
• すぬけくんが先手、りんごさんが後手で交互に石を取っていき、どちらかの山の石の個数を 0 にした方が負けとなる。石を取るときのルールは以下の通りである。
  • まず、2 つの山のうち残っている石の個数が少ない方の石の個数を k とする。
  • 2 つの山のどちらか一方を選び、1～k 個の石を取る。

2 人ともが勝ちを目指して最適な戦略を取るとき、どちらが勝つでしょうか？

入力例1

4 2

出力例1

snuke

ゲームは、例えば以下のような流れで進行します。

• すぬけくんが 1 つ目の山から石を 2 つ取る。
• りんごさんが 1 つ目の山から石を 1 つ取る。
• すぬけくんが 2 つ目の山から石を 1 つ取る。
• りんごさんが 1 つ目の山から石を 1 つ取る。これにより 1 つ目の山の石の個数が 0 になるためりんごさんの負けとなり、すぬけくんが勝つ。

入力例2

1 999999999

出力例2

rng

入力例3

100 999999999

出力例3

snuke

すぬけくんが最初の手番で 1 つ目の山から石を 99 個取ると入力例 2 のような状況になり、りんごさんの負けとなりすぬけくんが勝ちます。