AtCoder Daily Training EASY 2025/08/06 18:00start

A - Required Length

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

配点 : 100 点

問題文

高橋君は、ある web サイトに設定するパスワードを、英小文字のみからなる文字列 P にしようと考えています。
一方で、その web サイトのパスワードは長さ L 以上の文字列である必要があります。

P が長さの条件をみたすか、すなわち長さ L 以上の文字列であるか判定してください。

制約

P は英小文字のみからなる長さ 1 以上 100 以下の文字列
1 \leq L \leq 100
L は整数

入力

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

P
L

出力

P が長さの条件をみたすならば Yes を、そうでないならば No を出力せよ。

入力例 1

chokudai
5

出力例 1

Yes

chokudai の長さは 8 であり、特に 5 以上であるため長さの条件をみたしています。
よって、Yes を出力します。

入力例 2

ac
3

出力例 2

No

ac の長さは 2 であり、特に 3 未満であるため長さの条件をみたしていません。
よって、No を出力します。

入力例 3

atcoder
7

出力例 3

Yes

atcoder の長さは 7 であり、特に 7 以上であるため長さの条件をみたしています。
よって、Yes を出力します。

Score : 100 points

Problem Statement

Takahashi wants to set his password for a certain website to a string P consisting of lowercase English letters.
The password for that website must be a string of length at least L.

Determine whether P satisfies the length condition, that is, whether it is a string of length at least L.

Constraints

P is a string consisting of lowercase English letters with length between 1 and 100, inclusive.
1 \leq L \leq 100
L is an integer.

Input

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

P
L

Output

If P satisfies the length condition, print Yes; otherwise, print No.

Sample Input 1

chokudai
5

Sample Output 1

Yes

The length of chokudai is 8, which is at least 5, so it satisfies the length condition.
Thus, print Yes.

Sample Input 2

ac
3

Sample Output 2

No

The length of ac is 2, which is less than 3, so it does not satisfy the length condition.
Thus, print No.

Sample Input 3

atcoder
7

Sample Output 3

Yes

The length of atcoder is 7, which is at least 7, so it satisfies the length condition.
Thus, print Yes.

B - Last Two Digits

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

配点 : 100 点

問題文

100 以上の整数 N が与えられます。N の下 2 桁を出力してください。

ただし、N の下 2 桁とは十の位と一の位をこの順に並べたものを言います。

制約

100 \le N \le 999
N は整数である。

入力

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

出力

答えを出力せよ。

入力例 1

出力例 1

254 の下 2 桁は 54 であるため、54 を出力します。

入力例 2

出力例 2

101 の下 2 桁は 01 であるため、01 を出力します。

Score : 100 points

Problem Statement

You are given an integer N at least 100. Print the last two digits of N.

Strictly speaking, print the tens and ones digits of N in this order.

Constraints

100 \le N \le 999
N is an integer.

Input

Input is given from Standard Input in the following format:

Output

Print the answer.

Sample Input 1

Sample Output 1

The last two digits of 254 are 54, which should be printed.

Sample Input 2

Sample Output 2

The last two digits of 101 are 01, which should be printed.

C - Postal Card

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

配点 : 200 点

問題文

数字のみからなる長さ 6 の文字列が N 個与えられます。i \, (i = 1, 2, \dots, N) 番目のものを S_i と表します。

さらに、数字のみからなる長さ 3 の文字列が M 個与えられます。j \, (j = 1, 2, \dots, M) 番目のものを T_j と表します。

S_1, S_2, \dots, S_N のうち、末尾 3 文字が T_1, T_2, \dots, T_M のいずれかに一致するものの個数を求めてください。

制約

1 \leq N, M \leq 1000
N, M は整数
全ての i = 1, 2, \dots, N に対し、S_i は数字のみからなる長さ 6 の文字列
全ての j = 1, 2, \dots, M に対し、T_j は数字のみからなる長さ 3 の文字列

入力

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

N M
S_1
S_2
\vdots
S_N
T_1
T_2
\vdots
T_M

出力

答えを出力せよ。

入力例 1

出力例 1

S_1 の末尾 3 文字は 857 であり、これは T_3 に一致します。
S_2 の末尾 3 文字は 159 であり、これは T_1 に一致します。
S_3 の末尾 3 文字は 028 であり、これは T_1, T_2, T_3 のいずれにも一致しません。

以上から、答えは 2 です。

入力例 2

出力例 2

入力例 3

出力例 3

Score : 200 points

Problem Statement

You are given N strings of length six each, consisting of digits. Let S_i be the i-th (i = 1, 2, \dots, N) of them.

You are also given M strings of length three each, consisting of digits. Let T_j be the j-th (j = 1, 2, \dots, M) of them.

Find the number of strings among S_1, S_2, \dots, S_N whose last three characters coincide with one or more of T_1, T_2, \dots, T_M.

Constraints

1 \leq N, M \leq 1000
N and M are integers.
S_i is a string of length 6 consisting of digits, for all i = 1, 2, \dots, N.
T_j is a string of length 3 consisting of digits, for all j = 1, 2, \dots, M.

Input

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

N M
S_1
S_2
\vdots
S_N
T_1
T_2
\vdots
T_M

Output

Print the answer.

Sample Input 1

Sample Output 1

The last three characters of S_1 are 857, which coincide with T_3.
The last three characters of S_2 are 159, which coincide with T_1.
The last three characters of S_3 are 028, which do not coincide with T_1, T_2, or T_3.

Thus, the answer is 2.

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3

D - Minimize Abs 1

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

配点 : 200 点

問題文

長さ N の整数列 A=(A_1,A_2,\ldots,A_N) 及び整数 L,R が与えられます。ここで L,R は L\leq R を満たします。

i=1,2,\ldots,N について以下の 2 つの条件を共に満たす整数 X_i を求めてください。なお、求める整数は常に一意に定まります。

L\leq X_i \leq R
L 以上 R 以下であるようなどの整数 Y についても |X_i - A_i| \leq |Y-A_i| を満たす

制約

1\leq N\leq 2\times 10^5
1\leq L\leq R \leq 10^9
1\leq A_i\leq 10^9
入力は全て整数

入力

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

N L R
A_1 \ldots A_N

出力

i=1,2,\ldots,N について X_i を空白区切りで出力せよ。

入力例 1

5 4 7
3 1 4 9 7

出力例 1

4 4 4 7 7

i=1 では、

|4-3|=1
|5-3|=2
|6-3|=3
|7-3|=4

より X_i = 4 です。

入力例 2

3 10 10
11 10 9

出力例 2

10 10 10

Score : 200 points

Problem Statement

You are given an integer sequence A=(A_1,A_2,\ldots,A_N) of length N and integers L and R such that L\leq R.

For each i=1,2,\ldots,N, find the integer X_i that satisfies both of the following conditions. Note that the integer to be found is always uniquely determined.

L\leq X_i \leq R.
For every integer Y such that L \leq Y \leq R, it holds that |X_i - A_i| \leq |Y - A_i|.

Constraints

1\leq N\leq 2\times 10^5
1\leq L\leq R \leq 10^9
1\leq A_i\leq 10^9
All input values are integers.

Input

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

N L R
A_1 \ldots A_N

Output

Print X_i for i=1,2,\ldots,N, separated by spaces.

Sample Input 1

5 4 7
3 1 4 9 7

Sample Output 1

4 4 4 7 7

For i=1:

|4-3|=1
|5-3|=2
|6-3|=3
|7-3|=4

Thus, X_i = 4.

Sample Input 2

3 10 10
11 10 9

Sample Output 2

10 10 10

E - Keys

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

配点 : 300 点

問題文

あなたは N 本の鍵 1,2,\dots,N を持っています。
このうち何本かの鍵は正しい鍵で、それ以外はダミーの鍵です。

また、鍵を何本でも挿し込めるドアX があり、このドアX は正しい鍵を K 本以上挿し込んだ時、またその時に限って開きます。

あなたはこれらの鍵に対して M 回のテストを行いました。このうち i 回目のテストの内容は次の通りです。

C_i 本の鍵 A_{i,1},A_{i,2},\dots,A_{i,C_i} をドアX に挿し込む。
テスト結果はひとつの英文字 R_i で表現される。
- R_i = o のとき i 回目のテストでドアが開いたことを表す。
- R_i = x のとき i 回目のテストでドアが開かなかったことを表す。

各鍵が正しいかダミーかの組み合わせは 2^N 通り考えられますが、このうちどのテスト結果にも矛盾しない組み合わせの個数を求めてください。
ただし、与えられるテスト結果が誤っており上記の条件を満たす組み合わせが存在しない場合もあります。その場合は 0 通りと解答してください。

制約

N,M,K,C_i,A_{i,j} は整数
1 \le K \le N \le 15
1 \le M \le 100
1 \le C_i \le N
1 \le A_{i,j} \le N
j \neq k ならば A_{i,j} \neq A_{i,k}
R_i は o または x

入力

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

N M K
C_1 A_{1,1} A_{1,2} \dots A_{1,C_1} R_1
C_2 A_{2,1} A_{2,2} \dots A_{2,C_2} R_2
\vdots
C_M A_{M,1} A_{M,2} \dots A_{M,C_M} R_M

出力

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

入力例 1

3 2 2
3 1 2 3 o
2 2 3 x

出力例 1

この入力では鍵が 3 本あり、テストは 2 回行われました。
また、ドアX を開くのに必要な正しい鍵の本数は 2 本です。

1 回目のテストでは鍵 1,2,3 を使い、その結果ドアX は開きました。
2 回目のテストでは鍵 2,3 を使い、その結果ドアX は開きませんした。

各鍵が正しいかダミーかの組み合わせであって、どのテスト結果にも矛盾しないものは以下の 2 通りです。

鍵 1 は本物、鍵 2 はダミー、鍵 3 は本物である。
鍵 1 は本物、鍵 2 は本物、鍵 3 はダミーである。

入力例 2

4 5 3
3 1 2 3 o
3 2 3 4 o
3 3 4 1 o
3 4 1 2 o
4 1 2 3 4 x

出力例 2

問題文中でも述べた通り、答えが 0 通りである場合もあります。

入力例 3

11 4 9
10 1 2 3 4 5 6 7 8 9 10 o
11 1 2 3 4 5 6 7 8 9 10 11 o
10 11 10 9 8 7 6 5 4 3 2 x
10 11 9 1 4 3 7 5 6 2 10 x

出力例 3

Score : 300 points

Problem Statement

You have N keys numbered 1, 2, \dots, N.
Some of these are real keys, while the others are dummies.

There is a door, Door X, into which you can insert any number of keys. Door X will open if and only if at least K real keys are inserted.

You have conducted M tests on these keys. The i-th test went as follows:

You inserted C_i keys A_{i,1}, A_{i,2}, \dots, A_{i,C_i} into Door X.
The test result is represented by a single English letter R_i.
- R_i = o means that Door X opened in the i-th test.
- R_i = x means that Door X did not open in the i-th test.

There are 2^N possible combinations of which keys are real and which are dummies. Among these, find the number of combinations that do not contradict any of the test results.
It is possible that the given test results are incorrect and no combination satisfies the conditions. In such a case, report 0.

Constraints

N, M, K, C_i, and A_{i,j} are integers.
1 \le K \le N \le 15
1 \le M \le 100
1 \le C_i \le N
1 \le A_{i,j} \le N
A_{i,j} \neq A_{i,k} if j \neq k.
R_i is o or x.

Input

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

N M K
C_1 A_{1,1} A_{1,2} \dots A_{1,C_1} R_1
C_2 A_{2,1} A_{2,2} \dots A_{2,C_2} R_2
\vdots
C_M A_{M,1} A_{M,2} \dots A_{M,C_M} R_M

Output

Print the answer as an integer.

Sample Input 1

3 2 2
3 1 2 3 o
2 2 3 x

Sample Output 1

In this input, there are three keys and two tests were conducted.
Two correct keys are required to open Door X.

In the first test, keys 1, 2, 3 were used, and Door X opened.
In the second test, keys 2, 3 were used, and Door X did not open.

There are two combinations of which keys are real and which are dummies that do not contradict any of the test results:

Key 1 is real, key 2 is a dummy, and key 3 is real.
Key 1 is real, key 2 is real, and key 3 is a dummy.

Sample Input 2

4 5 3
3 1 2 3 o
3 2 3 4 o
3 3 4 1 o
3 4 1 2 o
4 1 2 3 4 x

Sample Output 2

As mentioned in the problem statement, the answer may be 0.

Sample Input 3

11 4 9
10 1 2 3 4 5 6 7 8 9 10 o
11 1 2 3 4 5 6 7 8 9 10 11 o
10 11 10 9 8 7 6 5 4 3 2 x
10 11 9 1 4 3 7 5 6 2 10 x