AtCoder Daily Training EASY 2024/05/16 20:30start

A - Digit Machine

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

1 桁の数字が表示される画面と、ボタンからなる機械があります。

画面に数字 k が表示されているとき、ボタンを 1 回押すと画面の数字が a_k に変わります。

0 が表示されている状態からボタンを 3 回押すと、画面には何が表示されますか？

制約

0\leq a_i \leq 9
入力は全て整数である

入力

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

a_0 a_1 \dots a_9

出力

答えを出力せよ。

入力例 1

9 0 1 2 3 4 5 6 7 8

出力例 1

画面に表示される数字は、0 \rightarrow 9 \rightarrow 8 \rightarrow 7 と変化します。

入力例 2

4 8 8 8 0 8 8 8 8 8

出力例 2

画面に表示される数字は、0 \rightarrow 4 \rightarrow 0 \rightarrow 4 と変化します。

入力例 3

0 0 0 0 0 0 0 0 0 0

出力例 3

Score : 100 points

Problem Statement

There is a device with a screen that shows a single-digit number, and a button.

When the screen is showing a number k, pressing the button once changes the number on the screen to a_k.

The device currently shows 0. After pressing the button 3 times, what will be shown on the screen?

Constraints

0\leq a_i \leq 9
All values in input are integers.

Input

Input is given from Standard Input in the following format:

a_0 a_1 \dots a_9

Output

Print the answer.

Sample Input 1

9 0 1 2 3 4 5 6 7 8

Sample Output 1

The number on the screen transitions as 0 \rightarrow 9 \rightarrow 8 \rightarrow 7.

Sample Input 2

4 8 8 8 0 8 8 8 8 8

Sample Output 2

The number on the screen transitions as 0 \rightarrow 4 \rightarrow 0 \rightarrow 4.

Sample Input 3

0 0 0 0 0 0 0 0 0 0

Sample Output 3

B - Similar String

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

二つの文字 x と y は以下の 3 つの条件のうちどれか 1 つを満たすとき、似た文字と呼ばれます。

x と y は同じ文字
x と y の片方が 1 で、もう片方が l
x と y の片方が 0 で、もう片方が o

また、長さ N の文字列 S と T は以下の条件を満たすとき、似た文字列と呼ばれます。

任意の i\ (1\leq i\leq N) について、 S の i 番目の文字と T の i 番目の文字は似た文字

英小文字及び数字からなる長さ N の文字列 S,T が与えられます。 S と T が似た文字列か判定してください。

制約

N は 1 以上 100 以下の整数
S,T は英小文字及び数字からなる長さ N の文字列

入力

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

N
S
T

出力

S と T が似た文字列の場合 Yes を、そうでない場合 No を出力せよ。

入力例 1

3
l0w
1ow

出力例 1

Yes

S の 1 文字目は lで、T の 1 文字目は 1です。これらは似た文字です。

S の 2 文字目は 0で、T の 2 文字目は oです。これらは似た文字です。

S の 3 文字目は wで、T の 3 文字目は wです。これらは似た文字です。

よって S と T は似た文字列です。

入力例 2

3
abc
arc

出力例 2

No

S の 2 文字目は bで、T の 2 文字目は rです。これらは似た文字ではありません。

よって S と T は似た文字列ではありません。

入力例 3

4
nok0
n0ko

出力例 3

Yes

Score : 100 points

Problem Statement

Two characters x and y are called similar characters if and only if one of the following conditions is satisfied:

x and y are the same character.
One of x and y is 1 and the other is l.
One of x and y is 0 and the other is o.

Two strings S and T, each of length N, are called similar strings if and only if:

for all i\ (1\leq i\leq N), the i-th character of S and the i-th character of T are similar characters.

Given two length-N strings S and T consisting of lowercase English letters and digits, determine if S and T are similar strings.

Constraints

N is an integer between 1 and 100.
Each of S and T is a string of length N consisting of lowercase English letters and digits.

Input

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

N
S
T

Output

Print Yes if S and T are similar strings, and No otherwise.

Sample Input 1

3
l0w
1ow

Sample Output 1

Yes

The 1-st character of S is l, and the 1-st character of T is 1. These are similar characters.

The 2-nd character of S is 0, and the 2-nd character of T is o. These are similar characters.

The 3-rd character of S is w, and the 3-rd character of T is w. These are similar characters.

Thus, S and T are similar strings.

Sample Input 2

3
abc
arc

Sample Output 2

No

The 2-nd character of S is b, and the 2-nd character of T is r. These are not similar characters.

Thus, S and T are not similar strings.

Sample Input 3

4
nok0
n0ko

Sample Output 3

Yes

C - MissingNo.

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

ナオヒロ君は N+1 個の連続する整数を 1 個ずつ持っていましたが、そのうち 1 個をなくしてしまいました。

残っている N 個の整数が順不同で A_1,\ldots,A_N として与えられるので、なくした整数を求めてください。

なお、なくした整数が一意に定まるような入力のみが与えられます。

制約

2 \leq N \leq 100
1 \leq A_i \leq 1000
入力は全て整数である
なくした整数は一意に定まる

入力

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

N
A_1 A_2 \ldots A_N

出力

答えを出力せよ。

入力例 1

3
2 3 5

出力例 1

ナオヒロ君は初め 2,3,4,5 の 4 個の整数を持っており、4 をなくし、2,3,5 が残っていました。

なくした整数である 4 を出力します。

入力例 2

8
3 1 4 5 9 2 6 8

出力例 2

入力例 3

16
152 153 154 147 148 149 158 159 160 155 156 157 144 145 146 150

出力例 3

Score : 200 points

Problem Statement

Naohiro had N+1 consecutive integers, one of each, but he lost one of them.

The remaining N integers are given in arbitrary order as A_1,\ldots,A_N. Find the lost integer.

The given input guarantees that the lost integer is uniquely determined.

Constraints

2 \leq N \leq 100
1 \leq A_i \leq 1000
All input values are integers.
The lost integer is uniquely determined.

Input

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

N
A_1 A_2 \ldots A_N

Output

Print the answer.

Sample Input 1

3
2 3 5

Sample Output 1

Naohiro originally had four integers, 2,3,4,5, then lost 4, and now has 2,3,5.

Print the lost integer, 4.

Sample Input 2

8
3 1 4 5 9 2 6 8

Sample Output 2

Sample Input 3

16
152 153 154 147 148 149 158 159 160 155 156 157 144 145 146 150

Sample Output 3

D - Qualification Contest

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

N 人の人があるコンテストに参加し、i 位の人のハンドルネームは S_i でした。
上位 K 人のハンドルネームを辞書順に出力してください。

辞書順とは？

辞書順とは簡単に説明すると「単語が辞書に載っている順番」を意味します。より厳密な説明として、相異なる文字列 S と文字列 T の大小を判定するアルゴリズムを以下に説明します。

以下では「 S の i 文字目の文字」を S_i のように表します。また、 S が T より辞書順で小さい場合は S \lt T 、大きい場合は S \gt T と表します。

S と T のうち長さが短い方の文字列の長さを L とします。i=1,2,\dots,L に対して S_i と T_i が一致するか調べます。
S_i \neq T_i である i が存在する場合、そのような i のうち最小のものを j とします。そして、S_j と T_j を比較して、 S_j がアルファベット順で T_j より小さい場合は S \lt T 、大きい場合は S \gt T と決定して、アルゴリズムを終了します。
S_i \neq T_i である i が存在しない場合、 S と T の長さを比較して、S が T より短い場合は S \lt T 、長い場合は S \gt T と決定して、アルゴリズムを終了します。

制約

1 \leq K \leq N \leq 100
K, N は整数
S_i は英小文字からなる長さ 10 以下の文字列
i \neq j ならば S_i \neq S_j

入力

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

N K
S_1
S_2
\vdots
S_N

出力

答えを改行区切りで出力せよ。

入力例 1

5 3
abc
aaaaa
xyz
a
def

出力例 1

aaaaa
abc
xyz

このコンテストには 5 人が参加し、1 位の人のハンドルネームは abc 、2 位の人のハンドルネームは aaaaa 、3 位の人のハンドルネームは xyz 、4 位の人のハンドルネームは a 、5 位の人のハンドルネームは def でした。

上位 3 人のハンドルネームは abc、aaaaa、xyz であるため、これを辞書順に並べ替えて aaaaa 、abc 、xyz の順に出力します。

入力例 2

4 4
z
zyx
zzz
rbg

出力例 2

rbg
z
zyx
zzz

入力例 3

3 1
abc
arc
agc

出力例 3

abc

Score : 200 points

Problem Statement

There were N participants in a contest. The participant ranked i-th had the nickname S_i.
Print the nicknames of the top K participants in lexicographical order.

What is lexicographical order?

Simply put, the lexicographical order is the order of words in a dictionary. As a formal description, below is an algorithm to order distinct strings S and T.

Let S_i denote the i-th character of a string S. We write S \lt T if S is lexicographically smaller than T, and S \gt T if S is larger.

Let L be the length of the shorter of S and T. For i=1,2,\dots,L, check whether S_i equals T_i.
If there is an i such that S_i \neq T_i, let j be the smallest such i. Compare S_j and T_j. If S_j is alphabetically smaller than T_j, we get S \lt T; if S_j is larger, we get S \gt T.
If there is no i such that S_i \neq T_i, compare the lengths of S and T. If S is shorter than T, we get S \lt T; if S is longer, we get S \gt T.

Constraints

1 \leq K \leq N \leq 100
K and N are integers.
S_i is a string of length 10 consisting of lowercase English letters.
S_i \neq S_j if i \neq j.

Input

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

N K
S_1
S_2
\vdots
S_N

Output

Print the nicknames, separated by newlines.

Sample Input 1

5 3
abc
aaaaa
xyz
a
def

Sample Output 1

aaaaa
abc
xyz

This contest had five participants. The participants ranked first, second, third, fourth, and fifth had the nicknames abc, aaaaa, xyz, a, and def, respectively.

The nicknames of the top three participants were abc, aaaaa, xyz, so print these in lexicographical order: aaaaa, abc, xyz.

Sample Input 2

4 4
z
zyx
zzz
rbg

Sample Output 2

rbg
z
zyx
zzz

Sample Input 3

3 1
abc
arc
agc

Sample Output 3

abc

E - Find it!

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 350 点

問題文

N 頂点 N 辺の有向グラフがあります。
i 番目の辺は頂点 i から頂点 A_i に伸びます。 ( i \neq A_i であることは制約より保証されます )
同一頂点を複数回含まない有向閉路をひとつ求めてください。
なお、この問題の制約下で答えが存在することが示せます。

注釈

この問題では、有向閉路とは以下の条件を全て満たす頂点の列 B=(B_1,B_2,\dots,B_M) であるとします。

M \ge 2
B_i から B_{i+1} に辺が伸びている。 ( 1 \le i \le M-1 )
B_M から B_1 に辺が伸びている。
i \neq j ならば B_i \neq B_j

制約

入力は全て整数
2 \le N \le 2 \times 10^5
1 \le A_i \le N
A_i \neq i

入力

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

N
A_1 A_2 \dots A_N

出力

以下の形式で出力せよ。

M
B_1 B_2 \dots B_M

M は出力する有向閉路の頂点数であり、 B_i は有向閉路の i 番目の頂点である。
出力は以下の条件を満たす必要がある。

2 \le M
B_{i+1} = A_{B_i} ( 1 \le i \le M-1 )
B_{1} = A_{B_M}
B_i \neq B_j ( i \neq j )

答えとして考えられるものが複数ある場合、どれを出力しても正解となる。

入力例 1

7
6 7 2 1 3 4 5

出力例 1

4
7 5 3 2

7 \rightarrow 5 \rightarrow 3 \rightarrow 2 \rightarrow 7 は確かに有向閉路になっています。

この入力に対応するグラフは以下の通りです。

他の正解となる出力の例は以下の通りです。

4
2 7 5 3

3
4 1 6

グラフが連結であるとは限らないことに注意してください。

入力例 2

2
2 1

出力例 2

2
1 2

1 \rightarrow 2 と 2 \rightarrow 1 の辺が双方存在するケースです。
この場合、 1 \rightarrow 2 \rightarrow 1 は確かに有向閉路になっています。

この入力に対応するグラフは以下の通りです。
図中 1 \leftrightarrow 2 で 1 \rightarrow 2 と 2 \rightarrow 1 の辺が双方あることを表現しています。

入力例 3

8
3 7 4 7 3 3 8 2

出力例 3

3
2 7 8

この入力に対応するグラフは以下の通りです。

Score : 350 points

Problem Statement

There is a directed graph with N vertices and N edges.
The i-th edge goes from vertex i to vertex A_i. (The constraints guarantee that i \neq A_i.)
Find a directed cycle without the same vertex appearing multiple times.
It can be shown that a solution exists under the constraints of this problem.

Notes

The sequence of vertices B = (B_1, B_2, \dots, B_M) is called a directed cycle when all of the following conditions are satisfied:

M \geq 2
The edge from vertex B_i to vertex B_{i+1} exists. (1 \leq i \leq M-1)
The edge from vertex B_M to vertex B_1 exists.
If i \neq j, then B_i \neq B_j.

Constraints

All input values are integers.
2 \le N \le 2 \times 10^5
1 \le A_i \le N
A_i \neq i

Input

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

N
A_1 A_2 \dots A_N

Output

Print a solution in the following format:

M
B_1 B_2 \dots B_M

M is the number of vertices, and B_i is the i-th vertex in the directed cycle.
The following conditions must be satisfied:

2 \le M
B_{i+1} = A_{B_i} ( 1 \le i \le M-1 )
B_{1} = A_{B_M}
B_i \neq B_j ( i \neq j )

If multiple solutions exist, any of them will be accepted.

Sample Input 1

7
6 7 2 1 3 4 5

Sample Output 1

4
7 5 3 2

7 \rightarrow 5 \rightarrow 3 \rightarrow 2 \rightarrow 7 is indeed a directed cycle.

Here is the graph corresponding to this input:

Here are other acceptable outputs:

4
2 7 5 3

3
4 1 6

Note that the graph may not be connected.

Sample Input 2

2
2 1

Sample Output 2

2
1 2

This case contains both of the edges 1 \rightarrow 2 and 2 \rightarrow 1.
In this case, 1 \rightarrow 2 \rightarrow 1 is indeed a directed cycle.

Here is the graph corresponding to this input, where 1 \leftrightarrow 2 represents the existence of both 1 \rightarrow 2 and 2 \rightarrow 1:

Sample Input 3

8
3 7 4 7 3 3 8 2

Sample Output 3

3
2 7 8

Here is the graph corresponding to this input: