問題文

清々しい朝だ。今日の CODE THANKS FESTIVAL は目一杯楽しむぞ。そのためにも朝ごはんをしっかりと食べないといけない。

コーヒーを淹れるのには A 分かかり、トーストを焼くのには B 分かかる。両方の準備を同時に始めたとして、朝食の準備が完了するのは何分後になるだろうか？

入力例1

10 5

出力例1

10

このケースではコーヒーを淹れるのに 10 分、トーストを焼くのに 5 分かかります。同時にコーヒーとトーストの準備を始めると、開始から 5 分後にトーストが焼き上がり、10 分後にコーヒーを淹れ終わります。したがって 10 を出力します。

入力例2

42 42

出力例2

42

問題文

あなたが持っている電卓には、足し算(+)と掛け算(×)の、2 つの演算子が存在します。

あなたには、 3 つの数字 A,B,C が与えられます。 これらの数字を電卓に、「A → 演算子 → B → 演算子 → C」の順番で入力します。

たとえば、(A,B,C)=(1,2,3) のとき、最初の演算を足し算、次の演算の演算を掛け算とすることを考えます。 この場合、入力は「1 → + → 2 → × → 3」であり、計算結果は 9 です。電卓は順番に演算を行うため、演算子の優先順位は無視して左から計算します。

あなたは、各数字の間に入れる演算をうまく定めて最大値を得る一人遊びを行うことにしました。 各数字の間に入れる演算をうまく選ぶことによって得られる計算結果の最大値を求めて下さい。

入力例1

1
2
3

出力例1

9

問題文で言及したケースです。

• 「1 → + → 2 → + → 3」を計算すると 6 が得られます。
• 「1 → + → 2 → × → 3」を計算すると 9 が得られます。
• 「1 → × → 2 → + → 3」を計算すると 5 が得られます。
• 「1 → × → 2 → × → 3」を計算すると 6 が得られます。

したがって、最大値の 9 を出力すれば良いです。

入力例2

1
0
9

出力例2

10

「1 → + → 0 → + → 9」を計算すると 10 が得られ、これが最大値である。

入力例3

2
3
4

出力例3

24

「2 → × → 3 → × → 4」を計算すると 24 が得られ、これが最大値である。

入力例4

9
9
0

出力例4

81

「9 → × → 9 → + → 0」を計算すると 81 が得られ、これが最大値である。

問題文

ある国では「きつね派」と「うさぎ派」がその人気を競っています。あなたは「きつね派」の参謀として、今度行われる人気投票に勝つための策を考えています。

この国には N 個の地域があり、それぞれの地域で投票が行われます。それぞれの地域における総投票数と、そのうちの「きつね派」の得票数が与えられるので、「きつね派」が過半数の票を獲得した地域の個数を求めるプログラムを作成してください。

ただし、「過半数」とは半分よりも大きい数を表すので、たとえば総投票数が 100 のとき得票数が 50 でも過半数とは言わないことに注意してください。

入力例1

5
150 130 100 200 150
100 60 50 101 70

出力例1

2

1 番目の地域と 4 番目の地域で「きつね派」が過半数の票を獲得しているので 2 を出力します。

3 番目の地域では「きつね派」がちょうど総投票数の半分の票を獲得していますが、過半数には達していないので数えないことに注意してください。

入力例2

5
5 4 3 2 1
2 2 2 1 0

出力例2

1

3 番目の地域でのみ「きつね派」が過半数の票を獲得しています。

問題文

今、タコ星人の間で足ゲームというゲームが流行っています。足ゲームとは、N 個のボタンを T 秒の間の決められたタイミングで踏むとクリアすることが出来るというゲームです。ボタン i は A_i 秒ごとに 1 回踏まなければなりません。つまり、足ゲームをクリアするためには T 秒の間、ボタン i を開始から A_i 秒後、2 \times A_i 秒後、3 \times A_i 秒後・・・のタイミングで 1 回ずつ踏まなければなりません。

タコ星人は変身能力を持っていて、自分の足の本数を自由に変えることが出来ます。タコ星人が同じタイミングで X 個のボタンを踏むためには X 本の足が必要です。足ゲームをクリアするためには何本の足が必要となるでしょう。

入力例1

2 6
2
3

出力例1

2

この入力例では、

• ボタン 1 を、開始から 2 秒後と 4 秒後と 6 秒後のタイミング
• ボタン 2 を、開始から 3 秒後と 6 秒後のタイミング

で踏む必要があります。

開始から 6 秒後のタイミングでは 2 つのボタンを同時に踏む必要があるため、足は 2 本必要です。

入力例2

2 5
2
3

出力例2

1

入力例3

4 40
7
4
3
14

出力例3

3

問題文

縦の長さが R、横の長さが C であるような 2 次元グリッド盤面があります。盤面の最も左上のマスの座標は (1,1) で、最も右下のマスの座標は (R,C) です。

この盤面に以下の操作を N 回繰り返します。

• 盤面のある長方形区間に含まれる全てのセルを黒く塗る。具体的には、r,c,h,w が与えられるので、塗り始めの左上の座標を (r,c) として、そのマスを含めて縦幅 h マス、横幅 w マスであるような長方形区間に含まれる h×w 個のマスを全て黒く塗る。

黒いものが大好きなあなたは、今盤面上のある地点におり、別のある地点に黒いマスの上のみを辿ってたどり着きたいと思っています。あなたは、上下左右のいずれか近傍の 1 マスへの移動を自由に繰り返すことができます。盤面の外には出ることができません。

あなたのスタート地点のマスの座標 (r_s,c_s) とゴール地点のマスの座標 (r_g,c_g) といくつかの操作が与えられるので、スタート地点からゴール地点まで黒いマスの上だけを移動して、辿り着くことができるならば YES を出力し、辿りつけなかったりそもそもスタート地点やゴール地点がそもそも黒いマスでない場合は NO を出力してください。

入力例1

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

出力例1

YES

白いマスを .、黒いマスを # とすると、黒塗りの操作を施した後の盤面は、 以下の通りとなる。

.....
.####
....#
....#

さらに、スタート地点を S、ゴール地点を G とすると、以下のような位置関係となっている。

.....
.S...
....G
.....

入力例2

4 5
1 2
2 2
2
1 1 1 5
1 1 4 1

出力例2

NO

入力例3

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

出力例3

YES

入力例4

1 5
1 1
1 2
1
1 3 1 2

出力例4

NO

入力例5

1 5
1 3
1 2
1
1 3 1 2

出力例5

NO

入力例6

48 48
1 1
48 48
1
1 1 48 48

出力例6

YES

問題文

うなぎは太鼓ゲームに興じています。太鼓ゲームは、画面に表示される文字列に合わせて太鼓を叩くゲームです。表示されている文字列が S である場合は太鼓の中心を叩き、T である場合は太鼓のふちを叩きます。このゲームではいくつかの文字列が 1 列に表示され、それらの文字列に合わせて順番通りに太鼓を叩くとゲームをクリアできます。しかし、画面に表示されている文字列同士の間隔が狭すぎて、どこで文字列が区切られているのかが分かりません。

ゲームをクリアしたいうなぎは、画面に表示された文字列の正しい区切り方の個数を数えることにしました。ただし正しい区切り方とは、文字列を区切る方法であって、区切られた各部分の文字列が文字列 S または文字列 T と一致しているもののことを指します。

入力例1

dondonkatsudon
don
katsu

出力例1

1

don,don,katsu,don のように区切ることが出来ます。

また、それ以外の正しい区切り方は存在しません。

入力例2

aaaaa
aaa
aa

出力例2

2

aaa,aa のように区切る方法と、aa,aaa のように区切る方法の 2 通りが存在します。

入力例3

ffffffffffffffffffffffffffffffffffffffffffffffffffffffff
f
ff

出力例2

435293607

答えは非常に大きくなる可能性があるため、1,000,000,007 で割った余りを求めることを忘れないようにして下さい。

問題文

N 個の石が積まれた山があり、2 人のプレーヤーが交互にこの山からいくつかの石をとっていくゲームを考えます。最後の石をとったプレーヤーが勝利とし、とれる石の個数は以下のようにして決まります。

一番最初に先手が石をとるときは 1 個以上 P 個以下の好きな個数だけ石をとれます。それ以降については、各プレーヤーは 1 個以上、直前にとられた石の個数 + 1 個以下の好きな個数だけ石をとれます。

たとえば、最初に先手が石を 3 個とると、次に後手は 1 個以上 4 個以下の石をとることができます。そこで後手が 2 個の石をとったとすると、次に先手は 1 個以上 3 個以下の石をとることができます。

N と P が決まっていれば、先手か後手のどちらかに必勝法があります。N と P が与えられるので、先手と後手のどちらが必勝であるかを判定するプログラムを作成してください。

入力例1

4
2

出力例1

first

最初に先手が石を 1 個とります。すると次に後手は 1 個か 2 個の石をとることができますが、どちらの場合でもその次に先手が残った石をすべてとることができます。

したがってこの場合は先手必勝です。

入力例2

5
2

出力例2

second

最初に先手が石を 2 個とると、次に後手に残った 3 個の石をとられて負けてしまいます。

最初に先手が石を 1 個とったとします。このとき、次に後手が 1 個の石をとると残りの石は 3 個になります。この状態から次に先手が石を 1 個とっても 2 個とっても、後手が残った石をすべてとることができます。

したがってこの場合は後手必勝です。

入力例3

100
100

出力例3

first

最初の一手ですべての石をとることができます。

入力例4

100
19

出力例4

second

問題文

あなたは最近、ほんの少し特殊なしりとりゲームにハマっており、いくつかの英単語(注)が含まれる「しりとり基本セット」を購入しました。

しりとりゲームのルールは以下の通りです。

• しりとりゲームでの発言に用いることのできる単語を予め決めておき、それ以外の単語は発言に用いることができないものとする。 ただし、英単語を用いる際、それを反転させたものを代わりに発言してもよい。
• 一度用いた英単語は今後使用できない(反転したものを発言した場合も、元の単語は使用できなくなる)。
• 初回は、自由に英単語を選んで発言する。
• 2 回目以降に発言する英単語は、その先頭文字と直前の発言の末尾文字が一致していなければならない。
• 発言しようとしたときに、条件を満たす英単語が存在しなかった場合、その場でしりとりは終了する。

普通、しりとりは複数人でプレイするものですが、孤独を好むあなたは全ての英単語を余すことなく一回のしりとりゲームで使用しゲームを終えることを目標に、一人遊びを行おうと思っています。 しかし、賢いあなたは「しりとり基本セット」に含まれる英単語だけではどう頑張っても目標を達成できない可能性があることに気づきました。

そこで、追加の英単語をいくつか単品で購入して、それらと「しりとり基本セット」に含まれる英単語のみを用いてしりとりゲームを行い、目標を達成することとしました。あなたが購入しなければならない英単語の最小数を答えてください。

あなたが住んでいる世界では、幸運なことに任意の英単語が潤沢な数売られており、必要な数だけ購入することができます。

(注) ここでいう英単語とは、アルファベット小文字(a-z)のみから構成される 長さ 2 ～ 20 の文字列のことを指すとします。実際の英単語の定義とはかけ離れていることに注意してください。

入力例1

3
soup
peas
ecir

出力例1

1

「しりとり基本セット」に含まれる英単語だけでは、それらを余すことなく使用し尽くすことはできません。

そこで、例えば単語 sugar を買うことによって、「soup→peas→sugar→rice」 (最後の rice は ecir を反転したもの)というように、全ての単語を使ってしりとりゲームを終えることができ、目標を達成できます。

入力例2

4
ba
bc
ca
da

出力例2

0

一例として、「ab→bc→ca→ad」というようにしりとりゲームを行えば、英単語追加購入する必要はありません。この例では、ba と da を反転して使っています。

入力例3

13
ab
cd
ef
gh
ij
kl
mn
op
qr
st
uv
wx
yz

出力例3

12

入力例4

3
aa
xyz
zwx

出力例4

1