AtCoder Daily Training EASY 2026/07/03 18:00start

A - Counting Passes

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

N 人の人 1,2,\dots,N がある試験を受け、人 i は A_i 点を取りました。
この試験では、 L 点以上を取った人のみが合格となります。
N 人のうち何人が合格したか求めてください。

制約

入力は全て整数
1 \le N \le 100
1 \le L \le 1000
0 \le A_i \le 1000

入力

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

N L
A_1 A_2 \dots A_N

出力

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

入力例 1

5 60
60 20 100 90 40

出力例 1

5 人が試験を受けました。 60 点以上取ると合格です。

人 1 は 60 点を取ったので、合格です。
人 2 は 20 点を取ったので、不合格です。
人 3 は 100 点を取ったので、合格です。
人 4 は 90 点を取ったので、合格です。
人 5 は 40 点を取ったので、不合格です。

以上より、合格したのは 3 人だと分かります。

入力例 2

4 80
79 78 77 76

出力例 2

合格者がいない場合もあります。

入力例 3

10 50
31 41 59 26 53 58 97 93 23 84

出力例 3

Score : 100 points

Problem Statement

N people labeled 1,2,\dots,N took an exam, and person i scored A_i points.
Only those who scored at least L points pass this exam.
Determine how many people out of the N have passed the exam.

Constraints

All input values are integers.
1 \le N \le 100
1 \le L \le 1000
0 \le A_i \le 1000

Input

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

N L
A_1 A_2 \dots A_N

Output

Print the answer as an integer.

Sample Input 1

5 60
60 20 100 90 40

Sample Output 1

Five people took the exam. You need to score at least 60 points to pass.

Person 1 scored 60 points, so they passed.
Person 2 scored 20 points, so they did not pass.
Person 3 scored 100 points, so they passed.
Person 4 scored 90 points, so they passed.
Person 5 scored 40 points, so they did not pass.

From the above, we can see that three people have passed.

Sample Input 2

4 80
79 78 77 76

Sample Output 2

There may be cases no one has passed.

Sample Input 3

10 50
31 41 59 26 53 58 97 93 23 84

Sample Output 3

B - Buildings

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

N 個のビルが横一列に並んでいて、左から i 番目のビルの高さは H_i です。

左から 1 番目のビルより高いビルが存在するか判定し、存在する場合その内最も左のビルは左から何番目か求めてください。

制約

1\leq N\leq 100
1\leq H_i \leq 100
入力される数値は全て整数

入力

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

N 
H_1 H_2 \ldots H_N

出力

左から 1 番目のビルより高いビルが存在しない場合 -1 を出力せよ。

存在する場合、その内最も左のビルは左から何番目か出力せよ。

入力例 1

4
3 2 5 2

出力例 1

左から 1 番目のビルより高いビルは、左から 3 番目のビルです。

入力例 2

3
4 3 2

出力例 2

-1

左から 1 番目のビルより高いビルは存在しません。

入力例 3

7
10 5 10 2 10 13 15

出力例 3

左から 1 番目のビルより高いビルは、左から 6 番目のビルと左から 7 番目のビルです。その内最も左のビルは左から 6 番目のビルです。

Score: 100 points

Problem Statement

There are N buildings aligned in a row. The i-th building from the left has a height of H_i.

Determine if there is a building taller than the first one from the left. If such a building exists, find the position of the leftmost such building from the left.

Constraints

1 \leq N \leq 100
1 \leq H_i \leq 100
All input values are integers.

Input

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

N
H_1 H_2 \ldots H_N

Output

If no building is taller than the first one from the left, print -1.

If such a building exists, print the position (index) of the leftmost such building from the left.

Sample Input 1

4
3 2 5 2

Sample Output 1

The building taller than the first one from the left is the third one from the left.

Sample Input 2

3
4 3 2

Sample Output 2

-1

No building is taller than the first one from the left.

Sample Input 3

7
10 5 10 2 10 13 15

Sample Output 3

The buildings taller than the first one from the left are the sixth and seventh ones. Among them, the leftmost is the sixth one.

C - Draw Frame

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

縦 H 行、横 W 列のマス目があります。高橋くんは、このマス目のそれぞれのマスを白か黒で塗ろうとしています。

高橋くんは、マス目に含まれるマスのうち端にあるマスをすべて黒く塗り、それ以外のマスを白く塗ります。高橋くんが色を塗ったあとのマス目を出力してください。

より厳密には

H\times W のマス目があります。

上から i 行目 (1\le i\le H) 、左から j 列目 (1\le j\le W) のマスをマス (i,j) と呼ぶことにします。

マス (i,j)\ (1\le i\le H,1\le j\le W) とマス (k,l)\ (1\le k\le H,1\le l\le W) が |i-k|+|j-l|=1 を満たすとき、かつそのときに限りこれらのマスは辺で隣接していると言います。

マス (i,j) と辺で隣接しているマスが 3 個以下のとき、かつそのときに限りマス (i,j) は端にあると言います。

次の条件を満たす H 個の文字列 S _ 1,S _ 2,\ldots,S _ H を求めてください。

S _ i は長さ W の文字列であり、S _ i の j 文字目は、マス (i,j) が端にあるとき # 、そうでないとき . である。

制約

3\le H\le10
3\le W\le10
入力はすべて整数

入力

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

H W

出力

H 行にわたって、長さ W の文字列を出力せよ。 i 行目 (1\le i\le H) の j 文字目 (1\le j\le W) には、マス (i,j) が黒く塗られているなら # 、白く塗られているなら . を出力せよ。

入力例 1

4 5

出力例 1

#####
#...#
#...#
#####

例えば、マス (1,1) は端にあります。マス (1,1) と辺で隣接しているマスはマス (1,2) とマス (2,1) の 2 個のみだからです。よって、マス (1,1) は黒く塗られるので、1 行目の 1 文字目には # を出力してください。

逆に、例えばマス (3,4) は端にありません。マス (3,4) と辺で隣接しているマスはマス (2,4), マス (3,3), マス (3,5), マス (4,4) の 4 個だからです。よって、マス (3,4) は白く塗られるので、3 行目の 4 文字目には . を出力してください。

入力例 2

5 6

出力例 2

######
#....#
#....#
#....#
######

Score : 200 points

Problem Statement

There is a grid with H rows and W columns. Takahashi is going to paint each cell of this grid black or white.

He paints all cells on the border of the grid black, and all other cells white. Output the grid after he has painted it.

More formally

There is an H\times W grid.

We call the cell at the i-th row from the top (1\le i\le H) and the j-th column from the left (1\le j\le W) cell (i,j).

Cell (i,j)\ (1\le i\le H,1\le j\le W) and cell (k,l)\ (1\le k\le H,1\le l\le W) are said to be edge-adjacent if and only if |i-k|+|j-l|=1.

Cell (i,j) is said to be on the border if and only if the number of cells edge-adjacent to cell (i,j) is at most 3.

Find H strings S _ 1,S _ 2,\ldots,S _ H satisfying the following condition.

S _ i is a string of length W, and the j-th character of S _ i is # if cell (i,j) is on the border, and . otherwise.

Constraints

3\le H\le10
3\le W\le10
All input values are integers.

Input

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

H W

Output

Output H lines, each a string of length W. The j-th character (1\le j\le W) of the i-th line (1\le i\le H) should be # if cell (i,j) is painted black, and . if it is painted white.

Sample Input 1

4 5

Sample Output 1

#####
#...#
#...#
#####

For example, cell (1,1) is on the border. This is because there are only two cells edge-adjacent to cell (1,1): cells (1,2) and (2,1). Thus, cell (1,1) is painted black, so the first character of the first line should be #.

Conversely, for example, cell (3,4) is not on the border. This is because there are four cells edge-adjacent to cell (3,4): cells (2,4), (3,3), (3,5), and (4,4). Thus, cell (3,4) is painted white, so the fourth character of the third line should be ..

Sample Input 2

5 6

Sample Output 2

######
#....#
#....#
#....#
######

D - Triple Metre

Time Limit: 2 sec / Memory Limit: 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

E - King's Summit

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

10^9 行 10^9 列のグリッドがあり、このグリッドの上から i 番目、左から j 番目のマスをマス (i, j) と表記します。

グリッド上には N 人の人がおり、はじめ i 人目の人はマス (R_i, C_i) にいます。

はじめ時刻は 0 であり、各人は、時刻 1, 2, 3, 4, \ldots に以下のような移動をすることができます。

その場に留まるか、8 近傍のマスに移動する。ただし、グリッドの外側に出ることはできない。厳密には、現在いるマスをマス (i, j) としてマス (i - 1, j - 1), (i - 1, j), (i - 1, j + 1), (i, j - 1), (i, j), (i, j + 1), (i + 1, j - 1), (i + 1, j), (i + 1, j + 1) のうち存在するマスのいずれかに移動する。また、移動には時間がかからないものとする。

N 人の人が全員同じマスに集まる時刻として考えられる最小値を求めてください。

制約

1 \leq N \leq 2 \times 10^5
1 \leq R_i, C_i \leq 10^9
入力される値はすべて整数

入力

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

N
R_1 C_1
R_2 C_2
\vdots
R_N C_N

出力

答えを出力せよ。

入力例 1

出力例 1

以下のようにそれぞれの人が移動することによって、全員が時刻 3 にマス (5, 4) に集まります。

時刻 1 では、1 人目の人はマス (3, 4)、2 人目の人はマス (6, 2)、3 人目の人はマス (7, 2) に移動する。
時刻 2 では、1 人目の人はマス (4, 4)、2 人目の人はマス (5, 3)、3 人目の人はマス (6, 3) に移動する。
時刻 3 では、1 人目の人はマス (5, 4)、2 人目の人はマス (5, 4)、3 人目の人はマス (5, 4) に移動する。

入力例 2

出力例 2

はじめからすべての人は同じマスにいます。

入力例 3

6
91 999999986
53 999999997
32 999999932
14 999999909
49 999999985
28 999999926

出力例 3

Score : 300 points

Problem Statement

There is a grid with 10^9 rows and 10^9 columns. Let (i, j) denote the square at the i-th row from the top and j-th column from the left.

There are N people on the grid. Initially, the i-th person is at square (R_i, C_i).

The time starts at 0. Each person can do the following move at times 1, 2, 3, 4, \ldots.

Stay at the current position, or move to an 8-adjacent square. It is forbidden to leave the grid. Formally, let square (i, j) be the current square, and move to one of the squares (i - 1, j - 1), (i - 1, j), (i - 1, j + 1), (i, j - 1), (i, j), (i, j + 1), (i + 1, j - 1), (i + 1, j), (i + 1, j + 1) that exists. Assume that the move takes no time.

Find the minimum possible time when the N people are at the same square.

Constraints

1 \leq N \leq 2 \times 10^5
1 \leq R_i, C_i \leq 10^9
All input values are integers.

Input

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

N
R_1 C_1
R_2 C_2
\vdots
R_N C_N

Output

Output the answer.

Sample Input 1

Sample Output 1

All people will be at square (5, 4) at time 3 if each person moves as follows.

At time 1, the 1st person moves to square (3, 4), the 2nd person moves to square (6, 2), and the 3rd person moves to square (7, 2).
At time 2, the 1st person moves to square (4, 4), the 2nd person moves to square (5, 3), and the 3rd person moves to square (6, 3).
At time 3, the 1st person moves to square (5, 4), the 2nd person moves to square (5, 4), and the 3rd person moves to square (5, 4).

Sample Input 2

Sample Output 2

All people start at the same square.

Sample Input 3

6
91 999999986
53 999999997
32 999999932
14 999999909
49 999999985
28 999999926