Time Limit: 2 sec / Memory Limit: 256 MB
問題文
清々しい朝だ。今日の CODE THANKS FESTIVAL は目一杯楽しむぞ。そのためにも朝ごはんをしっかりと食べないといけない。
コーヒーを淹れるのには A 分かかり、トーストを焼くのには B 分かかる。両方の準備を同時に始めたとして、朝食の準備が完了するのは何分後になるだろうか?
入力
入力は以下の形式で標準入力から与えられる。
A B
- 1 行目には、2 つの整数 A (1 ≦ A ≦ 60), B (1 ≦ B ≦ 60) が空白区切りで与えられる。これは、コーヒーを淹れるのに A 分、トーストを焼くのに B 分かかることを表す。
出力
朝食の準備が完了するまでの時間 (分単位) を 1 行に出力せよ。
出力の末尾には改行を入れること。
入力例1
10 5
出力例1
10
このケースではコーヒーを淹れるのに 10 分、トーストを焼くのに 5 分かかります。同時にコーヒーとトーストの準備を始めると、開始から 5 分後にトーストが焼き上がり、10 分後にコーヒーを淹れ終わります。したがって 10 を出力します。
入力例2
42 42
出力例2
42
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
あなたが持っている電卓には、足し算(+)と掛け算(×)の、2 つの演算子が存在します。
あなたには、 3 つの数字 A,B,C が与えられます。 これらの数字を電卓に、「A → 演算子 → B → 演算子 → C」の順番で入力します。
たとえば、(A,B,C)=(1,2,3) のとき、最初の演算を足し算、次の演算の演算を掛け算とすることを考えます。 この場合、入力は「1 → + → 2 → × → 3」であり、計算結果は 9 です。電卓は順番に演算を行うため、演算子の優先順位は無視して左から計算します。
あなたは、各数字の間に入れる演算をうまく定めて最大値を得る一人遊びを行うことにしました。 各数字の間に入れる演算をうまく選ぶことによって得られる計算結果の最大値を求めて下さい。
入力
入力は以下の形式で標準入力から与えられる。
A B C
- 1 行目には、数字 A (0 ≦ A ≦ 9) が与えられる。
- 2 行目には、数字 B (0 ≦ B ≦ 9) が与えられる。
- 3 行目には、数字 C (0 ≦ C ≦ 9) が与えられる。
出力
1 行目に、計算結果の最大値を出力せよ。末尾の改行を忘れないこと。
入力例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 が得られ、これが最大値である。
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
ある国では「きつね派」と「うさぎ派」がその人気を競っています。あなたは「きつね派」の参謀として、今度行われる人気投票に勝つための策を考えています。
この国には N 個の地域があり、それぞれの地域で投票が行われます。それぞれの地域における総投票数と、そのうちの「きつね派」の得票数が与えられるので、「きつね派」が過半数の票を獲得した地域の個数を求めるプログラムを作成してください。
ただし、「過半数」とは半分よりも大きい数を表すので、たとえば総投票数が 100 のとき得票数が 50 でも過半数とは言わないことに注意してください。
入力
入力は以下の形式で標準入力から与えられる。
N V_1 V_2 ... V_N F_1 F_2 ... F_N
- 1 行目には整数 N (1 ≦ N ≦ 100) が与えられる。これは地域の個数を表す。
- 2 行目には N 個の整数が空白区切りで与えられる。このうち i (1 ≦ i ≦ N) 個目の数 V_i (1 ≦ V_i ≦ 1,000) は、i 番目の地域における総投票数を表す。
- 3 行目には N 個の整数が空白区切りで与えられる。このうち i (1 ≦ i ≦ N) 個目の数 F_i (0 ≦ F_i ≦ V_i) は、i 番目の地域における「きつね派」の得票数を表す。
出力
「きつね派」が過半数の投票を獲得した地域の個数を 1 行に出力せよ。
出力の末尾には改行を入れること。
入力例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 番目の地域でのみ「きつね派」が過半数の票を獲得しています。
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
今、タコ星人の間で足ゲームというゲームが流行っています。足ゲームとは、N 個のボタンを T 秒の間の決められたタイミングで踏むとクリアすることが出来るというゲームです。ボタン i は A_i 秒ごとに 1 回踏まなければなりません。つまり、足ゲームをクリアするためには T 秒の間、ボタン i を開始から A_i 秒後、2 \times A_i 秒後、3 \times A_i 秒後・・・のタイミングで 1 回ずつ踏まなければなりません。
タコ星人は変身能力を持っていて、自分の足の本数を自由に変えることが出来ます。タコ星人が同じタイミングで X 個のボタンを踏むためには X 本の足が必要です。足ゲームをクリアするためには何本の足が必要となるでしょう。
入力
入力は以下の形式で標準入力から与えられる。
N T A_1 A_2 : A_N
- 1 行目には、足ゲームのボタンの個数を表す整数 N (1 ≦ N ≦ 1000) と、足ゲームのプレイ時間を表す整数 T (1 ≦ T ≦ 1000) が空白区切りで与えられる。
- 2 行目からの N 行では、各ボタンを踏むタイミングの情報が与えられる。このうち i 行目には、ボタン i を踏む間隔を表す整数 A_i (1 ≦ A_i ≦ T) が与えられる。
出力
タコ星人が足ゲームをクリアするために必要な足の本数を表す 1 つの整数を 1 行に出力せよ。また、出力の末尾には改行を入れること。
入力例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
Time Limit: 2 sec / Memory Limit: 256 MB
(14:47更新) オープン参加者の解答のリジャッジも完了しました.
12:34以降に提出された解答に対するテストケースは正しいものとなっています.
問題文
縦の長さが 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
を出力してください。
入力
入力は以下の形式で標準入力から与えられる。
R C r_s c_s r_g c_g N r_1 c_1 h_1 w_1 r_2 c_2 h_2 w_2 : r_N c_N h_N w_N
- 1 行目には、盤面の縦の長さと横の長さをそれぞれ表す整数 R,C (1 ≦ R,C ≦ 48) が与えられる。
- 2 行目には、スタート地点のマスの座標を表す 2 つの整数 r_s (1≦ r_s ≦ R) と c_s (1≦ c_s ≦ C) が与えられる。
- 3 行目には、ゴール地点のマスの座標を表す 2 つの整数 r_g (1≦ r_g ≦ R) と c_g (1≦ c_g ≦ C) が与えられる。
- 4 行目には、操作回数を表す整数 N (1 ≦ N ≦ 1000) が与えられる。
- 5 行目から N 行には、長方形の情報が与えられる。そのうち i 行目には、 i 番目の長方形の r,c,h,w を表す 4 つの整数 r_i (1≦ r_i ≦ R),c_i (1≦ c_i ≦ C),h_i (1≦ r_i+h_i-1 ≦ R),w_i (1≦ c_i+w_i-1 ≦ C) が与えられる。
- スタート地点とゴール地点は必ず異なる。つまり、(r_s,c_s)≠(r_g,c_g) が成り立つ。
出力
1 行目に、問題文の要求にしたがって 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
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
うなぎは太鼓ゲームに興じています。太鼓ゲームは、画面に表示される文字列に合わせて太鼓を叩くゲームです。表示されている文字列が S である場合は太鼓の中心を叩き、T である場合は太鼓のふちを叩きます。このゲームではいくつかの文字列が 1 列に表示され、それらの文字列に合わせて順番通りに太鼓を叩くとゲームをクリアできます。しかし、画面に表示されている文字列同士の間隔が狭すぎて、どこで文字列が区切られているのかが分かりません。
ゲームをクリアしたいうなぎは、画面に表示された文字列の正しい区切り方の個数を数えることにしました。ただし正しい区切り方とは、文字列を区切る方法であって、区切られた各部分の文字列が文字列 S または文字列 T と一致しているもののことを指します。
入力
入力は以下の形式で標準入力から与えられる。
X S T
- 1 行目には、画面に表示されている文字列 X (1 ≦ |X| ≦ 1000) が与えられる。ただし、|X| は文字列 X の長さを表すものとします。
- 2 行目には、太鼓の中心を叩くことを指示する文字列 S (1 ≦ |S| ≦ |X|) が与えられる。
- 3 行目には、太鼓のふちを叩くことを指示する文字列 T (1 ≦ |T| ≦ |X|, S \neq T) が与えられる。
- 入力される文字列は全てアルファベット小文字(
a
-z
)のみから構成される。 - 画面に表示された文字列の正しい区切り方は 1 通り以上存在することが保証されている。
出力
画面に表示された文字列の正しい区切り方の個数を 1,000,000,007 (10^9+7) で割った余りを 1 行に出力せよ。また、出力の末尾には改行を入れること。
入力例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 で割った余りを求めることを忘れないようにして下さい。
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
N 個の石が積まれた山があり、2 人のプレーヤーが交互にこの山からいくつかの石をとっていくゲームを考えます。最後の石をとったプレーヤーが勝利とし、とれる石の個数は以下のようにして決まります。
一番最初に先手が石をとるときは 1 個以上 P 個以下の好きな個数だけ石をとれます。それ以降については、各プレーヤーは 1 個以上、直前にとられた石の個数 + 1 個以下の好きな個数だけ石をとれます。
たとえば、最初に先手が石を 3 個とると、次に後手は 1 個以上 4 個以下の石をとることができます。そこで後手が 2 個の石をとったとすると、次に先手は 1 個以上 3 個以下の石をとることができます。
N と P が決まっていれば、先手か後手のどちらかに必勝法があります。N と P が与えられるので、先手と後手のどちらが必勝であるかを判定するプログラムを作成してください。
入力
入力は以下の形式で標準入力から与えられる。
N P
- 1 行目には整数 N (1 ≦ N ≦ 500) が与えられる。これは N 個の石がある状態からゲームを始めることを表す。
- 2 行目には整数 P (1 ≦ P ≦ N) が与えられる。これは一番最初に先手が P 個まで石をとってよいことを表す。
出力
先手必勝ならば first
と、後手必勝ならば second
と 1 行に出力せよ。
出力の末尾には改行を入れること。
入力例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
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
あなたは最近、ほんの少し特殊なしりとりゲームにハマっており、いくつかの英単語(注)が含まれる「しりとり基本セット」を購入しました。
しりとりゲームのルールは以下の通りです。
- しりとりゲームでの発言に用いることのできる単語を予め決めておき、それ以外の単語は発言に用いることができないものとする。 ただし、英単語を用いる際、それを反転させたものを代わりに発言してもよい。
- 一度用いた英単語は今後使用できない(反転したものを発言した場合も、元の単語は使用できなくなる)。
- 初回は、自由に英単語を選んで発言する。
- 2 回目以降に発言する英単語は、その先頭文字と直前の発言の末尾文字が一致していなければならない。
- 発言しようとしたときに、条件を満たす英単語が存在しなかった場合、その場でしりとりは終了する。
普通、しりとりは複数人でプレイするものですが、孤独を好むあなたは全ての英単語を余すことなく一回のしりとりゲームで使用しゲームを終えることを目標に、一人遊びを行おうと思っています。 しかし、賢いあなたは「しりとり基本セット」に含まれる英単語だけではどう頑張っても目標を達成できない可能性があることに気づきました。
そこで、追加の英単語をいくつか単品で購入して、それらと「しりとり基本セット」に含まれる英単語のみを用いてしりとりゲームを行い、目標を達成することとしました。あなたが購入しなければならない英単語の最小数を答えてください。
あなたが住んでいる世界では、幸運なことに任意の英単語が潤沢な数売られており、必要な数だけ購入することができます。
(注) ここでいう英単語とは、アルファベット小文字(a
-z
)のみから構成される 長さ 2 ~ 20 の文字列のことを指すとします。実際の英単語の定義とはかけ離れていることに注意してください。
入力
入力は以下の形式で標準入力から与えられる。
N w_1 w_2 : w_N
- 1 行目には、「しりとり基本セット」に含まれる英単語の数 N (1 ≦ N ≦ 100,000) が与えられる。
- 2 行目から N 行には、「しりとり基本セット」に含まれる英単語の情報が与えられる。そのうち i 行目には、i 番目の英単語を表す w_i (2 ≦ |w_i| ≦ 20) が書かれている。 w_i はアルファベット小文字(
a
-z
)のみから構成される。 - 全ての単語は互いに異なることが保障されている。また、ある単語を反転させたものが別の単語と一致することがないことも保障されている。
出力
1 行目に、あなたが購入しなければならない英単語の最小数を出力せよ。末尾の改行を忘れないこと。
入力例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