A - カメツル算

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

カメには足が 4 本、ツルには足が 2 本あります。

カメが A 匹、ツルが B 羽いるとき、足は合計で何本あるでしょうか。

入力

入力は以下の形式で標準入力から与えられる。

A B
  • 1 行目には、2 つの整数 A (1 ≦ A ≦ 1000), B (1 ≦ B ≦ 1000) が空白区切りで与えられる。これは、カメが A 匹、ツルが B 羽いるということを表す。

出力

足の本数の合計を 1 行に出力せよ。

入力例1

20 14

出力例1

108

カメの足の本数の合計は 4 \times 20 = 80 本で、ツルの足の本数の合計は 2 \times 14 = 28 本なので、合わせて 108 本となります。

入力例2

296 415

出力例2

2014
B - バッジ

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

ある会社ではコンテスト参加者への景品としてバッジを配ることになりました。

見積もりによるとバッジが N 個必要です。

ある会社はバッジ製作機を 3 個持っており、A, B, C という名前が付けられています。

A, B, C は 1 分動かすと、ちょうど 1 分後にそれぞれ A 個、B 個、C 個のバッジを生産します。

この機械は 1 分単位でしか動かすことができず、秒単位で動かす (例えば機械 A を 30 秒動かしてバッジ A/2 個作る) ことはできません。

これらの製作機は 1 分稼働させると、2 分は放熱(待機)させる必要があるため、ある会社では 3 つの機械を順繰りに使用することにしました。例えば、機械 A → 機械 B → 機械 C → 機械 A → 機械 B → 機械 C → 機械 A → ... という順番や、機械 B → 機械 A → 機械 C → 機械 B → 機械 A → 機械 C → 機械 B → ... などの順番で動かします。

コンテスト開催まであまり時間がないので、できるだけ早くバッジを集めたいと考えています。うまく順番を選んだときに、N 個以上バッジが出来上がるまでにかかる時間の最小値を計算するプログラムを作成してください。

入力

入力は以下の形式で標準入力から与えられる。

N
A
B
C
  • 1 行目には、必要なバッジの個数 N (1 ≦ N ≦ 1,000) が与えられる。
  • 2 行目には、機械 A が 1 分間で作成するバッジの個数 A (1 ≦ A ≦ 1,000) が与えられる。
  • 3 行目には、機械 B が 1 分間で作成するバッジの個数 B (1 ≦ B ≦ 1,000) が与えられる。
  • 4 行目には、機械 C が 1 分間で作成するバッジの個数 C (1 ≦ C ≦ 1,000) が与えられる。

出力

バッジを N 個以上製作するのにかかる時間の最小値を 1 行に出力せよ。出力の末尾にも改行を入れること。

入力例1

26
5
2
3

出力例1

8

機械 A → 機械 B → 機械 C → 機械 A → 機械 B →機械 C → 機械 A → 機械 B という手順で動かすことにより 8 分で 26 個以上バッジを製作することができます。

時間 1 2 3 4 5 6 7 8
動かす機械の名前 A B C A B C A B
動かす機械の生産量 5 2 3 5 2 3 5 2
累積のバッジ数 5 7 10 15 17 20 25 27

入力例2

6
2
3
4

出力例2

2

必ずしもすべての機械を稼働させる必要はありません。

入力例3

450
3
7
19

出力例3

46
C - コンテスト

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

うさぎは N 問の問題が出題されるプログラミングコンテストに参加し、M 問の問題に正解しました。

うさぎは、各問題の配点と自分が正解した問題のリストから自分の得点を計算してみることにしました。

入力

入力は以下の形式で標準入力から与えられる。

N M
P_1 P_2 ... P_N
S_1 S_2 ... S_M
  • 1 行目には、コンテストに出題された問題数を表す整数 N (1 ≦ N ≦ 100) と、うさぎが解いた問題数を表す整数 M (1 ≦ M ≦ 100) が空白区切りで与えられる。
  • 2 行目には、各問題の配点を表す N 個の整数が空白区切りで与えられる。このうち i 番目の整数 P_i (1 ≦ P_i ≦ 100) は、i 番目の問題を正解した時に得られる得点を表す。
  • 3 行目には、うさぎが正解した問題の情報を表す M 個の整数が空白区切りで与えられる。このうち i 番目の整数 S_i (1 ≦ S_i ≦ N) は、うさぎが S_i 番目の問題を正解したことを表す。ただし、S は昇順に並んでいることが保証される。すなわち、全ての i, j (i < j) に対して S_i < S_j が成り立つ。

出力

うさぎの合計得点を 1 行に出力せよ。

入力例1

5 3
100 1 20 14 50
1 2 5

出力例1

151

この入力例では、うさぎは 1 番と 2 番と 5 番の問題に正解しています。1 番の問題の得点は 100 点、2 番の問題の得点は 1 点、5 番の問題の得点は 50 点なので、合計得点は 151 点となります。

入力例2

8 8
100 100 100 100 100 100 100 100
1 2 3 4 5 6 7 8

出力例2

800

この入力例では、うさぎは全ての問題に正解しています。

D - 定期券

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

あなたの勤める鉄道会社の路線には一直線に並んだ N 個の駅があり、駅には 1 から N までの異なる整数の番号がついています。より具体的には、駅 1、駅 2、……、駅 N-1、駅 N の順で駅が並んでいて、隣り合う駅の間に線路が引かれています。

この路線では従来は複雑な運賃計算方法を使っていましたが、乗客から運賃に関する質問が絶えないので、運賃計算を簡単にするために 1 駅ぶん移動するごとに 100 円の運賃がかかるという単純な運賃計算を導入することにしました。たとえば、駅 2 から駅 6 へ行くのには 400 円かかります。

ただし、定期券を持っている場合には運賃計算の際に定期券も考慮する必要があります。駅 a から駅 b までの定期券を持っている場合、その間にある駅どうしで移動するぶんの運賃はかかりません。たとえば、駅 3 から駅 5 までの定期券を持っているとき

  • 駅 2 から駅 6 へ行くのには 200 円かかります。
    • 駅 2 から駅 3 への移動と、駅 5 から駅 6 への移動は定期券の圏外なのでそれぞれ 100 円がかかります。
    • 一方、駅 3 から駅 4、駅 4 から駅 5 への移動は定期券の圏内なので運賃はかかりません。
  • 駅 3 から駅 4 へ行くのには運賃はかかりません。
  • 駅 7 から駅 10 へ行くのには 300 円かかります。

さて、せっかく運賃計算方法を単純にしたのに、いまだ乗客からの運賃に関する質問は減る様子を見せません。あなたは、これぐらい単純なルールであれば、プログラムで質問に答えられるのではないかと考えました。「駅 a から駅 b までの定期券を持っている人が、駅 s から駅 t へ行くときにかかる運賃は何円か？」という形式の質問に答えるプログラムを作成してください。

入力

N Q
a_1 b_1 s_1 t_1
a_2 b_2 s_2 t_2
:
a_Q b_Q s_Q t_Q
  • 1 行目には、駅の数を表す整数 N (2 ≦ N ≦ 10^5) と、運賃に関する質問の数を表す整数 Q (1 ≦ Q ≦ 10^5) が書かれている。
  • 2 行目から Q 行にわたって、各行に運賃に関する質問の情報が書かれている。このうち i (1 ≦ i ≦ Q) 行目には i 番目の質問を表す 4 つの整数 a_i, b_i (1 ≦ a_i < b_i ≦ N), s_i, t_i (1 ≦ s_i < t_i ≦ N) が書かれている。これは i 番目の質問が「駅 a_i から駅 b_i までの定期券を持っている人が、駅 s_i から駅 t_i へ行くときにかかる運賃は何円か？」であることを表す。

出力

Q 行出力せよ。i (1 ≦ i ≦ Q) 行目に、i 番目の質問に対する答えを表す整数を出力せよ。

入力例1

10 3
3 5 2 6
3 5 3 4
3 5 7 10

出力例1

200
0
300

この入出力例は問題文中で説明されている例です。

入力例2

100000 5
30000 50000 12345 67890
50000 50001 50000 50002
1 100000 9384 99384
1 2 3 100000
48592 84911 58124 91852

出力例2

3554500
100
0
9999700
694100
E - 儀式

Time Limit: 5 sec / Memory Limit: 256 MB

問題文

ある神殿では毎年、年越しの儀式が行われます。

儀式には R × C 個の石像を用います。石像は縦 (南北方向) に R 行、横 (東西方向) に C 列並んでおり、北西端にある石像を起点として、南に i-1 (1 ≦ i ≦ R) 個、東に j-1 (1 ≦ j ≦ C) 個だけ進んだ場所にある石像を石像 (i,j) と呼ぶことにします。最初、どの石像も南を向いています。

儀式は N 回の手順からなり、それらのうち s (1 ≦ s ≦ N) 回目の手順は以下のようになります。

  • 手順 s : r_{a,s} ≦ u ≦ r_{b,s} および c_{a,s} ≦ v ≦ c_{b,s} を満たすすべての整数組 (u,v) について、石像 (u,v) を左に 90 度回転させる。

例年はこの手順を N 回行いますが、今年はある 1 つの手順を忘れてしまっていて、最終結果がいつもと異なるものになってしまいました。

それぞれの手順は重要な意味を持っているのでこのままでは大変なことになってしまいます。

さらに困ったことに、N - 1 回の終了時のそれぞれの石像の向きは記録していませんでした。ただ、幸いなことに終了時に南を向いていた石像の個数が M 個であることがわかりました。

神殿内の会議で、忘れてしまった手順を列挙するプログラムを作成することにしましたが、この神殿にはプログラマーはいませんでした。あなたの課題は、儀式で忘れてしまった手順を列挙するプログラムを作成することです。

入力

入力は以下の形式で標準入力から与えられる。

R C M
N
r_{a,1} r_{b,1} c_{a,1} c_{b,1}
r_{a,2} r_{b,2} c_{a,2} c_{b,2}
:
r_{a,N} r_{b,N} c_{a,N} c_{b,N}
  • 1 行目には、石像群の行数 R (1 ≦ R ≦ 50)、列数 C (1 ≦ C ≦ 50) および終了時点で南を向いていた石像の個数 M (0 ≦ M ≦ R × C) が空白区切りで与えられる。
  • 2 行目には、手順の個数 N (1 ≦ N ≦ 5,000) が与えられる。
  • 3 行目から N 行には、各手順に関する情報が与えられる。このうち i (1 ≦ i ≦ N) 行目には 4 つの整数 r_{a,i}, r_{b,i} (1 ≦ r_{a,i} ≦ r_{b,i} ≦ R), c_{a,i}, c_{b,i} (1 ≦ c_{a,i} ≦ c_{b,i} ≦ C) が空白区切りで与えられる。これは、手順 i が r_{a,i} ≦ u ≦ r_{b,i} および c_{a,i} ≦ v ≦ c_{b,i} を満たすすべての整数組 (u,v) について、石像 (u,v) を左に 90 度回転させる手順であることを表す。
  • どの入力についても、少なくとも 1 つの手順は忘れた可能性がある (すなわち、解が少なくとも 1 つは存在する)。

出力

儀式で忘れてしまった手順が昇順に 手順 f_1、手順 f_2、 ... 、手順 f_m であるとしたとき、m 行にわたって出力せよ。m 行のうち l (1 ≦ l ≦ m) 行目には、整数 f_l を出力せよ。出力の末尾にも改行を入れること。

入力例1

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

出力例1

2
6

初期状態では、すべての像の向きは下表のようになっています。

南 南 南 南 南
南 南 南 南 南
南 南 南 南 南

例えば、手順 2 を忘れた場合の挙動は以下のようになります。

手順 1 の後、それぞれの像は

南 東 東 東 東
南 東 東 東 東
南 東 東 東 東

となります。

手順 3 の後、それぞれの像は

東 北 北 北 東
東 北 北 北 東
東 北 北 北 東

となります。

手順 4 の後、それぞれの像は

東 北 北 北 東
東 西 西 西 北
東 西 西 西 北

となります。

手順 5 の後、それぞれの像は

東 北 西 西 北
東 西 南 南 西
東 西 西 西 北

となります。

手順 6 の後、それぞれの像は

東 北 西 南 西
東 西 南 東 南
東 西 西 西 北

となります。

結果として南向きの石像が 3 個となるので、手順 2 は忘れた可能性があります。

この例の場合、他にも手順 6 を忘れた可能性があり、他の場合は個数が矛盾するので、1 行目に 2 を、2 行目に 6 を出力します。

入力例2

4 4 8
9
1 4 1 4
1 4 1 4
1 4 1 1
1 4 3 3
1 2 1 2
1 2 3 4
3 4 1 2
3 4 3 4
1 4 1 4

出力例2

1
2
5
6
7
8
9
F - 順位表

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

高橋君は N 人の参加者が参加するプログラミングコンテストに参加しました。各参加者には 1 から N までの番号が振られており、高橋君は参加者 1 でした。

このコンテストでは順位表を見ることが出来なかったため、高橋君は自分の順位が分かりません。高橋君はコンテスト後の懇親会で「参加者 A_i は参加者 B_i よりも順位が高い」という情報を M 個入手しました。高橋君はこの情報をもとに、自分の順位として考えられるもののうち最も高いものを計算してみることにしました。ただし、最も高い順位は 1 位で、最も低い順位は N 位です。また、同順位に 2 人以上の参加者がいることはありません。

入力

入力は以下の形式で標準入力から与えられる。

N M
A_1 B_1
A_2 B_2
:
A_M B_M
  • 1 行目には、コンテストの参加者の人数を表す整数 N (2 ≦ N ≦ 50) と 高橋君が得た情報の個数を表す整数 M (1 ≦ M ≦ 50) が空白区切りで与えられる。
  • 2 行目からの M 行では、高橋君が得た情報が与えられる。このうち i 行目には、i 番目の情報を表す 2 つの整数 A_i, B_i (1 ≦ A_i ≦ N, 1 ≦ B_i ≦ N, A_i \neq B_i) が空白区切りで与えられる。これは、参加者 A_i が参加者 B_i よりも順位が高かったという情報を表す。
  • 矛盾するような情報が与えられないこと、同じ情報が 2 回以上与えられないことが保証される。

出力

高橋君、すなわち参加者 1 の順位として考えられるもののうち最も高い順位を表す 1 つの整数を 1 行に出力せよ。

入力例1

5 3
2 1
3 2
1 5

出力例1

3

3 つの情報はそれぞれ、

  • 参加者 2 は参加者 1 よりも順位が高い。
  • 参加者 3 は参加者 2 よりも順位が高い。
  • 参加者 1 は参加者 5 よりも順位が高い。

です。順位表としては以下のようなものが考えられます。

  • 1 位：参加者 3
  • 2 位：参加者 2
  • 3 位：参加者 1
  • 4 位：参加者 4
  • 5 位：参加者 5

この場合、参加者 1 である高橋君は 3 位です。 また、高橋君が 2 位以上である順位表は存在しないため、3 を出力します。

入力例2

3 2
2 1
2 3

出力例2

2

入力例3

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

出力例3

5
G - 通勤電車と気分

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

私は通勤電車のエキスパートである。今日も駅のホームで電車を待っているところだ。待っている電車はこの駅が始発なので、席はすべて空いているが、自分より前に N 人の人が列をなしているので座れるかどうかは分からない。

車両には K 個の席が一直線に並んでおり、それぞれ席 1 から席 K までの連続する整数の番号がふられている。席の数と自分の前に並んでいる人数が分かれば、座れるかどうかが分かるのではないかと思われるかもしれないが、ことはそう単純ではないのである。

人はその日の気分によって座る席をどのように選ぶかが変わるということを私は知っている。具体的には、ある日の気分は次の 2 通りである。

  • 「とにかく座りたい気分」 : この気分の人は、空いている席がひとつでもあれば、そのうち番号が最も小さい席に座る。
  • 「余裕があれば座りたい気分」 : この気分の人は、空いている席のなかで、両隣の席も空いているようなものがあれば、そのうち番号が最も小さい席に座る。なお、隣の席が存在しない場合も、隣の席が空いていると見做してよい。

いずれの気分のときでも、座る条件を満たす席がない場合は席に座るのを諦める。

さて、いま私の前に並んでいる人たちを先頭から順に人 1, 人 2, ……, 人 N と番号づけることにする。つまり、まず人 1 が車両に入り、その日の気分に従って席を選ぶ。次に人 2 が車両に入り、その日の気分に従って席を選ぶ。これを繰り返して人 N が車両に入り、席を選び終えたらようやく私が車両に入る。

私の見立てでは、人 i は p_i パーセントの確率で「とにかく座りたい気分」になり、100 - p_i パーセントの確率で「余裕があれば座りたい気分」になる。この仮定のもとで、人 N までが車両に入って席を選び終えたとき、つまり、私が車両に入ったときに空いている席の個数の期待値がいくつになるかを計算したい。

入力

N K
p_1
p_2
:
p_N
  • 1 行目には、列に並んでいる人数を表す整数 N (1 ≦ N ≦ 100) と、車両にある席の個数を表す整数 K (1 ≦ K ≦ 200) が書かれている。
  • 2 行目から N 行にわたって、それぞれの人の情報が与えられる。このうち i 行目には、人 i が「とにかく座りたい気分」になる確率を表す整数 p_i (0 ≦ p_i ≦ 100) が書かれている。

部分点

この問題には部分点が設定されています。

  • N ≦ 10 を満たすデータセットにすべて正解すると 30 点が得られます。
  • すべてのデータセットに正解すると、上に加えてさらに 70 点が得られ、全体で 100 点が得られます。

出力

人 N が車両に入り席を選び終えた時点での、空いている席の個数の期待値を表す実数を 1 行に出力せよ。真の値との絶対誤差または相対誤差が 10^{-6} 以下であれば正答とみなす。

入力例1

3 4
100
30
60

出力例1

1.28

人 1 は常に「とにかく座りたい気分」なので、人 2, 3 の気分について考えると

  • 人 2, 3 の両方が「とにかく座りたい気分」になる確率は 0.3 \times 0.6 = 0.18 で、空席は 1 個になります。
  • 人 2 は「とにかく座りたい気分」だが人 3 は「余裕があれば座りたい気分」になる確率は 0.3 \times 0.4 = 0.12 で、空席は 1 個になります。
  • 人 2 は「余裕があれば座りたい気分」だが人 3 は「とにかく座りたい気分」になる確率は 0.7 \times 0.6 = 0.42 で、空席は 1 個になります。
  • 人 2, 3 の両方が「余裕があれば座りたい気分」になる確率は 0.7 \times 0.4 = 0.28 で、空席は 2 個になります。

したがって、空いている席の個数の期待値は 1 \times 0.18 + 1 \times 0.12 + 1 \times 0.42 + 2 \times 0.28 = 1.28 となります。

入力例2

5 7
28
31
59
61
30

出力例2

2.11193

入力例3

10 10
97
98
99
98
97
96
97
98
99
98

出力例3

0.020237732
H - 模様替え

Time Limit: 8 sec / Memory Limit: 256 MB

問題文

12 月に入り、2014 年もそろそろ終わりを迎えようとしています。そこで、気分を一新するために壁紙の模様替えをして 2015 年を迎えることにしました。

手元に縦 R 行横 C 列の生地があったので、その生地を必要ならば一部を切り出して壁紙のデザインにすることにしました。

生地からデザインを切り出すとき、必ずマス目に沿って切らなければならず、かつデザインは長方形の形状をしていなければなりません。

生地を構成する各マスはそれぞれただ 1 つの色で塗られています。

実は毎年面白いデザインを追求しているので、今年も面白いデザインとして「点対称なデザイン」であるような型紙を作ることにしました。

デザインが「点対称なデザイン」であるとは、デザインの大きさを縦 H 行、横 W 列としたとき、

  • H ≧ 2 および W ≧ 2 を満たす。
  • すべての整数 i,j (1 ≦ i ≦ H, 1 ≦ j ≦ W) について、デザインの上から i 番目、左から j 番目のマスの色 c_{i,j} が、デザインの上から H-i+1 番目、左から W-j+1 番目のマスの色 c_{H-i+1,W-j+1} と等しい。

である場合のことを指すこととします。

生地の場所によって、色以外にも様々な興味深い点があるので、縦横の大きさおよび色の配置が全く同じでも、切り出す元の場所が異なれば別のデザインとなります。そして、生地に対して「点対称なデザイン」であるデザインを 1 つ切り出す方法が全部で何通りあるか知りたいと思っています。

入力

入力は以下の形式で標準入力から与えられる。

R C
s_1
s_2
:
s_R
  • 1 行目には、生地の行数 R (1 ≦ R ≦ 250) および列数 C (1 ≦ C ≦ 250) が空白区切りで与えられる。
  • 2 行目から R 行には、生地の配色に関する情報が与えられる。このうち i (1 ≦ i ≦ R) 行目には長さ C の文字列 s_i が与えられる。s_i は半角小文字英字のみで構成されており、左から j (1 ≦ j ≦ C) 文字目は、生地の上から i 番目、左から j 番目のマスの色を表す。
  • 異なる 2 つのマスについて、上記の色を表す文字が同じなら同じ色で、異なるなら異なる色で塗られていることを表す。

部分点

この問題には部分点が設定されています。

  • R ≦ 20 および C ≦ 20 を満たすデータセット 1 にすべて正解すると、15 点が得られます。
  • R ≦ 100 および C ≦ 100 を満たすデータセット 2 にすべて正解すると、上記に加えてさらに 30 点が得られます。
  • 追加制約のないデータセット 3 にすべて正解すると、上記に 2 つに加えてさらに 55 点が得られ、全体で 100 点が得られます。

出力

「点対称なデザイン」であるデザインの個数を 1 行に出力せよ。出力の末尾にも改行を入れること。

入力例1

2 10
codethanks
documentsk

出力例1

2

生地の配色は下表のようになっています。

c o d e t h a n k s
d o c u m e n t s k

例えば、上から 1 番目、左から 1 番目のマスを左上端、上から 2 番目、左から 3 番目のマスを右下端とした縦 2 行横 3 列の領域を切り出すと、

c o d
d o c

となり、「点対称なデザイン」が切り出せます。他にも、1 つ切り出せる場所があるので、答えは 2 となります。

入力例2

6 4
aaaa
abba
abba
aaaa
ccbb
cdbb

出力例2

5

ある「点対称なデザイン」が別の「点対称なデザイン」を含んでいてもそれぞれ数えます。

また、この例の場合、

b b
b b

が 2 箇所に出てきますが、2 つとも数えます。