AtCoder Beginner Contest 097

A - Colorful Transceivers

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 100 点

問題文

数直線上にいるAさんとBさんとCさんがトランシーバーで会話をしようとしています。 Aさんは a [m] 地点、Bさんは b [m] 地点、Cさんは c [m] 地点にいます。二人の人間は、距離が d [m] 以内のとき直接会話が出来ます。 AさんとCさんが直接的、あるいは間接的に会話ができるか判定してください。ただしAさんとCさんが間接的に会話ができるとは、AさんとBさんが直接会話でき、かつBさんとCさんが直接会話できることを指します。

制約

1 ≤ a,b,c ≤ 100
1 ≤ d ≤ 100
入力は全て整数

入力

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

a b c d

出力

会話できるなら Yes を, できないなら No を出力せよ。

入力例 1

4 7 9 3

出力例 1

Yes

AさんとBさんは直接会話可能です。また、BさんとCさんも直接会話可能です。従って Yes を出力してください。

入力例 2

100 10 1 2

出力例 2

No

この場合は不可能です。

入力例 3

10 10 10 1

出力例 3

Yes

複数人が同じ場所にいることもあります。

入力例 4

1 100 2 10

出力例 4

Yes

Score : 100 points

Problem Statement

Three people, A, B and C, are trying to communicate using transceivers. They are standing along a number line, and the coordinates of A, B and C are a, b and c (in meters), respectively. Two people can directly communicate when the distance between them is at most d meters. Determine if A and C can communicate, either directly or indirectly. Here, A and C can indirectly communicate when A and B can directly communicate and also B and C can directly communicate.

Constraints

1 ≤ a,b,c ≤ 100
1 ≤ d ≤ 100
All values in input are integers.

Input

Input is given from Standard Input in the following format:

a b c d

Output

If A and C can communicate, print Yes; if they cannot, print No.

Sample Input 1

4 7 9 3

Sample Output 1

Yes

A and B can directly communicate, and also B and C can directly communicate, so we should print Yes.

Sample Input 2

100 10 1 2

Sample Output 2

No

They cannot communicate in this case.

Sample Input 3

10 10 10 1

Sample Output 3

Yes

There can be multiple people at the same position.

Sample Input 4

1 100 2 10

Sample Output 4

Yes

B - Exponential

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 200 点

問題文

正整数 X が与えられます。 X 以下の最大のべき乗数を求めてください。ただし、べき乗数とは、ある 1 以上の整数 b と 2 以上の整数 p を使って b^p とかける整数のことを指すこととします。

制約

1 ≤ X ≤ 1000
X は整数

入力

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

出力

X 以下の最大のべき乗数を出力せよ。

入力例 1

出力例 1

10 以下のべき乗数は 1,4,8,9 の 4 つです。この内最も大きい 9 を出力してください。

入力例 2

出力例 2

入力例 3

出力例 3

Score : 200 points

Problem Statement

You are given a positive integer X. Find the largest perfect power that is at most X. Here, a perfect power is an integer that can be represented as b^p, where b is an integer not less than 1 and p is an integer not less than 2.

Constraints

1 ≤ X ≤ 1000
X is an integer.

Input

Input is given from Standard Input in the following format:

Output

Print the largest perfect power that is at most X.

Sample Input 1

Sample Output 1

There are four perfect powers that are at most 10: 1, 4, 8 and 9. We should print the largest among them, 9.

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3

C - K-th Substring

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

文字列 s が与えられます。 s の異なる substring のうち、辞書順で K 番目に小さいものを出力してください。

ただし、s の substring とは、 s の空でない連続した部分を取り出してできる文字列とします。例えば、 s = ababc とすると、 a, bab, ababc は s の substring ですが、 ac, z, 空文字列は s の substring ではありません。また、substring が異なるとは、文字列として異なることを指します。

なお、X = x_{1}x_{2}...x_{n}, Y = y_{1}y_{2}...y_{m} を二つの異なる文字列とするとき、Y が X の接頭辞であるか、j を x_{j} \neq y_{j} であるような最小の整数として x_{j} > y_{j} である場合、そしてその場合に限って X は Y より辞書順で大きいといいます。

制約

1 ≤ |s| ≤ 5000
s は英小文字からなる
1 ≤ K ≤ 5
s は異なる substring を K 個以上持つ

部分点

|s| ≤ 50 を満たすデータセットに正解した場合は、部分点として 200 点が与えられる。

入力

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

s
K

出力

辞書順で K 番目に小さい s の substring を出力せよ。

入力例 1

aba
4

出力例 1

s の substring は a, b, ab, ba, aba の 5 つです。このうち 4 番目に小さい b を出力してください。 a を 2 回カウントしないことに注意してください。

入力例 2

atcoderandatcodeer
5

出力例 2

andat

入力例 3

z
1

出力例 3

Score : 300 points

Problem Statement

You are given a string s. Among the different substrings of s, print the K-th lexicographically smallest one.

A substring of s is a string obtained by taking out a non-empty contiguous part in s. For example, if s = ababc, a, bab and ababc are substrings of s, while ac, z and an empty string are not. Also, we say that substrings are different when they are different as strings.

Let X = x_{1}x_{2}...x_{n} and Y = y_{1}y_{2}...y_{m} be two distinct strings. X is lexicographically larger than Y if and only if Y is a prefix of X or x_{j} > y_{j} where j is the smallest integer such that x_{j} \neq y_{j}.

Constraints

1 ≤ |s| ≤ 5000
s consists of lowercase English letters.
1 ≤ K ≤ 5
s has at least K different substrings.

Partial Score

200 points will be awarded as a partial score for passing the test set satisfying |s| ≤ 50.

Input

Input is given from Standard Input in the following format:

s
K

Output

Print the K-th lexicographically smallest substring of K.

Sample Input 1

aba
4

Sample Output 1

s has five substrings: a, b, ab, ba and aba. Among them, we should print the fourth smallest one, b. Note that we do not count a twice.

Sample Input 2

atcoderandatcodeer
5

Sample Output 2

andat

Sample Input 3

z
1

Sample Output 3

D - Equals

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

1 から N までの整数を並び替えた順列 p_1, p_2, .., p_N があります。また、 1 以上 N 以下の整数のペアが M 個与えられます。これらは (x_1,y_1), (x_2,y_2), .., (x_M,y_M) で表されます。シカの AtCoDeer くんは順列 p に次の操作を好きなだけ行って、 p_i = i となる i (1 ≤ i ≤ N) の数を最大にしようと考えています。

1 ≤ j ≤ M なる j を選び、 p_{x_j} と p_{y_j} をスワップする

操作後の p_i = i となる i の数として考えうる最大値を求めてください。

制約

2 ≤ N ≤ 10^5
1 ≤ M ≤ 10^5
p は 1 から N までの整数を並び替えた順列
1 ≤ x_j,y_j ≤ N
x_j ≠ y_j
i ≠ j なら、 \{x_i,y_i\} ≠ \{x_j,y_j\}
入力は全て整数

入力

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

N M
p_1 p_2 .. p_N
x_1 y_1
x_2 y_2
:
x_M y_M

出力

操作後の p_i = i となる i (1 ≤ i ≤ N) の数として考えうる最大値を出力せよ。

入力例 1

出力例 1

j=1 を選んで操作すると、 p は 1 3 5 4 2 となり、これがベストなので答えは 2 です。

入力例 2

出力例 2

例えば j=1, j=2, j=1 の順に操作すると、 p は 1 2 3 となり明らかにこれがベストです。同じ j を何回選んでもいいことに注意してください。

入力例 3

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

出力例 3

入力例 4

5 1
1 2 3 4 5
1 5

出力例 4

操作をする必要はありません。

Score : 400 points

Problem Statement

We have a permutation of the integers from 1 through N, p_1, p_2, .., p_N. We also have M pairs of two integers between 1 and N (inclusive), represented as (x_1,y_1), (x_2,y_2), .., (x_M,y_M). AtCoDeer the deer is going to perform the following operation on p as many times as desired so that the number of i (1 ≤ i ≤ N) such that p_i = i is maximized:

Choose j such that 1 ≤ j ≤ M, and swap p_{x_j} and p_{y_j}.

Find the maximum possible number of i such that p_i = i after operations.

Constraints

2 ≤ N ≤ 10^5
1 ≤ M ≤ 10^5
p is a permutation of integers from 1 through N.
1 ≤ x_j,y_j ≤ N
x_j ≠ y_j
If i ≠ j, \{x_i,y_i\} ≠ \{x_j,y_j\}.
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
p_1 p_2 .. p_N
x_1 y_1
x_2 y_2
:
x_M y_M

Output

Print the maximum possible number of i such that p_i = i after operations.

Sample Input 1

Sample Output 1

If we perform the operation by choosing j=1, p becomes 1 3 5 4 2, which is optimal, so the answer is 2.

Sample Input 2

Sample Output 2

If we perform the operation by, for example, choosing j=1, j=2, j=1 in this order, p becomes 1 2 3, which is obviously optimal. Note that we may choose the same j any number of times.

Sample Input 3

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

Sample Output 3

Sample Input 4

5 1
1 2 3 4 5
1 5

Sample Output 4

We do not have to perform the operation.