AtCoder Daily Training EASY 2026/08/27 18:00start

A - Full House 2

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

配点 : 100 点

問題文

4 枚のカードがあり、それぞれのカードには整数 A,B,C,D が書かれています。
ここに 1 枚カードを加え、フルハウスとできるか判定してください。

ただし、 5 枚組のカードは以下の条件を満たすとき、またそのときに限って、フルハウスであると呼ばれます。

異なる整数 x,y について、 x が書かれたカード 3 枚と y が書かれたカード 2 枚からなる。

制約

入力は全て整数
1 \le A,B,C,D \le 13

入力

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

A B C D

出力

1 枚カードを加えてフルハウスとできる場合は Yes 、そうでないときは No と出力せよ。

入力例 1

7 7 7 1

出力例 1

Yes

7,7,7,1 に 1 を加えた時、フルハウスとなります。

入力例 2

13 12 11 10

出力例 2

No

13,12,11,10 に何を加えてもフルハウスにはなりません。

入力例 3

3 3 5 5

出力例 3

Yes

3,3,5,5 に 3 を加えた時、フルハウスとなります。
また、 5 を加えてもフルハウスとなります。

入力例 4

8 8 8 8

出力例 4

No

8,8,8,8 に何を加えてもフルハウスにはなりません。
同じ 5 枚のカードはフルハウスではないことに注意してください。

入力例 5

1 3 4 1

出力例 5

No

Score : 100 points

Problem Statement

There are four cards with integers A,B,C,D written on them.
Determine whether a Full House can be formed by adding one card.

A set of five cards is called a Full House if and only if the following condition is satisfied:

For two distinct integers x and y, there are three cards with x written on them and two cards with y written on them.

Constraints

All input values are integers.
1 \le A,B,C,D \le 13

Input

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

A B C D

Output

If adding one card can form a Full House, print Yes; otherwise, print No.

Sample Input 1

7 7 7 1

Sample Output 1

Yes

Adding 1 to 7,7,7,1 forms a Full House.

Sample Input 2

13 12 11 10

Sample Output 2

No

Adding anything to 13,12,11,10 does not form a Full House.

Sample Input 3

3 3 5 5

Sample Output 3

Yes

Adding 3,3,5,5 to 3 forms a Full House.
Also, adding 5 forms a Full House.

Sample Input 4

8 8 8 8

Sample Output 4

No

Adding anything to 8,8,8,8 does not form a Full House.
Note that five identical cards do not form a Full House.

Sample Input 5

1 3 4 1

Sample Output 5

No

B - Count Down

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

配点 : 100 点

問題文

N 以下の非負整数を大きい方から順にすべて出力してください。

制約

1 \leq N \leq 100
N は整数

入力

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

出力

N 以下の非負整数が X 個存在するとき、X 行出力せよ。
i=1,2,\ldots,X に対し、i 行目には N 以下の非負整数のうち大きい方から i 番目のものを出力せよ。

入力例 1

出力例 1

3 以下の非負整数は 0,1,2,3 の 4 個です。
1 行目に 3 を、2 行目に 2 を、3 行目に 1 を、4 行目に 0 を出力することでこれらを大きい方から順に出力したことになります。

入力例 2

出力例 2

Score : 100 points

Problem Statement

Print all non-negative integers less than or equal to N in descending order.

Constraints

1 \leq N \leq 100
N is an integer.

Input

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

Output

Print X lines, where X is the number of non-negative integers less than or equal to N.
For each i=1, 2, \ldots, X, the i-th line should contain the i-th greatest non-negative integer less than or equal to N.

Sample Input 1

Sample Output 1

We have four non-negative integers less than or equal to 3, which are 0, 1, 2, and 3.
To print them in descending order, print 3 in the first line, 2 in the second, 1 in the third, and 0 in the fourth.

Sample Input 2

Sample Output 2

C - Triple Metre

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

配点 : 200 点

問題文

文字列 S が文字列 T の部分文字列であるとは、次の条件を満たすような整数 i, j (1 \leq i \leq j \leq |T|) が存在することを言います。

T の i 文字目から j 文字目までを順番を変えずに抜き出してできる文字列が S と一致する。

文字列 T を oxx を 10^5 個結合した文字列として定めます。
文字列 S が与えられるので、 S が T の部分文字列である場合は Yes を、そうでない場合は No を出力してください。

制約

S は o と x のみからなる文字列である。
S の長さは 1 以上 10 以下である。

入力

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

出力

S が条件を満たす場合は Yes を、そうでない場合は No を出力せよ。

入力例 1

xoxxoxxo

出力例 1

Yes

T のはじめの方を抜き出すと oxxoxxoxxoxx... となっています。
T の 3 文字目から 10 文字目までを抜き出した文字列は S と一致するので、 S は T の部分文字列です。よって Yes を出力します。

入力例 2

xxoxxoxo

出力例 2

No

T から文字列をどのように抜き出しても S と一致しないので、S は T の部分文字列でありません。よって No を出力します。

入力例 3

ox

出力例 3

Yes

Score : 200 points

Problem Statement

A string S is said to be a substring of a string T when there is a pair of integers i and j (1 \leq i \leq j \leq |T|) that satisfy the following condition.

The extraction of the i-th through j-th characters of T without changing the order equals S.

Let T be the concatenation of 10^5 copies of oxx.
Given a string S, print Yes if S is a substring of T, and No otherwise.

Constraints

S is a string consisting of o and x.
The length of S is between 1 and 10 (inclusive).

Input

Input is given from Standard Input in the following format:

Output

If S satisfies the condition, print Yes; otherwise, print No.

Sample Input 1

xoxxoxxo

Sample Output 1

Yes

T begins like this: oxxoxxoxxoxx... Since the extraction of 3-rd through 10-th characters of T equals S, S is a substring of T, so Yes should be printed.

Sample Input 2

xxoxxoxo

Sample Output 2

No

Since there is no way to extract from T a string that equals S, S is not a substring of T, so No should be printed.

Sample Input 3

ox

Sample Output 3

Yes

D - Count Distinct Integers

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

配点 : 200 点

問題文

長さ N の正整数列 a = (a_1, a_2, \dots, a_N) には何種類の整数が現れますか？

制約

1 \leq N \leq 1000
1 \leq a_i \leq 10^9 \, (1 \leq i \leq N)
入力は全て整数

入力

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

N
a_1 \ldots a_N

出力

答えを出力せよ。

入力例 1

6
1 4 1 2 2 1

出力例 1

1, 2, 4 の 3 種類の整数が現れます。

入力例 2

1
1

出力例 2

入力例 3

11
3 1 4 1 5 9 2 6 5 3 5

出力例 3

Score : 200 points

Problem Statement

In a sequence of N positive integers a = (a_1, a_2, \dots, a_N), how many different integers are there?

Constraints

1 \leq N \leq 1000
1 \leq a_i \leq 10^9 \, (1 \leq i \leq N)
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
a_1 \ldots a_N

Output

Print the answer.

Sample Input 1

6
1 4 1 2 2 1

Sample Output 1

There are three different integers: 1, 2, 4.

Sample Input 2

1
1

Sample Output 2

Sample Input 3

11
3 1 4 1 5 9 2 6 5 3 5

Sample Output 3

E - Fishbones

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

配点 : 300 点

問題文

アーティストの高砂君は、魚の骨をかたどったオブジェを作りました。

オブジェは N 本の肋骨と 1 本の脊椎からなります。肋骨には 1 から N までの番号が付けられています。

高砂君は、以下の条件をすべて満たすように N+1 本の骨に 1 つずつ文字列を書こうと考えています。

脊椎に書く文字列の長さは N である。
肋骨 i = 1, \dots, N に対して、以下が成り立つ。
- 肋骨 i に書く文字列の長さは A_i である。
- 肋骨 i に書く文字列の B_i 文字目は、脊椎に書く文字列の i 文字目に一致する。
N+1 本の骨に書く文字列はいずれも、S_1, \cdots, S_M のいずれかである(重複してもよい)。

S_1, \cdots, S_M は英小文字からなる文字列であり、互いに異なります。

j = 1, \cdots, M に対して、以下の質問に答えてください。

条件を満たす書き方のうち、脊椎に書く文字列が S_j であるものは存在しますか？

制約

N は整数
1 \leq N \leq 10
A_i, B_i は整数 (1 \leq i \leq N)
1 \leq B_i \leq A_i \leq 10 (1 \leq i \leq N)
M は整数
1 \leq M \leq 200\,000
S_j は英小文字からなる文字列 (1 \leq j \leq M)
1 \leq |S_j| \leq 10 (1 \leq j \leq M)
S_1, \cdots, S_M は相異なる

入力

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

N
A_1 B_1
\vdots
A_N B_N
M
S_1
\vdots
S_M

出力

M 行出力せよ。

j 行目 (1 \leq j \leq M) には、条件を満たす書き方のうち脊椎に書く文字列が S_j のものが存在するならば Yes を、存在しないならば No を出力せよ。

入力例 1

5
5 3
5 2
4 1
5 1
3 2
8
retro
chris
itchy
tuna
crab
rock
cod
ash

出力例 1

Yes
Yes
No
No
No
No
No
No

肋骨 1,2,3,4,5 にそれぞれ chris, retro, tuna, retro, cod と書くことで、脊椎に retro を書いたときに条件を満たします。

retro の長さは 5 文字。
各肋骨について、以下が成り立つ。
- 肋骨 1 に書かれる文字列 chris の長さは 5 文字である。その 3 文字目は r であり、retro の 1 文字目に一致する。
- 肋骨 2 に書かれる文字列 retro の長さは 5 文字である。その 2 文字目は e であり、retro の 2 文字目に一致する。
- 肋骨 3 に書かれる文字列 tuna の長さは 4 文字である。その 1 文字目は t であり、retro の 3 文字目に一致する。
- 肋骨 4 に書かれる文字列 retro の長さは 5 文字である。その 1 文字目は r であり、retro の 4 文字目に一致する。
- 肋骨 5 に書かれる文字列 cod の長さは 3 文字である。その 2 文字目は o であり、retro の 5 文字目に一致する。

肋骨 1,2,3,4,5 にそれぞれ itchy, chris, rock, itchy, ash と書くことで、脊椎に chris を書いたときに条件を満たします。

入力例 2

5
5 1
5 2
5 3
5 4
5 5
8
retro
chris
itchy
tuna
crab
rock
cod
ash

出力例 2

Yes
Yes
Yes
No
No
No
No
No

Score : 300 points

Problem Statement

Artist Takasago has created an object in the shape of a fish skeleton.

The object consists of N ribs and one spine. The ribs are numbered 1 through N.

He wants to write one string on each of the N+1 bones, satisfying all of the following conditions.

The length of the string written on the spine is N.
For each rib i = 1, \dots, N, the following hold.
- The length of the string written on rib i is A_i.
- The B_i-th character of the string written on rib i equals the i-th character of the string written on the spine.
Each of the strings written on the N+1 bones is one of S_1, \cdots, S_M (duplicates allowed).

S_1, \cdots, S_M are strings consisting of lowercase English letters, and they are all distinct.

For each j = 1, \cdots, M, answer the following question.

Among the ways to write strings satisfying the conditions, is there one where the string written on the spine is S_j?

Constraints

N is an integer.
1 \leq N \leq 10
A_i and B_i are integers. (1 \leq i \leq N)
1 \leq B_i \leq A_i \leq 10 (1 \leq i \leq N)
M is an integer.
1 \leq M \leq 200\,000
S_j is a string consisting of lowercase English letters. (1 \leq j \leq M)
1 \leq |S_j| \leq 10 (1 \leq j \leq M)
S_1, \cdots, S_M are pairwise distinct.

Input

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

N
A_1 B_1
\vdots
A_N B_N
M
S_1
\vdots
S_M

Output

Output M lines.

The j-th line (1 \leq j \leq M) should contain Yes if there exists a way to write strings satisfying the conditions with S_j written on the spine, and No otherwise.

Sample Input 1

5
5 3
5 2
4 1
5 1
3 2
8
retro
chris
itchy
tuna
crab
rock
cod
ash

Sample Output 1

Yes
Yes
No
No
No
No
No
No

By writing chris, retro, tuna, retro, cod on ribs 1,2,3,4,5 respectively, the conditions are satisfied with retro written on the spine.

The length of retro is 5.
For each rib, the following hold.
- The string written on rib 1 is chris, which has length 5. Its third character is r, which equals the first character of retro.
- The string written on rib 2 is retro, which has length 5. Its second character is e, which equals the second character of retro.
- The string written on rib 3 is tuna, which has length 4. Its first character is t, which equals the third character of retro.
- The string written on rib 4 is retro, which has length 5. Its first character is r, which equals the fourth character of retro.
- The string written on rib 5 is cod, which has length 3. Its second character is o, which equals the fifth character of retro.

By writing itchy, chris, rock, itchy, ash on ribs 1,2,3,4,5 respectively, the conditions are satisfied with chris written on the spine.

Sample Input 2

5
5 1
5 2
5 3
5 4
5 5
8
retro
chris
itchy
tuna
crab
rock
cod
ash

Sample Output 2

Yes
Yes
Yes
No
No
No
No
No