AtCoder Daily Training EASY 2024/01/17 16:00start

A - Legendary Players

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

配点 : 100 点

問題文

AtCoder では、レーティング上位 10 人のハンドルネームには金色の冠が、上位 1 人のハンドルネームには白金色の冠が表示されます。

このコンテストが開始した時点で、アルゴリズム部門での上位 10 人に入っているプレイヤーのハンドルネームとレーティングは以下のようになっています。

tourist 3858
ksun48 3679
Benq 3658
Um_nik 3648
apiad 3638
Stonefeang 3630
ecnerwala 3613
mnbvmar 3555
newbiedmy 3516
semiexp 3481

上記のプレイヤーのハンドルネーム S が与えられるので、その人のレーティングを出力してください。

制約

S はアルゴリズム部門でレーティング上位 10 人に入っているプレイヤーのハンドルネームのいずれかと等しい。

入力

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

出力

対応するプレイヤーのレーティングを 1 行で出力せよ。

入力例 1

tourist

出力例 1

このコンテストが開始した時点において、 tourist さんのアルゴリズム部門のレーティングは 3858 です。

入力例 2

semiexp

出力例 2

このコンテストが開始した時点において、 semiexp さんのアルゴリズム部門のレーティングは 3481 です。

Score : 100 points

Problem Statement

In AtCoder, the top 10 rated players' usernames are displayed with a gold crown, and the top-rated player's username is displayed with a platinum crown.

At the start of this contest, the usernames and ratings of the top 10 rated players in the algorithm category are as follows:

tourist 3858
ksun48 3679
Benq 3658
Um_nik 3648
apiad 3638
Stonefeang 3630
ecnerwala 3613
mnbvmar 3555
newbiedmy 3516
semiexp 3481

You are given the username S of one of these players. Print that player's rating.

Constraints

S is equal to one of the usernames of the top 10 rated players in the algorithm category.

Input

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

Output

Print the rating of the corresponding player in one line.

Sample Input 1

tourist

Sample Output 1

At the start of this contest, the rating of tourist in the algorithm category is 3858.

Sample Input 2

semiexp

Sample Output 2

At the start of this contest, the rating of semiexp in the algorithm category is 3481.

B - Tires

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

配点 : 100 点

問題文

末尾が er または ist であるような文字列 S が与えられます。
S の末尾が er である場合は er を、 ist である場合は ist を出力してください。

制約

2 \le |S| \le 20
S は英小文字のみからなる。
S の末尾は er または ist である。

入力

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

出力

答えを出力せよ。

入力例 1

atcoder

出力例 1

er

S="atcoder" の末尾は er です。

入力例 2

tourist

出力例 2

ist

入力例 3

er

出力例 3

er

Score : 100 points

Problem Statement

You are given a string S ending with er or ist.
If S ends with er, print er; if it ends with ist, print ist.

Constraints

2 \le |S| \le 20
S consists of lowercase English letters.
S ends with er or ist.

Input

Input is given from Standard Input in the following format:

Output

Print the answer.

Sample Input 1

atcoder

Sample Output 1

er

S="atcoder" ends with er.

Sample Input 2

tourist

Sample Output 2

ist

Sample Input 3

er

Sample Output 3

er

C - Number Box

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

配点 : 200 点

問題文

正整数 N が与えられます。

N 行 N 列のマス目があり、上から i 行目、左から j 列目のマスには数字 A_{i,j} が書かれています。

このマス目は上下および左右がつながっているものとします。つまり以下が全て成り立ちます。

(1,i) の上のマスは (N,i) であり、(N,i) の下のマスは (1,i) である。(1\le i\le N)
(i,1) の左のマスは (i,N) であり、(i,N) の右のマスは (i,1) である。(1\le i\le N)

高橋君は、上下左右および斜めの 8 方向のうちいずれかを初めに選びます。そして、好きなマスから決めた方向に 1 マス移動することを N-1 回繰り返します。

高橋君は N 個のマス上を移動することになりますが、高橋君が通ったマスに書かれている数字を左から通った順番に並べた整数としてあり得る最大のものを求めてください。

制約

1 \le N \le 10
1 \le A_{i,j} \le 9
入力はすべて整数。

入力

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

N
A_{1,1}A_{1,2}\dots A_{1,N}
A_{2,1}A_{2,2}\dots A_{2,N}
\vdots
A_{N,1}A_{N,2}\dots A_{N,N}

出力

答えを出力せよ。

入力例 1

出力例 1

高橋君が上から 2 行目、左から 4 列目のマスから出発し、右下に進むことで、通ったマスに書かれた数字を並べ 9786 を作ることができます。 9786 より大きい値を作ることはできないため、9786 が解です。

入力例 2

出力例 2

1111111111

32bit整数型に答えが収まるとは限らないことに注意してください。

Score : 200 points

Problem Statement

You are given a positive integer N.

We have a grid with N rows and N columns, where the square at the i-th row from the top and j-th column from the left has a digit A_{i,j} written on it.

Assume that the upper and lower edges of this grid are connected, as well as the left and right edges. In other words, all of the following holds.

(N,i) is just above (1,i), and (1,i) is just below (N,i). (1\le i\le N).
(i,N) is just to the left of (i,1), and (i,1) is just to the right of (i,N). (1\le i\le N).

Takahashi will first choose one of the following eight directions: up, down, left, right, and the four diagonal directions. Then, he will start on a square of his choice and repeat moving one square in the chosen direction N-1 times.

In this process, Takahashi visits N squares. Find the greatest possible value of the integer that is obtained by arranging the digits written on the squares visited by Takahashi from left to right in the order visited by him.

Constraints

1 \le N \le 10
1 \le A_{i,j} \le 9
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_{1,1}A_{1,2}\dots A_{1,N}
A_{2,1}A_{2,2}\dots A_{2,N}
\vdots
A_{N,1}A_{N,2}\dots A_{N,N}

Output

Print the answer.

Sample Input 1

Sample Output 1

If Takahashi starts on the square at the 2-nd row from the top and 4-th column from the left and goes down and to the right, the integer obtained by arranging the digits written on the visited squares will be 9786. It is impossible to make a value greater than 9786, so the answer is 9786.

Sample Input 2

Sample Output 2

1111111111

Note that the answer may not fit into a 32-bit integer.

D - Takahashi's Failure

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

配点 : 200 点

問題文

高橋君の家には N 個の食品があり、i 番目の食品のおいしさは A_i です。
また、高橋君には嫌いな食品が K 個あり、具体的には i=1,2,\ldots,K について、B_i 番目の食品が嫌いです。

高橋君は N 個の食品のうち、おいしさが最大の食品から 1 つを選んで食べようと考えています。高橋君が嫌いな食品を食べる可能性があるならば Yes を、食べる可能性が無いならば No を出力してください。

制約

1\leq K\leq N\leq 100
1\leq A_i\leq 100
1\leq B_i\leq N
B_i はすべて相異なる
入力はすべて整数

入力

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

N K
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_K

出力

高橋君が嫌いな食品を食べる可能性があるならば Yes を、無いならば No を出力せよ。

入力例 1

5 3
6 8 10 7 10
2 3 4

出力例 1

Yes

5 個の食品の中でおいしさが最大の食品は食品 3 と 5 の 2 つであり、この 2 つのいずれかを食べます。
高橋君が嫌いな食品は 2,3,4 の 3 つであり、そのうち食品 3 を食べる可能性があります。
よって、Yes を出力します。

入力例 2

5 2
100 100 100 1 1
5 4

出力例 2

No

おいしさが最大の食品は食品 1,2,3 の 3 つであり、高橋君は嫌いな食品を食べる可能性はありません。

入力例 3

2 1
100 1
2

出力例 3

No

おいしさが最大の食品は食品 1 であり、高橋君は嫌いな食品を食べる可能性はありません。

Score : 200 points

Problem Statement

Takahashi has N foods in his house. The i-th food has the tastiness of A_i.
He dislikes K of these foods: for each i=1,2,\ldots,K, he dislikes the B_i-th food.

Out of the foods with the greatest tastiness among the N foods, Takahashi will randomly choose one and eat it.
If he has a chance to eat something he dislikes, print Yes; otherwise, print No.

Constraints

1\leq K\leq N\leq 100
1\leq A_i\leq 100
1\leq B_i\leq N
All B_i are distinct.
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_K

Output

If Takahashi has a chance to eat a food he dislikes, print Yes; otherwise, print No.

Sample Input 1

5 3
6 8 10 7 10
2 3 4

Sample Output 1

Yes

Among the five foods, the ones with the greatest tastiness are Food 3 and 5, of which he eats one.
He dislikes Food 2, 3, and 4, one of which he has a chance to eat: Food 3.
Therefore, the answer is Yes.

Sample Input 2

5 2
100 100 100 1 1
5 4

Sample Output 2

No

The foods with the greatest tastiness are Food 1, 2, and 3, none of which he has a chance to eat.

Sample Input 3

2 1
100 1
2

Sample Output 3

No

The food with the greatest tastiness is Food 1, which he has no chance to eat.

E - Peak

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

配点 : 300 点

問題文

高橋くんは数直線上に N 個のプレゼントを置きました。そのうち i 個目のプレゼントは座標 A_i に置かれました。

あなたは数直線上の長さ M の半開区間 [x,x+M) を選び、そこに含まれるプレゼントを全て獲得します。
より詳しくは、以下の手順でプレゼントを獲得します。

まず、実数 x をひとつ選択する。
その後、プレゼントのうち置かれている座標が x \le A_i < x+M を満たすものを全て獲得する。

最大でいくつのプレゼントを獲得することができますか?

制約

入力は全て整数
1 \le N \le 3 \times 10^5
1 \le M \le 10^9
0 \le A_i \le 10^9

入力

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

N M
A_1 A_2 \dots A_N

出力

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

入力例 1

8 6
2 3 5 7 11 13 17 19

出力例 1

例えば、半開区間 [1.5,7.5) を指定します。
このとき、座標 2,3,5,7 にある 4 つのプレゼントを全て獲得することができ、これが獲得可能な最大の個数です。

入力例 2

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

出力例 2

同一の座標に複数のプレゼントが置いてあることもあります。

入力例 3

10 998244353
100000007 0 1755647 998244353 495 1000000000 1755648 503 1755649 998244853

出力例 3

Score : 300 points

Problem Statement

Takahashi has placed N gifts on a number line. The i-th gift is placed at coordinate A_i.

You will choose a half-open interval [x,x+M) of length M on the number line and acquire all the gifts included in it.
More specifically, you acquire gifts according to the following procedure.

First, choose one real number x.
Then, acquire all the gifts whose coordinates satisfy x \le A_i < x+M.

What is the maximum number of gifts you can acquire?

Constraints

All input values are integers.
1 \le N \le 3 \times 10^5
1 \le M \le 10^9
0 \le A_i \le 10^9

Input

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

N M
A_1 A_2 \dots A_N

Output

Print the answer as an integer.

Sample Input 1

8 6
2 3 5 7 11 13 17 19

Sample Output 1

For example, specify the half-open interval [1.5,7.5).
In this case, you can acquire the four gifts at coordinates 2,3,5,7, the maximum number of gifts that can be acquired.

Sample Input 2

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

Sample Output 2

There may be multiple gifts at the same coordinate.

Sample Input 3

10 998244353
100000007 0 1755647 998244353 495 1000000000 1755648 503 1755649 998244853