A - Saturday

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

ある日、学校へ行くのに疲れてしまった高橋くんは、土曜日まであと何日あるかを知りたくなりました。
その日は平日で、曜日を英語で表すと S だったことが分かっています。その日より後の直近の土曜日は何日後かを求めてください。

なお、月曜日、火曜日、水曜日、木曜日、金曜日はそれぞれ英語で Monday, Tuesday, Wednesday, Thursday, Friday です。

制約

  • S は Monday, Tuesday, Wednesday, Thursday, Friday のいずれかである

入力

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

S

出力

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


入力例 1

Wednesday

出力例 1

3

この日は水曜日なので、3 日後に土曜日になります。


入力例 2

Monday

出力例 2

5

Score : 100 points

Problem Statement

One day, tired from going to school, Takahashi wanted to know how many days there were until Saturday.
We know that the day was a weekday, and the name of the day of the week was S in English.
How many days were there until the first Saturday after that day (including Saturday but not the starting day)?

Constraints

  • S is Monday, Tuesday, Wednesday, Thursday, or Friday.

Input

Input is given from Standard Input in the following format:

S

Output

Print the answer as an integer.


Sample Input 1

Wednesday

Sample Output 1

3

It was Wednesday, so there were 3 days until the first Saturday after that day.


Sample Input 2

Monday

Sample Output 2

5
B - Cut

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

N 枚からなるカードの山があり、上から i 枚目のカードには整数 A_i が書かれています。

山の下から K 枚のカードを取り出し、順序を保ったまま山の一番上に乗せました。

この操作後の山の上から順に、カードに書かれた整数を出力してください。

制約

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

入力

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

N K
A_1 A_2 \ldots A_N

出力

操作後の山の上から i 枚目のカードに書かれた整数を B_i とする。B_1,B_2,\ldots,B_N をこの順に空白区切りで出力せよ。


入力例 1

5 3
1 2 3 4 5

出力例 1

3 4 5 1 2

最初、カードに書かれた整数は山の上から順に 1,2,3,4,5 です。

山の下から 3 枚のカードを取り出し、そのまま山の一番上に乗せたあと、カードに書かれた整数は山の上から順に 3,4,5,1,2 となります。


入力例 2

6 2
1 2 1 2 1 2

出力例 2

1 2 1 2 1 2

カードに書かれている整数は相異なるとは限りません。

Score : 100 points

Problem Statement

There is a stack of N cards, and the i-th card from the top has an integer A_i written on it.

You take K cards from the bottom of the stack and place them on top of the stack, maintaining their order.

Print the integers written on the cards from top to bottom after the operation.

Constraints

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

Input

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

N K
A_1 A_2 \ldots A_N

Output

Let B_i be the integer written on the i-th card from the top of the stack after the operation. Print B_1,B_2,\ldots,B_N in this order, separated by spaces.


Sample Input 1

5 3
1 2 3 4 5

Sample Output 1

3 4 5 1 2

Initially, the integers written on the cards are 1,2,3,4,5 from top to bottom.

After taking three cards from the bottom of the stack and placing them on top, the integers written on the cards become 3,4,5,1,2 from top to bottom.


Sample Input 2

6 2
1 2 1 2 1 2

Sample Output 2

1 2 1 2 1 2

The integers written on the cards are not necessarily distinct.

C - Cat

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

長さ N の文字列 S が与えられます。

S に連続して含まれる na を全て nya に置き換えて得られる文字列を答えてください。

制約

  • N は 1 以上 1000 以下の整数
  • S は英小文字からなる長さ N の文字列

入力

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

N
S

出力

答えを出力せよ。


入力例 1

4
naan

出力例 1

nyaan

naan に連続して含まれる na を全て nya に置き換えて得られる文字列は nyaan です。


入力例 2

4
near

出力例 2

near

S に na が連続して含まれないこともあります。


入力例 3

8
national

出力例 3

nyationyal

Score : 200 points

Problem Statement

You are given a string S of length N.

Find the string obtained by replacing all contiguous occurrences of na in S with nya.

Constraints

  • N is an integer between 1 and 1000, inclusive.
  • S is a string of length N consisting of lowercase English letters.

Input

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

N
S

Output

Print the answer.


Sample Input 1

4
naan

Sample Output 1

nyaan

Replacing all contiguous occurrences of na in naan with nya results in the string nyaan.


Sample Input 2

4
near

Sample Output 2

near

S may not contain a contiguous na.


Sample Input 3

8
national

Sample Output 3

nyationyal
D - 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
E - T-shirts

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

AtCoder 社はロゴ入りの T シャツを販売しています。

高橋君の N 日間の予定が 0, 1, 2 のみからなる長さ N の文字列 S で与えられます。
具体的には、1\leq i\leq N をみたす整数 i について、

  • S の i 文字目が 0 のとき、i 日目に何の予定も入っていません。
  • S の i 文字目が 1 のとき、i 日目に高橋君は食事に行く予定があります。
  • S の i 文字目が 2 のとき、i 日目に高橋君は競技プログラミングのイベントに行く予定が入っています。

高橋君は無地の T シャツを M 枚持っており、1 日目の直前の時点ですべて洗濯済みの状態となっています。
これに加えて、次の条件をみたすように行動できるように、高橋君は AtCoder のロゴ入りの T シャツを何枚か購入する事にしました。

  • 食事に行く日には、無地の T シャツ 1 枚またはロゴ入りの T シャツ 1 枚を着用する。
  • 競技プログラミングのイベントに行く日にはロゴ入りの T シャツ 1 枚を着用する。
  • 何の予定もない日には T シャツを着用しない。加えて、その時点で着用済みの T シャツを全て洗濯する。 洗濯した T シャツは翌日から着用できる。
  • 一度着用した T シャツは次に洗濯するまで着用できない。

N 日間のうち予定が入っている日すべてについて、条件をみたす T シャツを着用できるようにするために、高橋君は最低何枚のTシャツを購入する必要があるか求めてください。 新しく T シャツを購入する必要がないならば 0 を出力してください。
ただし、購入した T シャツも 1 日目の直前の時点ですべて洗濯済みの状態で存在するものとします。

制約

  • 1\leq M\leq N\leq 1000
  • S は 0, 1, 2 のみからなる長さ N の文字列
  • N,M は整数

入力

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

N M
S

出力

問題文の条件をみたすように行動するために 高橋君が購入する必要のある T シャツの枚数の最小値を出力せよ。
新しく購入する必要がないならば 0 を出力せよ。


入力例 1

6 1
112022

出力例 1

2

高橋君がロゴ入りの T シャツを 2 枚購入したとき、次のようにして高橋君は T シャツを着用することができます。

  • 1 日目、高橋君はロゴ入りの T シャツを着用して食事に行きます。
  • 2 日目、高橋君は無地の T シャツを着用して食事に行きます。
  • 3 日目、高橋君はロゴ入りの T シャツを着用して競技プログラミングのイベントに行きます。
  • 4 日目、高橋君は予定がないため、着用した T シャツをすべて洗濯します。これにより、1,2,3 日目に着用した T シャツを再び着用することが可能になります。
  • 5 日目、高橋君はロゴ入りの T シャツを着用して競技プログラミングのイベントに行きます。
  • 6 日目、高橋君はロゴ入りの T シャツを着用して競技プログラミングのイベントに行きます。

高橋君がロゴ入りの T シャツを 1 枚以下しか購入しなかった場合には、 どのようにしても条件をみたすように T シャツを着用することができません。
よって、2 を出力します。


入力例 2

3 1
222

出力例 2

3

入力例 3

2 1
01

出力例 3

0

高橋君は新しく T シャツを購入する必要はありません。

Score : 300 points

Problem Statement

AtCoder Inc. sells T-shirts with its logo.

You are given Takahashi's schedule for N days as a string S of length N consisting of 0, 1, and 2.
Specifically, for an integer i satisfying 1\leq i\leq N,

  • if the i-th character of S is 0, he has no plan scheduled for the i-th day;
  • if the i-th character of S is 1, he plans to go out for a meal on the i-th day;
  • if the i-th character of S is 2, he plans to attend a competitive programming event on the i-th day.

Takahashi has M plain T-shirts, all washed and ready to wear just before the first day.
In addition, to be able to satisfy the following conditions, he will buy several AtCoder logo T-shirts.

  • On days he goes out for a meal, he will wear a plain or logo T-shirt.
  • On days he attends a competitive programming event, he will wear a logo T-shirt.
  • On days with no plans, he will not wear any T-shirts. Also, he will wash all T-shirts worn at that point. He can wear them again from the next day onwards.
  • Once he wears a T-shirt, he cannot wear it again until he washes it.

Determine the minimum number of T-shirts he needs to buy to be able to wear appropriate T-shirts on all scheduled days during the N days. If he does not need to buy new T-shirts, print 0.
Assume that the purchased T-shirts are also washed and ready to use just before the first day.

Constraints

  • 1\leq M\leq N\leq 1000
  • S is a string of length N consisting of 0, 1, and 2.
  • N and M are integers.

Input

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

N M
S

Output

Print the minimum number of T-shirts Takahashi needs to buy to be able to satisfy the conditions in the problem statement.
If he does not need to buy new T-shirts, print 0.


Sample Input 1

6 1
112022

Sample Output 1

2

If Takahashi buys two logo T-shirts, he can wear T-shirts as follows:

  • On the first day, he wears a logo T-shirt to go out for a meal.
  • On the second day, he wears a plain T-shirt to go out for a meal.
  • On the third day, he wears a logo T-shirt to attend a competitive programming event.
  • On the fourth day, he has no plans, so he washes all the worn T-shirts. This allows him to reuse the T-shirts worn on the first, second, and third days.
  • On the fifth day, he wears a logo T-shirt to attend a competitive programming event.
  • On the sixth day, he wears a logo T-shirt to attend a competitive programming event.

If he buys one or fewer logo T-shirts, he cannot use T-shirts to meet the conditions no matter what. Hence, print 2.


Sample Input 2

3 1
222

Sample Output 2

3

Sample Input 3

2 1
01

Sample Output 3

0

He does not need to buy new T-shirts.