A - コンテスト
N 問の問題があるコンテストがあり、i 問目の問題の配点は p_i 点である。コンテスタントは、この問題の中から何問か解き、解いた問題の配点の合計が得点となる。このコンテストの得点は何通り考えられるか。
入力は以下の形式で標準入力から与えられる。
答えを一行に出力せよ。
0, 2, 3, 5, 7, 8, 10 の 7 通りの得点が考えられる。
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 の 11 通りの得点が考えられる。
実行時間制限: 2 sec / メモリ制限: 256 MB
Problem Statement
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
Sample Input 2
10 1 1 1 1 1 1 1 1 1 1
Sample Output 2
11
B - ゲーム
すぬけ君とすめけ君がゲームをしている。最初に、二つの山がある。左の山には A 個の物が積まれており、上から i 番目のものの価値は a_i である。左の山には B 個の物が積まれており、上から i 番目のものの価値は b_i である。すぬけ君とすめけ君は、すぬけ君からはじめて交互に次の操作を繰り返す。
入力は以下の形式で標準入力から与えられる。
答えを一行に出力せよ。
すぬけ君は、最初に左の山の 1 を選ぶべきである。次にすめけ君が右の山の 2 をとり、すぬけ君が右の山の 10 をとる。すぬけ君の取ったものの合計は 1 + 10 = 11 となる。
実行時間制限: 2 sec / メモリ制限: 256 MB
Problem Statement
- 両方の山が空であれば、ゲームを終了する。
- 片方の山が空であれば、空でないほうの山の一番上のものをとる。
- 両方の山が空でなければ、好きなほうの山を選び、一番上のものをとる。
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
Sample Input 2
5 5 2 4 5 4 2 2 8 3 4 5
Sample Output 2
21
C - トーナメント
2^K 人が参加するトーナメントがある。このトーナメントでは以下の形式で試合を行う。
ただし、Elo Rating R_P の人 P と Elo Rating R_Q の人 Q が対戦した場合、人 P が勝つ確率は 1 / (1 + 10^{(R_Q - R_P) / 400}) であり、異なる試合の勝敗は独立であるとする。
入力は以下の形式で標準入力から与えられる。
答えを 2^K 行出力せよ。i 行目は人 i が優勝する確率であり、絶対誤差が 10^{-6} 以下のとき正当と判定される。
実行時間制限: 2 sec / メモリ制限: 256 MB
Problem Statement
- 第 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 ラウンドまで行う。
ただし、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
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 - サイコロ
サイコロを N 回振ったとき、出た目の積が D の倍数となる確率を求めよ。
入力は以下の形式で標準入力から与えられる。
答えを一行に出力せよ。絶対誤差が 10^{-6} 以下のとき正当と判定される。
サイコロを二回振ったときの組み合わせは、 36 通りあり、そのうち 15 通りでは積が 6 の倍数であるので、求める確率は 15/36 である。
実行時間制限: 2 sec / メモリ制限: 256 MB
Problem Statement
Constraints
- 1 ≤ N ≤ 100
- 1 ≤ D ≤ 10^{18}
Input Format
N D
Output Format
Sample Input 1
2 6
Sample Output 1
0.416666667
Sample Input 2
3 2
Sample Output 2
0.875000000
E - 数
N 以下の正整数であって、十進法表記したときの各桁の数の和が D の倍数であるものの個数を mod 1,000,000,007 で求めよ。
入力は以下の形式で標準入力から与えられる。
答えを一行に出力せよ。
1 以上 100 以下の 3 の倍数 33 個が条件を満たす。
実行時間制限: 2 sec / メモリ制限: 256 MB
Problem Statement
Constraints
- 1 ≤ N ≤ 10^{10000}
- 1 ≤ D ≤ 100
Input Format
D N
Output Format
Sample Input 1
3 100
Sample Output 1
33
Sample Input 2
7 123456789012345678901234567890
Sample Output 2
468357804
F - 準急
ある路線には駅 1 から駅 N までの N 個の駅がある。すぬけ君は、この路線に準急を走らせることにした。
入力は以下の形式で標準入力から与えられる。
答えを一行に出力せよ。
実行時間制限: 2 sec / メモリ制限: 256 MB
Problem Statement
- 準急は、駅 1 に止まり、{駅 2, ..., 駅 N-1} の部分集合に止まり、駅 N に止まる。
- 連続する K個以上の駅に止まると、客が飽きてしまうので、そのようなことはしない。
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 - 辞書順
文字列 s の空でない部分列のうち、辞書順で K 番目のものを求めよ。そのようなものが存在しない場合は "Eel" (quotes for clarity) と出力せよ。
ただし、s から何文字か取り除き (0 文字でもよい)、残りの文字を順番を変えずにつなげたものを部分列という。たとえば、"aba" の部分列は "a", "b", "aa", "ab", "ba", "aba" の 6 個である。"a" は異なる場所に二回現れるが、文字列として同じであれば区別しないものとする。
入力は以下の形式で標準入力から与えられる。
答えを一行に出力せよ。
eel の部分列は辞書順に e, ee, eel, el, l である。6 番目は存在しない。
実行時間制限: 2 sec / メモリ制限: 256 MB
Problem Statement
ただし、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
Sample Input 2
lexicographical 100
Sample Output 2
capal
H - ナップザック
N 個の物があり、i 番目のものの重さ、価値、色はそれぞれw_i, v_i, c_i である。すぬけ君は、いくつかのものをナップザックに入れることにした。ただし、ナップザックに入れるものの重さの合計は W 以下であり、色は C 種類以下でなければならない。ナップザックに入れられるものの価値の合計の最大値を求めよ。
入力は以下の形式で標準入力から与えられる。
答えを一行に出力せよ。
二番目と三番目のものを入れるとよい。
実行時間制限: 2 sec / メモリ制限: 256 MB
Problem Statement
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 - イウィ
s は i と w からなる文字列である。すぬけ君は、この中から連続する三文字が "iwi" となっている部分を取り除く操作を繰り返すことができる。(iwi を取り除くと、その左側と右側にあった文字列が連結され、長さが三文字短い新しい文字列ができる。) 操作を行うことのできる回数の最大値を求めよ。
入力は以下の形式で標準入力から与えられる。
答えを一行に出力せよ。
先に 3 文字目から 5 文字目の iwi を取り除くのが最適である。
実行時間制限: 2 sec / メモリ制限: 256 MB
Problem Statement
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
Sample Input 2
iwiwwwiiiwiwiwiiwii
Sample Output 2
5
J - ボール
N 個のものがある。i 番目のものは座標 x_i におかれている。すぬけ君が、座標 x の点を目指してボールを投げると x-1, x, x+1 のうちのいずれかに 1/3 ずつの確率で飛んでいき、そこに物がおいてあった場合は倒れる。最適な戦略でボールを投げたとき、すべての物を倒すのに必要なボールを投げる回数の期待値を求めよ。
追記 : ボールを投げる場所は、前に投げたボールの飛んだ場所を見た後に決めることができる。
入力は以下の形式で標準入力から与えられる。
答えを一行に出力せよ。絶対誤差が 10^{-6} 以下のとき正当と判定される。
座標 1 に向かってボールを投げ続けるのがよい。
実行時間制限: 2 sec / メモリ制限: 256 MB
Problem Statement
追記 : ボールを投げる場所は、前に投げたボールの飛んだ場所を見た後に決めることができる。
Constraints
- 1 ≤ N ≤ 16
- 0 ≤ x_i ≤ 15
- x_i are pairwise distinct.
Input Format
N x_1 ... x_N
Output Format
Sample Input 1
2 0 2
Sample Output 1
4.500000000
Sample Input 2
5 1 3 4 2 5
Sample Output 2
8.986111111
K - ターゲット
円の列 C_1, C_2, ..., C_K は各 i に対し C_{i+1} が C_i の strictly に内部にあるときサイズ K のターゲットであるという。
すぬけ君は、円を N 個描いた。i 番目の円は中心が (x_i, 0) であり、半径が r_i である。この中から円をいくつか選んでターゲットを作るとき、ターゲットの最大サイズを求めよ。
入力は以下の形式で標準入力から与えられる。
答えを一行に出力せよ。
C_1 を二番目の円、C_2 を一番目の円とすればよい。
円の包含関係は strict である (境界が重なっている場合は内部とはみなさない)。
実行時間制限: 2 sec / メモリ制限: 256 MB
Problem Statement
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
Sample Input 2
2 1 1 2 2
Sample Output 2
1
L - 猫
すぬけ君は N 匹の猫を飼っている。猫 i と猫 j の仲のよさは f_{i,j} である。ある猫の幸福度は、その猫から距離 1 以内にいる猫との仲のよさの総和である。すぬけ君は、猫 1 から猫 N をこの順に一次元上に配置することにした。(猫 i の座標を x_i とすると、x_i は x_1 < x_2 < ... < x_N をみたす実数) 猫の幸福度の総和の最大値を求めよ。
入力は以下の形式で標準入力から与えられる。
答えを一行に出力せよ。
たとえば、x_1 = 1, x_2 = 1.5, x_3 = 4 とすると、猫 1 と 2 の幸福度は 2 であり、猫 3 の幸福度は 0 である。
実行時間制限: 2 sec / メモリ制限: 256 MB
Problem Statement
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
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 - 家
すぬけ君の家は 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 で求めよ。
入力は以下の形式で標準入力から与えられる。
答えを一行に出力せよ。
実行時間制限: 8 sec / メモリ制限: 256 MB
Problem Statement
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 - 木
頂点 1 から頂点 N までが紙が描かれている。すぬけ君は、頂点 a_i と頂点 b_i の間に辺を描き、木にすることにした。木を書いている途中で常に辺が連結になっているようにしたいとき、辺を描く順番は何通り考えられるか、mod 1,000,000,007 で求めよ。
入力は以下の形式で標準入力から与えられる。
答えを一行に出力せよ。
実行時間制限: 2 sec / メモリ制限: 256 MB
Problem Statement
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
Sample Input 2
8 1 2 4 6 6 7 3 2 2 4 4 5 8 6
Sample Output 2
752
O - 文字列
以下の条件を満たす文字列の個数を mod 1,000,000,007 で求めよ。
入力は以下の形式で標準入力から与えられる。
答えを一行に出力せよ。
acad, adac, acda, adca, cada, daca が条件を満たす。
実行時間制限: 2 sec / メモリ制限: 256 MB
Problem Statement
- 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
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 - うなぎ
N 頂点からなり、頂点 a_i と b_i が辺で結ばれている木がある。この木に K 本の disjoint なパスを書く方法が何通りあるか、mod 1,000,000,007 で求めよ。
ただし、パスとは、異なる 二頂点間の木上での経路のことである。二つのパスは、共通の頂点を通らないとき disjoint であるという。また、パスを書く順番は区別しないものとする (たとえば、パス P-Q を書いた後にパス R-S を書くことも、パス S-R を書いた後にパス P-Q を書くことも同じであるとみなす。)
入力は以下の形式で標準入力から与えられる。
答えを一行に出力せよ。
実行時間制限: 2 sec / メモリ制限: 256 MB
Problem Statement
ただし、パスとは、異なる 二頂点間の木上での経路のことである。二つのパスは、共通の頂点を通らないとき 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 - 連結
N 個の 0, 1 からなる文字列 w_1, ..., w_N がある。すぬけ君は、この中から文字列をいくつか選び、好きな順番で連結して文字列を作ることにした (同じ文字列を複数回選んでもよい)。このようにして作ることのできる長さ L の文字列の個数を mod 1,000,000,007 で求めよ。ただし、文字列として同じであれば、連結のしかたが異なるものも同じであるとみなす。
入力は以下の形式で標準入力から与えられる。
答えを一行に出力せよ。
0, 1 からなる長さ 10 の文字列がすべて作れることがわかる。
実行時間制限: 2 sec / メモリ制限: 256 MB
Problem Statement
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
Sample Input 2
3 5 01 10 0
Sample Output 2
14
R - グラフ
N 頂点からなる有向グラフがある。g_{i,j} = 1 であるとき頂点 i から頂点 j への有向辺がある。
最初に、すべての頂点は白く塗られている。すぬけ君は、以下の操作を二回行うことができる。
入力は以下の形式で標準入力から与えられる。
答えを一行に出力せよ。
たとえば、1 回目に 1->4, 2 回目に 2->4 とたどると 3 頂点が黒く塗られる。
たとえば、1 回目に 1->3->6->3->4, 2 回目に 2->3->5 とたどると 6 頂点が黒く塗られる。
実行時間制限: 2 sec / メモリ制限: 256 MB
Problem Statement
- ある頂点を選び、その頂点から有向辺をたどっていくつかの頂点に訪れる。同じ頂点を複数回とおってもよい。
- 一回以上通った頂点をすべて黒く塗る。
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
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
S - マス目
すぬけ君は、H x W のマス目を白と黒に塗り分けることにした。
入力は以下の形式で標準入力から与えられる。
答えを一行に出力せよ。
左上と右下が黒で、左下と右上のうち少なくとも一方が黒であるような塗り方が条件を満たす。
実行時間制限: 8 sec / メモリ制限: 256 MB
Problem Statement
- 左上のマス目と右下のマス目は黒に塗る。
- 左上のマス目から、黒いますを上下左右にたどって、右下のマス目に行くことができる。
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 - フィボナッチ
数列 {a_i} を次のように定義する。
入力は以下の形式で標準入力から与えられる。
答えを一行に出力せよ。
K = 2 のとき数列は 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... となる。
実行時間制限: 2 sec / メモリ制限: 256 MB
Problem Statement
- a_1 = a_2 = ... = a_K = 1
- a_i = a_{i-1} + ... + a_{i-K} (i > K)
Constraints
- 2 ≤ K ≤ 1000
- 1 ≤ N ≤ 10^9
Input Format
K N
Output Format
Sample Input 1
2 10
Sample Output 1
55
Sample Input 2
3 10
Sample Output 2
105