A - G1

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

AtCoder 国では馬のレースが N 個開催されています。
i 個目のレースには A_i 歳以下の馬が出場できます。
N 個のレースのうち、 K 歳の馬が出場できるレースの個数はいくつですか？

制約

  • 入力は全て整数
  • 1 \le N \le 100
  • 1 \le A_i \le 100
  • 1 \le K \le 100

入力

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

N
A_1 A_2 \dots A_N
K

出力

答えを整数として出力せよ。

入力例 1

5
3 1 4 1 5
4

出力例 1

2
  • 1 個目のレースには 3 歳以下の馬が出場できます。
  • 2 個目のレースには 1 歳以下の馬が出場できます。
  • 3 個目のレースには 4 歳以下の馬が出場できます。
  • 4 個目のレースには 1 歳以下の馬が出場できます。
  • 5 個目のレースには 5 歳以下の馬が出場できます。

5 個のレースのうち、 4 歳の馬が出場できるものは 3,5 個目の 2 つです。

入力例 2

1
1
100

出力例 2

0

K 歳の馬が出場できるレースがひとつもない場合もあります。

入力例 3

15
18 89 31 2 15 93 64 78 58 19 79 59 24 50 30
38

出力例 3

8

Score : 100 points

Problem Statement

In AtCoder Kingdom, there are N horse races being held.
Horses aged A_i or younger can participate in the i-th race.
Among the N races, how many races can a K-year-old horse participate in?

Constraints

  • All input values are integers.
  • 1 \le N \le 100
  • 1 \le A_i \le 100
  • 1 \le K \le 100

Input

The input is given from Standard Input in the following format:

N
A_1 A_2 \dots A_N
K

Output

Output the answer as an integer.

Sample Input 1

5
3 1 4 1 5
4

Sample Output 1

2
  • Horses aged 3 or younger can participate in the 1st race.
  • Horses aged 1 or younger can participate in the 2nd race.
  • Horses aged 4 or younger can participate in the 3rd race.
  • Horses aged 1 or younger can participate in the 4th race.
  • Horses aged 5 or younger can participate in the 5th race.

Among the 5 races, a 4-year-old horse can participate in the 3rd and 5th races, which is 2 races.

Sample Input 2

1
1
100

Sample Output 2

0

There may be no races that a K-year-old horse can participate in.

Sample Input 3

15
18 89 31 2 15 93 64 78 58 19 79 59 24 50 30
38

Sample Output 3

8
B - wwwvvvvvv

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

v と w のみからなる文字列 S が与えられます。

S の中に、下に尖っている部分が何箇所あるかを出力してください（入出力例にある図もご参照ください）。

制約

  • S は v と w のみからなる文字列
  • S の長さは 1 以上 100 以下

入力

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

S

出力

答えを整数として出力せよ。

入力例 1

vvwvw

出力例 1

7

vvwvw

上の画像のように、vvwvw という文字列には下に尖った部分が 7 箇所あります。

入力例 2

v

出力例 2

1

入力例 3

wwwvvvvvv

出力例 3

12

Score : 100 points

Problem Statement

You are given a string S consisting of v and w.

Print the number of "bottoms" in the string S (see the figure at Sample Input/Output).

Constraints

  • S is a string consisting of v and w.
  • The length of S is between 1 and 100, inclusive.

Input

The input is given from Standard Input in the following format:

S

Output

Print the answer as an integer.

Sample Input 1

vvwvw

Sample Output 1

7

vvwvw

The image above shows the seven "bottoms" in the string vvwvw.

Sample Input 2

v

Sample Output 2

1

Sample Input 3

wwwvvvvvv

Sample Output 3

12
C - Adjacency List

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

1, \dots, N と番号付けられた N 個の都市と、都市間を結ぶ M 本の道路があります。
i \, (1 \leq i \leq M) 番目の道路は都市 A_i と都市 B_i を結んでいます。

以下の指示に従い、N 行にわたって出力してください。

  • 都市 i \, (1 \leq i \leq N) と道路で直接結ばれた都市が d_i 個あるとし、それらを昇順に都市 a_{i, 1}, \dots, a_{i, d_i} とおく。
  • i \, (1 \leq i \leq N) 行目には、d_i + 1 個の整数 d_i, a_{i, 1}, \dots, a_{i, d_i} を、この順番で空白区切りで出力せよ。

制約

  • 2 \leq N \leq 10^5
  • 1 \leq M \leq 10^5
  • 1 \leq A_i \lt B_i \leq N \, (1 \leq i \leq M)
  • (i \neq j) ならば (A_i, B_i) \neq (A_j, B_j)
  • 入力される値は全て整数

入力

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

N M
A_1 B_1
\vdots
A_M B_M

出力

問題文の指示に従い、N 行にわたって出力せよ。

入力例 1

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

出力例 1

3 2 3 6
2 1 5
2 1 6
0
2 2 6
3 1 3 5

都市 1 と道路で直接結ばれているのは都市 2, 3, 6 です。よって、d_1 = 3, a_{1, 1} = 2, a_{1, 2} = 3, a_{1, 3} = 6 であるので、1 行目には 3, 2, 3, 6 をこの順番で空白区切りで出力します。

a_{i, 1}, \dots, a_{i, d_i} は昇順に並んでいなければならないことに注意してください。例えば、1 行目に 3, 3, 2, 6 をこの順番で出力した場合、不正解となります。

入力例 2

5 10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5

出力例 2

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

Score : 200 points

Problem Statement

There are N cities numbered 1, \dots, N, and M roads connecting cities.
The i-th road (1 \leq i \leq M) connects city A_i and city B_i.

Print N lines as follows.

  • Let d_i be the number of cities directly connected to city i \, (1 \leq i \leq N), and those cities be city a_{i, 1}, \dots, city a_{i, d_i}, in ascending order.
  • The i-th line (1 \leq i \leq N) should contain d_i + 1 integers d_i, a_{i, 1}, \dots, a_{i, d_i} in this order, separated by spaces.

Constraints

  • 2 \leq N \leq 10^5
  • 1 \leq M \leq 10^5
  • 1 \leq A_i \lt B_i \leq N \, (1 \leq i \leq M)
  • (A_i, B_i) \neq (A_j, B_j) if (i \neq j).
  • All values in the input are integers.

Input

The input is given from Standard Input in the following format:

N M
A_1 B_1
\vdots
A_M B_M

Output

Print N lines as specified in the Problem Statement.

Sample Input 1

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

Sample Output 1

3 2 3 6
2 1 5
2 1 6
0
2 2 6
3 1 3 5

The cities directly connected to city 1 are city 2, city 3, and city 6. Thus, we have d_1 = 3, a_{1, 1} = 2, a_{1, 2} = 3, a_{1, 3} = 6, so you should print 3, 2, 3, 6 in the first line in this order, separated by spaces.

Note that a_{i, 1}, \dots, a_{i, d_i} must be in ascending order. For instance, it is unacceptable to print 3, 3, 2, 6 in the first line in this order.

Sample Input 2

5 10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5

Sample Output 2

4 2 3 4 5
4 1 3 4 5
4 1 2 4 5
4 1 2 3 5
4 1 2 3 4
D - Unique Nicknames

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

人 1, 人 2, \dots 人 N の N 人の人がいます。人 i の姓は s_i、名は t_i です。

N 人の人すべてにあだ名をつけることを考えます。人 i のあだ名 a_i は以下の条件を満たす必要があります。

  • a_i は人 i の姓あるいは名と一致する。言い換えると、a_i = s_i または a_i = t_i の少なくとも一方が成り立つ。
  • a_i は自分以外の人の姓および名のどちらとも一致しない。言い換えると、1 \leq j \leq N, i \neq j を満たすすべての整数 j について a_i \neq s_j かつ a_i \neq t_j が成り立つ。

N 人全員に条件を満たすあだ名をつけることは可能でしょうか。可能ならば Yes を、そうでないならば No を出力してください。

制約

  • 2 \leq N \leq 100
  • N は整数である。
  • s_i,t_i は英小文字からなる 1 文字以上 10 文字以下の文字列である。

入力

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

N
s_1 t_1
s_2 t_2
\vdots
s_N t_N

出力

N 人すべてにあだ名をつけることが可能ならば Yes を、そうでないならば No を出力せよ。

入力例 1

3
tanaka taro
tanaka jiro
suzuki hanako

出力例 1

Yes

a_1 = taro, a_2 = jiro, a_3 = hanako とすれば、これは問題文にあるあだ名の条件を満たしています。(a_3 は suzuki でもよいです。)
ここで、a_1 = tanaka とはできないことに注意してください。なぜならば 人 2 の姓 s_2 もまた tanaka であるため、あだ名の条件の 2 つ目を満たさなくなるからです。

入力例 2

3
aaa bbb
xxx aaa
bbb yyy

出力例 2

No

問題文の条件を満たすあだ名のつけ方は存在しません。

入力例 3

2
tanaka taro
tanaka taro

出力例 3

No

同姓同名である人の組が存在する場合もあります。

入力例 4

3
takahashi chokudai
aoki kensho
snu ke

出力例 4

Yes

a_1 = chokudai, a_2 = kensho, a_3 = ke とすればよいです。

Score : 200 points

Problem Statement

There are N people numbered Person 1, Person 2, \dots, and Person N. Person i has a family name s_i and a given name t_i.

Consider giving a nickname to each of the N people. Person i's nickname a_i should satisfy all the conditions below.

  • a_i coincides with Person i's family name or given name. In other words, a_i = s_i and/or a_i = t_i holds.
  • a_i does not coincide with the family name and the given name of any other person. In other words, for all integer j such that 1 \leq j \leq N and i \neq j, it holds that a_i \neq s_j and a_i \neq t_j.

Is it possible to give nicknames to all the N people? If it is possible, print Yes; otherwise, print No.

Constraints

  • 2 \leq N \leq 100
  • N is an integer.
  • s_i and t_i are strings of lengths between 1 and 10 (inclusive) consisting of lowercase English alphabets.

Input

Input is given from Standard Input in the following format:

N
s_1 t_1
s_2 t_2
\vdots
s_N t_N

Output

If it is possible to give nicknames to all the N people, print Yes; otherwise, print No.

Sample Input 1

3
tanaka taro
tanaka jiro
suzuki hanako

Sample Output 1

Yes

The following assignment satisfies the conditions of nicknames described in the Problem Statement: a_1 = taro, a_2 = jiro, a_3 = hanako. (a_3 may be suzuki, too.)
However, note that we cannot let a_1 = tanaka, which violates the second condition of nicknames, since Person 2's family name s_2 is tanaka too.

Sample Input 2

3
aaa bbb
xxx aaa
bbb yyy

Sample Output 2

No

There is no way to give nicknames satisfying the conditions in the Problem Statement.

Sample Input 3

2
tanaka taro
tanaka taro

Sample Output 3

No

There may be a pair of people with the same family name and the same given name.

Sample Input 4

3
takahashi chokudai
aoki kensho
snu ke

Sample Output 4

Yes

We can let a_1 = chokudai, a_2 = kensho, and a_3 = ke.
E - Dice Sum

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

長さ N の整数からなる数列 A=(A_1,\ldots,A_N) であって、以下の条件を全て満たすものは何通りありますか？

  • 1\le A_i \le M (1 \le i \le N)

  • \displaystyle\sum _{i=1}^N A_i \leq K

ただし、答えは非常に大きくなることがあるので、答えを 998244353 で割った余りを求めてください。

制約

  • 1 \leq N, M \leq 50
  • N \leq K \leq NM
  • 入力は全て整数

入力

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

N M K

出力

答えを 998244353 で割った余りを出力せよ。

入力例 1

2 3 4

出力例 1

6

条件を満たす数列は以下の 6 つです。

  • (1,1)
  • (1,2)
  • (1,3)
  • (2,1)
  • (2,2)
  • (3,1)

入力例 2

31 41 592

出力例 2

798416518

答えを 998244353 で割った余りを出力してください。

Score : 300 points

Problem Statement

How many integer sequences of length N, A=(A_1, \ldots, A_N), satisfy all of the conditions below?

  • 1\le A_i \le M (1 \le i \le N)

  • \displaystyle\sum _{i=1}^N A_i \leq K

Since the count can get enormous, find it modulo 998244353.

Constraints

  • 1 \leq N, M \leq 50
  • N \leq K \leq NM
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M K

Output

Print the answer.

Sample Input 1

2 3 4

Sample Output 1

6

The following six sequences satisfy the conditions.

  • (1,1)
  • (1,2)
  • (1,3)
  • (2,1)
  • (2,2)
  • (3,1)

Sample Input 2

31 41 592

Sample Output 2

798416518

Be sure to print the count modulo 998244353.