A - Fifty-Fifty

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 100

問題文

長さ 4 の英大文字からなる文字列 S が与えられます。 S がちょうど 2 種類の文字からなり、かつ現れる各文字はちょうど 2 回ずつ現れているかどうかを判定してください。

制約

  • S の長さは 4 である
  • S は英大文字からなる

入力

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

S

出力

S がちょうど 2 種類の文字からなり、かつ現れる各文字はちょうど 2 回ずつ現れているなら Yes を、そうでないなら No を出力せよ。


入力例 1

ASSA

出力例 1

Yes

SAS からなり、AS はそれぞれ 2 回ずつ現れます。


入力例 2

STOP

出力例 2

No

入力例 3

FFEE

出力例 3

Yes

入力例 4

FREE

出力例 4

No

Score : 100 points

Problem Statement

You are given a 4-character string S consisting of uppercase English letters. Determine if S consists of exactly two kinds of characters which both appear twice in S.

Constraints

  • The length of S is 4.
  • S consists of uppercase English letters.

Input

Input is given from Standard Input in the following format:

S

Output

If S consists of exactly two kinds of characters which both appear twice in S, print Yes; otherwise, print No.


Sample Input 1

ASSA

Sample Output 1

Yes

S consists of A and S which both appear twice in S.


Sample Input 2

STOP

Sample Output 2

No

Sample Input 3

FFEE

Sample Output 3

Yes

Sample Input 4

FREE

Sample Output 4

No
B - Ordinary Number

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 200

問題文

{1,\ 2,\ ...,\ n} の順列 p = {p_1,\ p_2,\ ...,\ p_n} があります。

以下の条件を満たすような p_i (1 < i < n) がいくつあるかを出力してください。

  • p_{i - 1},\ p_i,\ p_{i + 1}3 つの数の中で、p_i2 番目に小さい。

制約

  • 入力は全て整数である。
  • 3 \leq n \leq 20
  • p は {1,\ 2,\ ...,\ n} の順列である。

入力

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

n
p_1 p_2 ... p_n

出力

条件を満たす p_i の個数を出力せよ。


入力例 1

5
1 3 5 4 2

出力例 1

2

p_1 = 1,\ p_2 = 3,\ p_3 = 5 の中で、p_2 = 32 番目に小さい数です。また、p_3 = 5,\ p_4 = 4,\ p_5 = 2 の中で、p_4 = 42 番目に小さい数です。条件を満たす要素はこの 2 つです。


入力例 2

9
9 6 3 2 5 8 7 4 1

出力例 2

5

Score : 200 points

Problem Statement

We have a permutation p = {p_1,\ p_2,\ ...,\ p_n} of {1,\ 2,\ ...,\ n}.

Print the number of elements p_i (1 < i < n) that satisfy the following condition:

  • p_i is the second smallest number among the three numbers p_{i - 1}, p_i, and p_{i + 1}.

Constraints

  • All values in input are integers.
  • 3 \leq n \leq 20
  • p is a permutation of {1,\ 2,\ ...,\ n}.

Input

Input is given from Standard Input in the following format:

n
p_1 p_2 ... p_n

Output

Print the number of elements p_i (1 < i < n) that satisfy the condition.


Sample Input 1

5
1 3 5 4 2

Sample Output 1

2

p_2 = 3 is the second smallest number among p_1 = 1, p_2 = 3, and p_3 = 5. Also, p_4 = 4 is the second smallest number among p_3 = 5, p_4 = 4, and p_5 = 2. These two elements satisfy the condition.


Sample Input 2

9
9 6 3 2 5 8 7 4 1

Sample Output 2

5
C - Divide the Problems

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 300

問題文

高橋君は、 N 個の競技プログラミング用の問題をつくりました。 それぞれの問題には 1 から N の番号がついており、問題 i の難易度は整数 d_i で表されます(大きいほど難しいです)。

高橋君はある整数 K を決めることで、

  • 難易度が K 以上ならば「 ARC 用の問題」
  • 難易度が K 未満ならば「 ABC 用の問題」

という風に、これらの問題を二種類に分類しようとしています。

ARC 用の問題」と「ABC 用の問題」が同じ数になるような整数 K の選び方は何通りあるでしょうか。

制約

  • 2 \leqq N \leqq 10^5
  • N は偶数である。
  • 1 \leqq d_i \leqq 10^5
  • 入力は全て整数である。

入力

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

N
d_1 d_2 ... d_N

出力

ARC 用の問題」と「ABC 用の問題」が同じ数になるような整数 K の選び方の数を出力してください。


入力例 1

6
9 1 4 4 6 7

出力例 1

2

K=5,6 としたとき、問題 1,5,6 が「ARC 用の問題」、問題 2,3,4 が「ABC 用の問題」となり、条件を満たします。 よって、答えは 2 通りです。


入力例 2

8
9 1 14 5 5 4 4 14

出力例 2

0

ARC 用の問題」と「ABC 用の問題」が同じ数になるような整数 K の選び方が存在しない場合もあります。


入力例 3

14
99592 10342 29105 78532 83018 11639 92015 77204 30914 21912 34519 80835 100000 1

出力例 3

42685

Score : 300 points

Problem Statement

Takahashi made N problems for competitive programming. The problems are numbered 1 to N, and the difficulty of Problem i is represented as an integer d_i (the higher, the harder).

He is dividing the problems into two categories by choosing an integer K, as follows:

  • A problem with difficulty K or higher will be for ARCs.
  • A problem with difficulty lower than K will be for ABCs.

How many choices of the integer K make the number of problems for ARCs and the number of problems for ABCs the same?

Problem Statement

  • 2 \leq N \leq 10^5
  • N is an even number.
  • 1 \leq d_i \leq 10^5
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
d_1 d_2 ... d_N

Output

Print the number of choices of the integer K that make the number of problems for ARCs and the number of problems for ABCs the same.


Sample Input 1

6
9 1 4 4 6 7

Sample Output 1

2

If we choose K=5 or 6, Problem 1, 5, and 6 will be for ARCs, Problem 2, 3, and 4 will be for ABCs, and the objective is achieved. Thus, the answer is 2.


Sample Input 2

8
9 1 14 5 5 4 4 14

Sample Output 2

0

There may be no choice of the integer K that make the number of problems for ARCs and the number of problems for ABCs the same.


Sample Input 3

14
99592 10342 29105 78532 83018 11639 92015 77204 30914 21912 34519 80835 100000 1

Sample Output 3

42685
D - Blue and Red Balls

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 400

問題文

K 個の青いボールと N-K 個の赤いボールがあります。同じ色のボールは区別が不可能です。すぬけ君と高橋君はこれらのボールで遊んでいます。

まず、すぬけ君が、N 個のボールを左から右に一列に並べます。

次に、高橋君は、これらのうち K 個の青いボールのみを回収します。高橋君は、1 回の操作で連続して並ぶ青いボールを何個でも回収することができます。高橋君は、常に K 個の青いボールを回収するのにかかる操作の回数が最小になるように行動します。

K 個の青いボールを回収するために高橋君がちょうど i 回操作をする必要があるボールの並べ方は何通りあるでしょうか。 1 ≤ i ≤ K をみたす i それぞれについて答えを計算し、 10^9+7 で割った余りを答えてください。

制約

  • 1 ≤ K ≤ N ≤ 2000

入力

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

N K

出力

i 行目 (1 ≤ i ≤ K) に高橋君がちょうど i 回操作をする必要があるボールの並べ方の総数を 10^9+7 で割った余りを出力せよ。


入力例 1

5 3

出力例 1

3
6
1

高橋君がちょうど 1 回操作をする必要があるボールの並べ方は (青, 青, 青, 赤, 赤), (赤, 青, 青, 青, 赤), (赤, 赤, 青, 青, 青) の 3 通りです。

高橋君がちょうど 2 回操作をする必要があるボールの並べ方は (青, 青, 赤, 青, 赤), (青, 青, 赤, 赤, 青), (赤, 青, 青, 赤, 青), (赤, 青, 赤, 青, 青), (青, 赤, 青, 青, 赤), (青, 赤, 赤, 青, 青) の 6 通りです。

高橋君がちょうど 3 回操作をする必要があるボールの並べ方は (青, 赤, 青, 赤, 青) のみの 1 通りです。


入力例 2

2000 3

出力例 2

1998
3990006
327341989

並べ方の総数を 10^9+7 で割った余りを出力することに注意してください。

Score : 400 points

Problem Statement

There are K blue balls and N-K red balls. The balls of the same color cannot be distinguished. Snuke and Takahashi are playing with these balls.

First, Snuke will arrange the N balls in a row from left to right.

Then, Takahashi will collect only the K blue balls. In one move, he can collect any number of consecutive blue balls. He will collect all the blue balls in the fewest moves possible.

How many ways are there for Snuke to arrange the N balls in a row so that Takahashi will need exactly i moves to collect all the blue balls? Compute this number modulo 10^9+7 for each i such that 1 \leq i \leq K.

Constraints

  • 1 \leq K \leq N \leq 2000

Input

Input is given from Standard Input in the following format:

N K

Output

Print K lines. The i-th line (1 \leq i \leq K) should contain the number of ways to arrange the N balls so that Takahashi will need exactly i moves to collect all the blue balls, modulo 10^9+7.


Sample Input 1

5 3

Sample Output 1

3
6
1

There are three ways to arrange the balls so that Takahashi will need exactly one move: (B, B, B, R, R), (R, B, B, B, R), and (R, R, B, B, B). (R and B stands for red and blue, respectively).

There are six ways to arrange the balls so that Takahashi will need exactly two moves: (B, B, R, B, R), (B, B, R, R, B), (R, B, B, R, B), (R, B, R, B, B), (B, R, B, B, R), and (B, R, R, B, B).

There is one way to arrange the balls so that Takahashi will need exactly three moves: (B, R, B, R, B).


Sample Input 2

2000 3

Sample Output 2

1998
3990006
327341989

Be sure to print the numbers of arrangements modulo 10^9+7.

E - Hopscotch Addict

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 500

問題文

ケンくんはけんけんぱが大好きです。今日は有向グラフ G の上でけんけんぱをすることにしました。 G1 から N で番号付けされた N 頂点および M 辺からなり、 i 番目の辺は頂点 u_i から頂点 v_i に接続しています。

ケンくんははじめ頂点 S にいて、頂点 T までけんけんぱで移動したいです。 1 回のけんけんぱでは、「自分の今いる頂点から出ている辺を 1 つ選んで、その辺が接続する頂点に移動する」という操作をちょうど 3 回連続で行います。

ケンくんが頂点 T に移動することができるか、また移動できるなら最小何回のけんけんぱで頂点 T まで移動することができるかを答えてください。 けんけんぱの操作の途中で頂点 T に訪れても、「頂点 T に移動できた」とは見なさないことに注意してください。

制約

  • 2 \leq N \leq 10^5
  • 0 \leq M \leq \min(10^5, N (N-1))
  • 1 \leq u_i, v_i \leq N(1 \leq i \leq M)
  • u_i \neq v_i (1 \leq i \leq M)
  • i \neq j ならば (u_i, v_i) \neq (u_j, v_j)
  • 1 \leq S, T \leq N
  • S \neq T

入力

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

N M
u_1 v_1
:
u_M v_M
S T

出力

何回けんけんぱを繰り返しても頂点 S から頂点 T へ移動できない場合には、-1 を出力せよ。 移動できる場合には、移動するのに必要なけんけんぱの最小回数を出力せよ。


入力例 1

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

出力例 1

2

1 回目のけんけんぱでは 1 \rightarrow 2 \rightarrow 3 \rightarrow 42 回目のけんけんぱでは 4 \rightarrow 1 \rightarrow 2 \rightarrow 3 と移動することで頂点 3 に辿り着くことができ、これが最小回数です。


入力例 2

3 3
1 2
2 3
3 1
1 2

出力例 2

-1

何回けんけんぱを繰り返しても頂点 1 に辿り着くため、頂点 2 に移動することは不可能です。 けんけんぱの途中で頂点 2 を通過することはできますが、これは移動できたとは見なしません。


入力例 3

2 0
1 2

出力例 3

-1

頂点 S と頂点 T は非連結である場合があります。


入力例 4

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

出力例 4

2

Score : 500 points

Problem Statement

Ken loves ken-ken-pa (Japanese version of hopscotch). Today, he will play it on a directed graph G. G consists of N vertices numbered 1 to N, and M edges. The i-th edge points from Vertex u_i to Vertex v_i.

First, Ken stands on Vertex S. He wants to reach Vertex T by repeating ken-ken-pa. In one ken-ken-pa, he does the following exactly three times: follow an edge pointing from the vertex on which he is standing.

Determine if he can reach Vertex T by repeating ken-ken-pa. If the answer is yes, find the minimum number of ken-ken-pa needed to reach Vertex T. Note that visiting Vertex T in the middle of a ken-ken-pa does not count as reaching Vertex T by repeating ken-ken-pa.

Constraints

  • 2 \leq N \leq 10^5
  • 0 \leq M \leq \min(10^5, N (N-1))
  • 1 \leq u_i, v_i \leq N(1 \leq i \leq M)
  • u_i \neq v_i (1 \leq i \leq M)
  • If i \neq j, (u_i, v_i) \neq (u_j, v_j).
  • 1 \leq S, T \leq N
  • S \neq T

Input

Input is given from Standard Input in the following format:

N M
u_1 v_1
:
u_M v_M
S T

Output

If Ken cannot reach Vertex T from Vertex S by repeating ken-ken-pa, print -1. If he can, print the minimum number of ken-ken-pa needed to reach vertex T.


Sample Input 1

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

Sample Output 1

2

Ken can reach Vertex 3 from Vertex 1 in two ken-ken-pa, as follows: 1 \rightarrow 2 \rightarrow 3 \rightarrow 4 in the first ken-ken-pa, then 4 \rightarrow 1 \rightarrow 2 \rightarrow 3 in the second ken-ken-pa. This is the minimum number of ken-ken-pa needed.


Sample Input 2

3 3
1 2
2 3
3 1
1 2

Sample Output 2

-1

Any number of ken-ken-pa will bring Ken back to Vertex 1, so he cannot reach Vertex 2, though he can pass through it in the middle of a ken-ken-pa.


Sample Input 3

2 0
1 2

Sample Output 3

-1

Vertex S and Vertex T may be disconnected.


Sample Input 4

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

Sample Output 4

2
F - Small Products

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 600

問題文

正の整数 K 個を一列に並べたものであって、隣接して並んでいるどの 2 つの整数の積も N 以下であるものの個数を 10^9+7 で割った余りを求めてください。

制約

  • 1\leq N\leq 10^9
  • 1 2\leq K\leq 100 (21:33 修正)
  • N,K は整数である

入力

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

N K

出力

条件を満たす列の個数を 10^9+7 で割った余りを出力せよ。


入力例 1

3 2

出力例 1

5

(1,1),(1,2),(1,3),(2,1),(3,1) が条件を満たします。


入力例 2

10 3

出力例 2

147

入力例 3

314159265 35

出力例 3

457397712

Score : 600 points

Problem Statement

Find the number of sequences of length K consisting of positive integers such that the product of any two adjacent elements is at most N, modulo 10^9+7.

Constraints

  • 1\leq N\leq 10^9
  • 1 2\leq K\leq 100 (fixed at 21:33 JST)
  • N and K are integers.

Input

Input is given from Standard Input in the following format:

N K

Output

Print the number of sequences, modulo 10^9+7.


Sample Input 1

3 2

Sample Output 1

5

(1,1), (1,2), (1,3), (2,1), and (3,1) satisfy the condition.


Sample Input 2

10 3

Sample Output 2

147

Sample Input 3

314159265 35

Sample Output 3

457397712