A - Weird Function

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

関数 f を f(x) = x^2 + 2x + 3 と定義します。
整数 t が入力されるので、 f(f(f(t)+t)+f(f(t))) を求めてください。
ただし、答えは 2 \times 10^9 以下の整数であることが保証されます。

制約

  • t は 0 以上 10 以下の整数である

入力

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

t

出力

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


入力例 1

0

出力例 1

1371

答えは以下の手順によって計算されます。

  • f(t) = t^2 + 2t + 3 = 0 \times 0 + 2 \times 0 + 3 = 3
  • f(t)+t = 3 + 0 = 3
  • f(f(t)+t) = f(3) = 3 \times 3 + 2 \times 3 + 3 = 18
  • f(f(t)) = f(3) = 18
  • f(f(f(t)+t)+f(f(t))) = f(18+18) = f(36) = 36 \times 36 + 2 \times 36 + 3 = 1371

入力例 2

3

出力例 2

722502

入力例 3

10

出力例 3

1111355571

Score : 100 points

Problem Statement

Let us define a function f as f(x) = x^2 + 2x + 3.
Given an integer t, find f(f(f(t)+t)+f(f(t))).
Here, it is guaranteed that the answer is an integer not greater than 2 \times 10^9.

Constraints

  • t is an integer between 0 and 10 (inclusive).

Input

Input is given from Standard Input in the following format:

t

Output

Print the answer as an integer.


Sample Input 1

0

Sample Output 1

1371

The answer is computed as follows.

  • f(t) = t^2 + 2t + 3 = 0 \times 0 + 2 \times 0 + 3 = 3
  • f(t)+t = 3 + 0 = 3
  • f(f(t)+t) = f(3) = 3 \times 3 + 2 \times 3 + 3 = 18
  • f(f(t)) = f(3) = 18
  • f(f(f(t)+t)+f(f(t))) = f(18+18) = f(36) = 36 \times 36 + 2 \times 36 + 3 = 1371

Sample Input 2

3

Sample Output 2

722502

Sample Input 3

10

Sample Output 3

1111355571
B - Shift

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

長さ N の数列 A = (A_1, A_2, \dots, A_N) が与えられます。
あなたは次の操作をちょうど K 回行います。

  • A の先頭の要素を取り除き、A の末尾に 0 を挿入する。

操作を行った後の A の要素をすべて出力してください。

制約

  • 1 \leq N \leq 100
  • 1 \leq K \leq 100
  • 1 \leq A_i \leq 100
  • 入力される値はすべて整数

入力

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

N K
A_1 A_2 \dots A_N

出力

操作を行った後の A の要素を空白区切りで 1 行に出力せよ。


入力例 1

3 2
2 7 8

出力例 1

8 0 0

操作を行う前は A = (2, 7, 8) です。
操作を 1 回行った時点では A = (7, 8, 0) です。
操作を 2 回行った時点では A = (8, 0, 0) です。
よって (8, 0, 0) が答えです。


入力例 2

3 4
9 9 9

出力例 2

0 0 0

入力例 3

9 5
1 2 3 4 5 6 7 8 9

出力例 3

6 7 8 9 0 0 0 0 0

Score : 100 points

Problem Statement

You are given a sequence A = (A_1, A_2, \dots, A_N) of length N.
You perform the following operation exactly K times:

  • remove the initial element of A and append a 0 to the tail of A.

Print all the elements of A after the operations.

Constraints

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

Input

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

N K
A_1 A_2 \dots A_N

Output

Print the elements of A after the operations in one line, separated by spaces.


Sample Input 1

3 2
2 7 8

Sample Output 1

8 0 0

Before the operations, A = (2, 7, 8).
After performing the operation once, A = (7, 8, 0).
After performing the operation twice, A = (8, 0, 0).
Thus, (8, 0, 0) is the answer.


Sample Input 2

3 4
9 9 9

Sample Output 2

0 0 0

Sample Input 3

9 5
1 2 3 4 5 6 7 8 9

Sample Output 3

6 7 8 9 0 0 0 0 0
C - Prefix and Suffix

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

英小文字からなる文字列 S, T が与えられます。S の長さは N、T の長さは M です。(N \leq M が制約で保証されています)

S が T の 接頭辞 であるとは、T のはじめ N 文字からなる文字列が S と一致することを言います。
S が T の 接尾辞 であるとは、T の後ろ N 文字からなる文字列が S と一致することを言います。

S が T の接頭辞であり、かつ接尾辞でもある場合は 0 を、
S が T の接頭辞であるが、接尾辞でない場合は 1 を、
S が T の接尾辞であるが、接頭辞でない場合は 2 を、
S が T の接頭辞でも接尾辞でもない場合は 3 を出力してください。

制約

  • 1 \leq N \leq M \leq 100
  • S は英小文字からなる長さ N の文字列
  • T は英小文字からなる長さ M の文字列

入力

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

N M
S
T

出力

問題文の指示に従って答えを出力せよ。


入力例 1

3 7
abc
abcdefg

出力例 1

1

S は T の接頭辞ですが接尾辞ではありません。よって 1 を出力します。


入力例 2

3 4
abc
aabc

出力例 2

2

S は T の接尾辞ですが接頭辞ではありません。


入力例 3

3 3
abc
xyz

出力例 3

3

S は T の接頭辞でも接尾辞でもありません。


入力例 4

3 3
aaa
aaa

出力例 4

0

S と T が完全に一致する場合もあります。この場合、S は T の接頭辞であり、かつ接尾辞でもあります。

Score : 200 points

Problem Statement

You are given two strings S and T consisting of lowercase English letters. The lengths of S and T are N and M, respectively. (The constraints guarantee that N \leq M.)

S is said to be a prefix of T when the first N characters of T coincide S.
S is said to be a suffix of T when the last N characters of T coincide S.

If S is both a prefix and a suffix of T, print 0;
If S is a prefix of T but not a suffix, print 1;
If S is a suffix of T but not a prefix, print 2;
If S is neither a prefix nor a suffix of T, print 3.

Constraints

  • 1 \leq N \leq M \leq 100
  • S is a string of length N consisting of lowercase English letters.
  • T is a string of length M consisting of lowercase English letters.

Input

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

N M
S
T

Output

Print the answer according to the instructions in the problem statement.


Sample Input 1

3 7
abc
abcdefg

Sample Output 1

1

S is a prefix of T but not a suffix, so you should print 1.


Sample Input 2

3 4
abc
aabc

Sample Output 2

2

S is a suffix of T but not a prefix.


Sample Input 3

3 3
abc
xyz

Sample Output 3

3

S is neither a prefix nor a suffix of T.


Sample Input 4

3 3
aaa
aaa

Sample Output 4

0

S and T may coincide, in which case S is both a prefix and a suffix of T.

D - Hit and Blow

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

長さ N の整数列 A = (A_1, A_2, \dots, A_N), B = (B_1, B_2, \dots, B_N) が与えられます。
A の要素はすべて異なります。B の要素もすべて異なります。

次の 2 つを出力してください。

  1. A にも B にも含まれ、その位置も一致している整数の個数。言い換えると、A_i = B_i を満たす整数 i の個数。
  2. A にも B にも含まれるが、その位置は異なる整数の個数。言い換えると、A_i = B_j, i \neq j を満たす整数の組 (i, j) の個数。

制約

  • 1 \leq N \leq 1000
  • 1 \leq A_i \leq 10^9
  • 1 \leq B_i \leq 10^9
  • A_1, A_2, \dots, A_N はすべて異なる。
  • B_1, B_2, \dots, B_N はすべて異なる。
  • 入力はすべて整数である。

入力

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

N
A_1 A_2 \dots A_N
B_1 B_2 \dots B_N

出力

答えを 2 行出力せよ。1 行目には 1. の個数、2 行目には 2. の個数を出力せよ。


入力例 1

4
1 3 5 2
2 3 1 4

出力例 1

1
2

A にも B にも含まれ、その位置も一致している整数は A_2 = B_2 = 3 の 1 個です。
A にも B にも含まれるが、その位置は異なる整数は A_1 = B_3 = 1 と A_4 = B_1 = 2 の 2 個です。


入力例 2

3
1 2 3
4 5 6

出力例 2

0
0

1., 2. ともに条件を満たす整数は存在しません。


入力例 3

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

出力例 3

3
2

Score : 200 points

Problem Statement

You are given integer sequences, each of length N: A = (A_1, A_2, \dots, A_N) and B = (B_1, B_2, \dots, B_N).
All elements of A are different. All elements of B are different, too.

Print the following two values.

  1. The number of integers contained in both A and B, appearing at the same position in the two sequences. In other words, the number of integers i such that A_i = B_i.
  2. The number of integers contained in both A and B, appearing at different positions in the two sequences. In other words, the number of pairs of integers (i, j) such that A_i = B_j and i \neq j.

Constraints

  • 1 \leq N \leq 1000
  • 1 \leq A_i \leq 10^9
  • 1 \leq B_i \leq 10^9
  • A_1, A_2, \dots, A_N are all different.
  • B_1, B_2, \dots, B_N are all different.
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \dots A_N
B_1 B_2 \dots B_N

Output

Print the answers in two lines: the answer to1. in the first line, and the answer to2. in the second line.


Sample Input 1

4
1 3 5 2
2 3 1 4

Sample Output 1

1
2

There is one integer contained in both A and B, appearing at the same position in the two sequences: A_2 = B_2 = 3.
There are two integers contained in both A and B, appearing at different positions in the two sequences: A_1 = B_3 = 1 and A_4 = B_1 = 2.


Sample Input 2

3
1 2 3
4 5 6

Sample Output 2

0
0

In both 1. and 2., no integer satisfies the condition.


Sample Input 3

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

Sample Output 3

3
2
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.