A - コンテスト

Time Limit: 2 sec / Memory Limit: 256 MB

Problem Statement

N 問の問題があるコンテストがあり、i 問目の問題の配点は p_i 点である。コンテスタントは、この問題の中から何問か解き、解いた問題の配点の合計が得点となる。このコンテストの得点は何通り考えられるか。

Constraints

  • 1 ≤ N ≤ 100
  • 1 ≤ p_i ≤ 100

Input Format

入力は以下の形式で標準入力から与えられる。
N
p_1 p_2 ... p_N

Output Format

答えを一行に出力せよ。

Sample Input 1

3
2 3 5

Sample Output 1

7
0, 2, 3, 5, 7, 8, 10 の 7 通りの得点が考えられる。

Sample Input 2

10
1 1 1 1 1 1 1 1 1 1

Sample Output 2

11
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 の 11 通りの得点が考えられる。
B - ゲーム

Time Limit: 2 sec / Memory Limit: 256 MB

Problem Statement

すぬけ君とすめけ君がゲームをしている。最初に、二つの山がある。左の山には A 個の物が積まれており、上から i 番目のものの価値は a_i である。左の山には B 個の物が積まれており、上から i 番目のものの価値は b_i である。すぬけ君とすめけ君は、すぬけ君からはじめて交互に次の操作を繰り返す。
  • 両方の山が空であれば、ゲームを終了する。
  • 片方の山が空であれば、空でないほうの山の一番上のものをとる。
  • 両方の山が空でなければ、好きなほうの山を選び、一番上のものをとる。
両者が最善を尽くしたとき、すぬけ君の取るものの価値の合計を求めよ。

Constraints

  • 1 ≤ A, B ≤ 1000
  • 1 ≤ a_i, b_i ≤ 1000

Input Format

入力は以下の形式で標準入力から与えられる。
A B
a_1 ...a_A
b_1 ... b_B

Output Format

答えを一行に出力せよ。

Sample Input 1

1 2
1
2 10

Sample Output 1

11
すぬけ君は、最初に左の山の 1 を選ぶべきである。次にすめけ君が右の山の 2 をとり、すぬけ君が右の山の 10 をとる。すぬけ君の取ったものの合計は 1 + 10 = 11 となる。

Sample Input 2

5 5
2 4 5 4 2
2 8 3 4 5

Sample Output 2

21
C - トーナメント

Time Limit: 2 sec / Memory Limit: 256 MB

Problem Statement

2^K 人が参加するトーナメントがある。このトーナメントでは以下の形式で試合を行う。
  • 第 1 ラウンドでは、1 と 2、3 と 4、…　が試合を行う。
  • 第 2 ラウンドでは、(1 と 2 の勝者) と (3 と 4 の勝者), (5 と 6 の勝者) と (7 と 8 の勝者), …　が試合を行う。
  • 第 3 ラウンドでは、((1 と 2 の勝者) と (3 と 4 の勝者) の勝者) と ((5 と 6 の勝者) と (7 と 8 の勝者) の勝者), ((9 と 10 の勝者) と (11 と 12 の勝者) の勝者) と ((13 と 14 の勝者) と (15 と 16 の勝者) の勝者), …　が試合を行う。
  • 以下同様に第 K ラウンドまで行う。
第 K ラウンドの終了後に優勝者が決定する。人 i の Elo Rating が R_i であるとき、人 i の優勝確率を求めよ。

ただし、Elo Rating R_P の人 P と Elo Rating R_Q の人 Q が対戦した場合、人 P が勝つ確率は 1 / (1 + 10^{(R_Q - R_P) / 400}) であり、異なる試合の勝敗は独立であるとする。

Constraints

  • 1 ≤ K ≤ 10
  • 0 ≤ R_i ≤ 4000

Input Format

入力は以下の形式で標準入力から与えられる。
K
R_1
…
R_{2^K}

Output Format

答えを 2^K 行出力せよ。i 行目は人 i が優勝する確率であり、絶対誤差が 10^{-6} 以下のとき正当と判定される。

Sample Input 1

1
2200
2600

Sample Output 1

0.090909091
0.909090909

Sample Input 2

3
2000
2500
2300
2700
2100
2400
2600
2200

Sample Output 2

0.000086893
0.122042976
0.005522752
0.493464665
0.000651695
0.053982389
0.321828438
0.002420190
D - サイコロ

Time Limit: 2 sec / Memory Limit: 256 MB

Problem Statement

サイコロを N 回振ったとき、出た目の積が D の倍数となる確率を求めよ。

Constraints

  • 1 ≤ N ≤ 100
  • 1 ≤ D ≤ 10^{18}

Input Format

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

Output Format

答えを一行に出力せよ。絶対誤差が 10^{-6} 以下のとき正当と判定される。

Sample Input 1

2 6

Sample Output 1

0.416666667
サイコロを二回振ったときの組み合わせは、 36 通りあり、そのうち 15 通りでは積が 6 の倍数であるので、求める確率は 15/36 である。

Sample Input 2

3 2

Sample Output 2

0.875000000
E - 数

Time Limit: 2 sec / Memory Limit: 256 MB

Problem Statement

N 以下の正整数であって、十進法表記したときの各桁の数の和が D の倍数であるものの個数を mod 1,000,000,007 で求めよ。

Constraints

  • 1 ≤ N ≤ 10^{10000}
  • 1 ≤ D ≤ 100

Input Format

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

Output Format

答えを一行に出力せよ。

Sample Input 1

3
100

Sample Output 1

33
1 以上 100 以下の 3 の倍数 33 個が条件を満たす。

Sample Input 2

7
123456789012345678901234567890

Sample Output 2

468357804
F - 準急

Time Limit: 2 sec / Memory Limit: 256 MB

Problem Statement

ある路線には駅 1 から駅 N までの N 個の駅がある。すぬけ君は、この路線に準急を走らせることにした。
  • 準急は、駅 1 に止まり、{駅 2, ..., 駅 N-1} の部分集合に止まり、駅 N に止まる。
  • 連続する K個以上の駅に止まると、客が飽きてしまうので、そのようなことはしない。
準急の停車駅の組み合わせとして何通り考えられるか、mod 1,000,000,007 で求めよ。

Constraints

  • 2 ≤ K ≤ N ≤ 1000000

Input Format

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

Output Format

答えを一行に出力せよ。

Sample Input 1

10 2

Sample Output 1

21

Sample Input 2

10 10

Sample Output 2

255
G - 辞書順

Time Limit: 2 sec / Memory Limit: 256 MB

Problem Statement

文字列 s の空でない部分列のうち、辞書順で K 番目のものを求めよ。そのようなものが存在しない場合は "Eel" (quotes for clarity) と出力せよ。

ただし、s から何文字か取り除き (0 文字でもよい)、残りの文字を順番を変えずにつなげたものを部分列という。たとえば、"aba" の部分列は "a", "b", "aa", "ab", "ba", "aba" の 6 個である。"a" は異なる場所に二回現れるが、文字列として同じであれば区別しないものとする。

Constraints

  • 1 ≤ |s| ≤ 1000000
  • Each character in s will be a lowercase letter ('a'-'z').
  • 1 ≤ K ≤ 10^{18}

Input Format

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

Output Format

答えを一行に出力せよ。

Sample Input 1

eel
6

Sample Output 1

Eel
eel の部分列は辞書順に e, ee, eel, el, l である。6 番目は存在しない。

Sample Input 2

lexicographical
100

Sample Output 2

capal
H - ナップザック

Time Limit: 2 sec / Memory Limit: 256 MB

Problem Statement

N 個の物があり、i 番目のものの重さ、価値、色はそれぞれw_i, v_i, c_i である。すぬけ君は、いくつかのものをナップザックに入れることにした。ただし、ナップザックに入れるものの重さの合計は W 以下であり、色は C 種類以下でなければならない。ナップザックに入れられるものの価値の合計の最大値を求めよ。

Constraints

  • 1 ≤ N ≤100
  • 1 ≤ W ≤10000
  • 1 ≤ C ≤ 50
  • 1 ≤ w_i, v_i ≤ 10000
  • 1 ≤ c_i ≤ 50

Input Format

入力は以下の形式で標準入力から与えられる。
N W C
w_1 v_1 c_1
…
w_N v_N c_N

Output Format

答えを一行に出力せよ。

Sample Input 1

4 5 2
1 10 1
1 20 2
1 30 3
10 100 4

Sample Output 1

50
二番目と三番目のものを入れるとよい。

Sample Input 2

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

Sample Output 2

27
I - イウィ

Time Limit: 2 sec / Memory Limit: 256 MB

Problem Statement

s は i と w からなる文字列である。すぬけ君は、この中から連続する三文字が "iwi" となっている部分を取り除く操作を繰り返すことができる。(iwi を取り除くと、その左側と右側にあった文字列が連結され、長さが三文字短い新しい文字列ができる。) 操作を行うことのできる回数の最大値を求めよ。

Constraints

  • 1 ≤ |s| ≤ 300
  • Each character in s will be either 'i' or 'w'.

Input Format

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

Output Format

答えを一行に出力せよ。

Sample Input 1

iwiwii

Sample Output 1

2
先に 3 文字目から 5 文字目の iwi を取り除くのが最適である。

Sample Input 2

iwiwwwiiiwiwiwiiwii

Sample Output 2

5
J - ボール

Time Limit: 2 sec / Memory Limit: 256 MB

Problem Statement

N 個のものがある。i 番目のものは座標 x_i におかれている。すぬけ君が、座標 x の点を目指してボールを投げると x-1, x, x+1 のうちのいずれかに 1/3 ずつの確率で飛んでいき、そこに物がおいてあった場合は倒れる。最適な戦略でボールを投げたとき、すべての物を倒すのに必要なボールを投げる回数の期待値を求めよ。

追記 : ボールを投げる場所は、前に投げたボールの飛んだ場所を見た後に決めることができる。

Constraints

  • 1 ≤ N ≤ 16
  • 0 ≤ x_i ≤ 15
  • x_i are pairwise distinct.

Input Format

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

Output Format

答えを一行に出力せよ。絶対誤差が 10^{-6} 以下のとき正当と判定される。

Sample Input 1

2
0 2

Sample Output 1

4.500000000
座標 1 に向かってボールを投げ続けるのがよい。

Sample Input 2

5
1 3 4 2 5

Sample Output 2

8.986111111
K - ターゲット

Time Limit: 2 sec / Memory Limit: 256 MB

Problem Statement

円の列 C_1, C_2, ..., C_K は各 i に対し C_{i+1} が C_i の strictly に内部にあるときサイズ K のターゲットであるという。 すぬけ君は、円を N 個描いた。i 番目の円は中心が (x_i, 0) であり、半径が r_i である。この中から円をいくつか選んでターゲットを作るとき、ターゲットの最大サイズを求めよ。

Constraints

  • 1 ≤ N ≤ 100000
  • 0 ≤ x_i ≤ 100,000,000
  • 1 ≤ r_i ≤ 100,000,000

Input Format

入力は以下の形式で標準入力から与えられる。
N
x_1 r_1
…
x_N r_N

Output Format

答えを一行に出力せよ。

Sample Input 1

3
1 1
0 3
3 2

Sample Output 1

2
C_1 を二番目の円、C_2 を一番目の円とすればよい。

Sample Input 2

2
1 1
2 2

Sample Output 2

1
円の包含関係は strict である (境界が重なっている場合は内部とはみなさない)。
L - 猫

Time Limit: 2 sec / Memory Limit: 256 MB

Problem Statement

すぬけ君は N 匹の猫を飼っている。猫 i と猫 j の仲のよさは f_{i,j} である。ある猫の幸福度は、その猫から距離 1 以内にいる猫との仲のよさの総和である。すぬけ君は、猫 1 から猫 N をこの順に一次元上に配置することにした。(猫 i の座標を x_i とすると、x_i は x_1 < x_2 < ... < x_N をみたす実数)　猫の幸福度の総和の最大値を求めよ。

Constraints

  • 1 ≤ N ≤ 1000
  • -1000 ≤ f_{i,j} ≤ 1000
  • f_{i,i} = 0
  • f_{i,j} = f_{j,i}

Input Format

入力は以下の形式で標準入力から与えられる。
N
f_{1,1} ... f_{1,N}
...
f_{N,1} ... f_{N,N}

Output Format

答えを一行に出力せよ。

Sample Input 1

3
0 2 3
2 0 -10
3 -10 0

Sample Output 1

4
たとえば、x_1 = 1, x_2 = 1.5, x_3 = 4 とすると、猫 1 と 2 の幸福度は 2 であり、猫 3 の幸福度は 0 である。

Sample Input 2

5
0 -3 5 2 -6
-3 0 6 -3 1
5 6 0 2 0
2 -3 2 0 4
-6 1 0 4 0

Sample Output 2

28
M - 家

Time Limit: 8 sec / Memory Limit: 256 MB

Problem Statement

すぬけ君の家は H 階建てであり、どの階も同じ構造をしている。各階には R 個の部屋があり、部屋 i と部屋 j の間には g_{i,j} = 1 であるとき bidirectional な通路がある。また、h 階の部屋 r から h-1 階の部屋 r に階段を使って降りることができる。(追記 : h, r は任意の整数) (登ることはできない。)　H 階の部屋 1 から 1 階の部屋 1 に同じ部屋をとおらずに行く経路の個数を mod 1,000,000,007 で求めよ。

Constraints

  • 2 ≤ H ≤ 1,000,000,000
  • 1 ≤ R ≤ 16
  • 0 ≤ g_{i,j} ≤ 1
  • g_{i,i} = 0
  • g_{i,j} = g_{j,i}

Input Format

入力は以下の形式で標準入力から与えられる。
H R
g_{1,1} ... g_{1,R}
...
g_{R.1} ... g_{R,R}

Output Format

答えを一行に出力せよ。

Sample Input 1

10 2
0 1
1 0

Sample Output 1

512

Sample Input 2

2 5
0 1 1 1 1
1 0 1 1 1
1 1 0 1 1
1 1 1 0 1
1 1 1 1 0

Sample Output 2

1025
N - 木

Time Limit: 2 sec / Memory Limit: 256 MB

Problem Statement

頂点 1 から頂点 N までが紙が描かれている。すぬけ君は、頂点 a_i と頂点 b_i の間に辺を描き、木にすることにした。木を書いている途中で常に辺が連結になっているようにしたいとき、辺を描く順番は何通り考えられるか、mod 1,000,000,007 で求めよ。

Constraints

  • 2 ≤ N ≤ 1000
  • 1 ≤ a_i, b_i ≤ N
  • The input will represent a tree.

Input Format

入力は以下の形式で標準入力から与えられる。
N
a_1 b_1
...
a_{N-1} b_{N-1}

Output Format

答えを一行に出力せよ。

Sample Input 1

4
1 2
2 3
3 4

Sample Output 1

4
  • 1-2 -> 2-3 -> 3-4
  • 2-3 -> 1-2 -> 3-4
  • 2-3 -> 3-4 -> 1-2
  • 3-4 -> 2-3 -> 1-2
の 4 通りの順番が考えられる。(1-2 と 3-4 の辺を先に書いてしまうと、その時点で辺が非連結となってしまう。)

Sample Input 2

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

Sample Output 2

752
O - 文字列

Time Limit: 2 sec / Memory Limit: 256 MB

Problem Statement

以下の条件を満たす文字列の個数を mod 1,000,000,007 で求めよ。
  • a を freq_1 個、b を freq_2 個、... z を freq_{26} 個含む (他の文字は含まない)。
  • 同じ文字が隣り合うことはない。

Constraints

  • 0 ≤ freq_i ≤ 10
  • At least one of freq_i will be nonzero.

Input Format

入力は以下の形式で標準入力から与えられる。
freq_1 ... freq_{26}

Output Format

答えを一行に出力せよ。

Sample Input 1

1 0 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Sample Output 1

6
acad, adac, acda, adca, cada, daca が条件を満たす。

Sample Input 2

1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Sample Output 2

3628800
P - うなぎ

Time Limit: 2 sec / Memory Limit: 256 MB

Problem Statement

N 頂点からなり、頂点 a_i と b_i が辺で結ばれている木がある。この木に K 本の disjoint なパスを書く方法が何通りあるか、mod 1,000,000,007 で求めよ。

ただし、パスとは、異なる 二頂点間の木上での経路のことである。二つのパスは、共通の頂点を通らないとき disjoint であるという。また、パスを書く順番は区別しないものとする (たとえば、パス P-Q を書いた後にパス R-S を書くことも、パス S-R を書いた後にパス P-Q を書くことも同じであるとみなす。)

Constraints

  • 2 ≤ N ≤ 1000
  • 1 ≤ K ≤ 50
  • 1 ≤ a_i, b_i ≤ N
  • The input will represent a tree.

Input Format

入力は以下の形式で標準入力から与えられる。
N K
a_1 b_1
...
a_{N-1} b_{N-1}

Output Format

答えを一行に出力せよ。

Sample Input 1

4 1
1 2
2 3
3 4

Sample Output 1

6

Sample Input 2

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

Sample Output 2

9
Q - 連結

Time Limit: 2 sec / Memory Limit: 256 MB

Problem Statement

N 個の 0, 1 からなる文字列 w_1, ..., w_N がある。すぬけ君は、この中から文字列をいくつか選び、好きな順番で連結して文字列を作ることにした (同じ文字列を複数回選んでもよい)。このようにして作ることのできる長さ L の文字列の個数を mod 1,000,000,007 で求めよ。ただし、文字列として同じであれば、連結のしかたが異なるものも同じであるとみなす。

Constraints

  • 1 ≤ N ≤ 510
  • 1 ≤ |w_i| ≤ 8
  • 1 ≤ L ≤ 100
  • Each character in w_i will be either '0' or '1'.
  • w_i are pairwise distinct.

Input Format

入力は以下の形式で標準入力から与えられる。
N L
w_1
...
w_N

Output Format

答えを一行に出力せよ。

Sample Input 1

4 10
00
01
10
11

Sample Output 1

1024
0, 1 からなる長さ 10 の文字列がすべて作れることがわかる。

Sample Input 2

3 5
01
10
0

Sample Output 2

14
R - グラフ

Time Limit: 2 sec / Memory Limit: 256 MB

Problem Statement

N 頂点からなる有向グラフがある。g_{i,j} = 1 であるとき頂点 i から頂点 j への有向辺がある。 最初に、すべての頂点は白く塗られている。すぬけ君は、以下の操作を二回行うことができる。
  • ある頂点を選び、その頂点から有向辺をたどっていくつかの頂点に訪れる。同じ頂点を複数回とおってもよい。
  • 一回以上通った頂点をすべて黒く塗る。
二回の操作後、黒く塗られた頂点の個数の最大値を求めよ。

Constraints

  • 1 ≤ N ≤ 300
  • 0 ≤ g_{i,j} ≤ 1
  • g_{i,i} = 0

Input Format

入力は以下の形式で標準入力から与えられる。
N
g_{1,1} ... g_{1,N}
...
g_{N,1} ... g_{N,N}

Output Format

答えを一行に出力せよ。

Sample Input 1

4
0 0 0 1
0 0 0 1
0 0 0 1
0 0 0 0

Sample Output 1

3
たとえば、1 回目に 1->4, 2 回目に 2->4 とたどると 3 頂点が黒く塗られる。

Sample Input 2

6
0 0 1 0 0 0
0 0 1 0 0 0
0 0 0 1 1 1
0 0 0 0 0 0
0 0 0 0 0 0
0 0 1 0 0 0

Sample Output 2

6
たとえば、1 回目に 1->3->6->3->4, 2 回目に 2->3->5 とたどると 6 頂点が黒く塗られる。
S - マス目

Time Limit: 8 sec / Memory Limit: 256 MB

Problem Statement

すぬけ君は、H x W のマス目を白と黒に塗り分けることにした。
  • 左上のマス目と右下のマス目は黒に塗る。
  • 左上のマス目から、黒いますを上下左右にたどって、右下のマス目に行くことができる。
条件を満たす塗り分け方の個数を mod 1,000,000,007 で求めよ。

Constraints

  • 2 ≤ H ≤ 6
  • 2 ≤ W ≤ 100

Input Format

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

Output Format

答えを一行に出力せよ。

Sample Input 1

2 2

Sample Output 1

3
左上と右下が黒で、左下と右上のうち少なくとも一方が黒であるような塗り方が条件を満たす。

Sample Input 2

5 8

Sample Output 2

950397139
T - フィボナッチ

Time Limit: 2 sec / Memory Limit: 256 MB

Problem Statement

数列 {a_i} を次のように定義する。
  • a_1 = a_2 = ... = a_K = 1
  • a_i = a_{i-1} + ... + a_{i-K} (i > K)
a_N を mod 1,000,000,007 で求めよ。

Constraints

  • 2 ≤ K ≤ 1000
  • 1 ≤ N ≤ 10^9

Input Format

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

Output Format

答えを一行に出力せよ。

Sample Input 1

2 10

Sample Output 1

55
K = 2 のとき数列は 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... となる。

Sample Input 2

3 10

Sample Output 2

105