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

A - Insert

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

長さ N の整数列 A と整数 K,X が与えられます。
整数列 A の K 要素目の直後に整数 X を 1 つ挿入した整数列 B を出力してください。

制約

入力は全て整数
1 \le K \le N \le 100
1 \le A_i,X \le 100

入力

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

N K X
A_1 A_2 \dots A_N

出力

整数列 A の K 要素目の直後に整数 X を 1 つ挿入した整数列 B を、以下の形式で出力せよ。

B_1 B_2 \dots B_{N+1}

入力例 1

4 3 7
2 3 5 11

出力例 1

2 3 5 7 11

K=3, X=7, A=(2,3,5,11) のとき、 B=(2,3,5,7,11) です。

入力例 2

1 1 100
100

出力例 2

100 100

入力例 3

8 8 3
9 9 8 2 4 4 3 5

出力例 3

9 9 8 2 4 4 3 5 3

Score : 100 points

Problem Statement

You are given an integer sequence A of length N and integers K and X.
Print the integer sequence B obtained by inserting the integer X immediately after the K-th element of the sequence A.

Constraints

All input values are integers.
1 \le K \le N \le 100
1 \le A_i, X \le 100

Input

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

N K X
A_1 A_2 \dots A_N

Output

Print the integer sequence B obtained by inserting the integer X immediately after the K-th element of the sequence A, in the following format:

B_1 B_2 \dots B_{N+1}

Sample Input 1

4 3 7
2 3 5 11

Sample Output 1

2 3 5 7 11

For K=3, X=7, and A=(2,3,5,11), we get B=(2,3,5,7,11).

Sample Input 2

1 1 100
100

Sample Output 2

100 100

Sample Input 3

8 8 3
9 9 8 2 4 4 3 5

Sample Output 3

9 9 8 2 4 4 3 5 3

B - N-choice question

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

整数 A,B が与えられるので、 A+B の値を答えてください。
但し、この問題は N 択問題であり、 i 番の選択肢は C_i です。
正解となる 選択肢の番号 を出力してください。

制約

入力は全て整数
1 \le N \le 300
1 \le A,B \le 1000
1 \le C_i \le 2000
C_i は相異なる。すなわち、同じ選択肢が複数存在することはない。
A+B=C_i なる i が丁度 1 つ存在する。すなわち、正解となる選択肢が必ずただ 1 つ存在する。

入力

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

N A B
C_1 C_2 \dots C_N

出力

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

入力例 1

3 125 175
200 300 400

出力例 1

125+175 = 300 です。
1 番の選択肢は 200 、 2 番の選択肢は 300 、 3 番の選択肢は 400 です。
よって正解となる選択肢の番号は 2 番であり、これを出力します。

入力例 2

1 1 1
2

出力例 2

1 択問題である場合もあります。

入力例 3

5 123 456
135 246 357 468 579

出力例 3

Score : 100 points

Problem Statement

Given integers A and B, find A+B.
This is a N-choice problem; the i-th choice is C_i.
Print the index of the correct choice.

Constraints

All values in the input are integers.
1 \le N \le 300
1 \le A,B \le 1000
1 \le C_i \le 2000
C_i are pairwise distinct. In other words, no two choices have the same value.
There is exactly one i such that A+B=C_i. In other words, there is always a unique correct choice.

Input

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

N A B
C_1 C_2 \dots C_N

Output

Print the answer as an integer.

Sample Input 1

3 125 175
200 300 400

Sample Output 1

We have 125+175 = 300.
The first, second, and third choices are 200, 300, and 400, respectively.
Thus, the 2-nd choice is correct, so 2 should be printed.

Sample Input 2

1 1 1
2

Sample Output 2

The problem may be a one-choice problem.

Sample Input 3

5 123 456
135 246 357 468 579

Sample Output 3

C - Hammer

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

数直線の原点に高橋君がいます。高橋君は座標 X にあるゴールに移動しようとしています。

座標 Y には壁があり、最初、高橋君は壁を超えて移動することができません。
座標 Z にあるハンマーを拾った後でなら、壁を破壊して通過できるようになります。

高橋君がゴールに到達することが可能か判定し、可能であれば移動距離の最小値を求めてください。

制約

-1000 \leq X,Y,Z \leq 1000
X,Y,Z は相異なり、いずれも 0 でない
入力に含まれる値は全て整数である

入力

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

X Y Z

出力

高橋君がゴールに到達することが可能であれば、移動距離の最小値を出力せよ。不可能であれば、かわりに -1 と出力せよ。

入力例 1

10 -10 1

出力例 1

高橋君はまっすぐゴールに向かうことができます。

入力例 2

20 10 -10

出力例 2

ゴールは壁の向こう側にあります。まずハンマーを拾い、壁を壊すことでゴールに到達することができます。

入力例 3

100 1 1000

出力例 3

-1

Score : 200 points

Problem Statement

Takahashi is at the origin of a number line. He wants to reach a goal at coordinate X.

There is a wall at coordinate Y, which Takahashi cannot go beyond at first.
However, after picking up a hammer at coordinate Z, he can destroy that wall and pass through.

Determine whether Takahashi can reach the goal. If he can, find the minimum total distance he needs to travel to do so.

Constraints

-1000 \leq X,Y,Z \leq 1000
X, Y, and Z are distinct, and none of them is 0.
All values in the input are integers.

Input

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

X Y Z

Output

If Takahashi can reach the goal, print the minimum total distance he needs to travel to do so. If he cannot, print -1 instead.

Sample Input 1

10 -10 1

Sample Output 1

Takahashi can go straight to the goal.

Sample Input 2

20 10 -10

Sample Output 2

The goal is beyond the wall. He can get there by first picking up the hammer and then destroying the wall.

Sample Input 3

100 1 1000

Sample Output 3

-1

D - Most Frequent Substrings

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

英小文字からなる長さ N の文字列 S が与えられます。

長さ K の文字列 t の出現回数を、以下を満たす整数 i の個数として定義します。

1 \leq i \leq N-K+1
S の i 文字目から i+K-1 文字目までからなる部分文字列が t に一致する。

長さ K の文字列に対する出現回数の最大値 x を求めてください。また、出現回数が x となるような長さ K の文字列をすべて辞書順昇順に出力してください。

制約

N, K は整数
S は英小文字からなる長さ N の文字列
1 \leq K \leq N \leq 100

入力

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

N K
S

出力

2 行出力せよ。

1 行目には、長さ K の文字列に対する出現回数の最大値 x を出力せよ。

2 行目には、出現回数が x となるような長さ K の文字列を辞書順昇順に、空白区切りで出力せよ。

入力例 1

9 3
ovowowovo

出力例 1

2
ovo owo

出現回数 2 の文字列として、以下が挙げられます。

文字列 ovo について、i=1,7 が条件を満たすことから、ovo の出現回数は 2 です。
文字列 owo について、i=3,5 が条件を満たすことから、owo の出現回数は 2 です。

出現回数が 2 よりも大きいような長さ 3 の文字列は存在しないので、求める最大値は 2 です。

一方で、出現回数が 2 よりも小さい文字列として、以下が挙げられます。

文字列 vow について、i=2 が条件を満たすことから、vow の出現回数は 1 です。
文字列 ooo について、条件を満たす i が存在しないことから、ooo の出現回数は 0 です。

入力例 2

9 1
ovowowovo

出力例 2

5
o

入力例 3

35 3
thequickbrownfoxjumpsoverthelazydog

出力例 3

2
the

Score : 200 points

Problem Statement

You are given a string S of length N consisting of lowercase English letters.

Define the number of occurrences of a string t of length K as the number of integers i that satisfy the following condition:

1 \leq i \leq N-K+1
The substring of S from the i-th character to the (i+K-1)-th character matches t.

Find the maximum value x of the number of occurrences of a string of length K. Also, output all strings of length K with x occurrences in ascending lexicographical order.

Constraints

N, K are integers.
S is a string of length N consisting of lowercase English letters.
1 \leq K \leq N \leq 100

Input

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

N K
S

Output

Output two lines.

The first line should contain the maximum value x of the number of occurrences of a string of length K.

The second line should contain all strings of length K with x occurrences in ascending lexicographical order, separated by spaces.

Sample Input 1

9 3
ovowowovo

Sample Output 1

2
ovo owo

The following strings have two occurrences:

For the string ovo, i=1,7 satisfy the condition, so the number of occurrences of ovo is 2.
For the string owo, i=3,5 satisfy the condition, so the number of occurrences of owo is 2.

There is no string of length 3 with more than two occurrences, so the maximum value is 2.

On the other hand, the following are examples of strings with fewer than two occurrences:

For the string vow, i=2 satisfies the condition, so the number of occurrences of vow is 1.
For the string ooo, there is no i that satisfies the condition, so the number of occurrences of ooo is 0.

Sample Input 2

9 1
ovowowovo

Sample Output 2

5
o

Sample Input 3

35 3
thequickbrownfoxjumpsoverthelazydog

Sample Output 3

2
the

E - Avoid Knight Attack

Time Limit: 4 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

縦 N マス、横 N マスの N ^ 2 マスからなるマス目があります。上から i 行目 (1\leq i\leq N) 、左から j 列目 (1\leq j\leq N) のマスをマス (i,j) と呼ぶことにします。

それぞれのマスは、空マスであるかコマが置かれているかのどちらかです。マス目には合計で M 個のコマが置かれており、k 番目 (1\leq k\leq M) のコマはマス (a _ k,b _ k) に置かれています。

あなたは、すでに置かれているどのコマにも取られないように、いずれかの空マスに自分のコマを置きたいです。

マス (i,j) に置かれているコマは、次のどれかの条件を満たすコマを取ることができます。

マス (i+2,j+1) に置かれている
マス (i+1,j+2) に置かれている
マス (i-1,j+2) に置かれている
マス (i-2,j+1) に置かれている
マス (i-2,j-1) に置かれている
マス (i-1,j-2) に置かれている
マス (i+1,j-2) に置かれている
マス (i+2,j-1) に置かれている

ただし、存在しないマスについての条件は常に満たされないものとします。

たとえば、マス (4,4) に置かれているコマは、以下の図で青く示されたマスに置かれているコマを取ることができます。

あなたがコマを置くことができるマスがいくつあるか求めてください。

制約

1\leq N\leq10 ^ 9
1\leq M\leq2\times10 ^ 5
1\leq a _ k\leq N,1\leq b _ k\leq N\ (1\leq k\leq M)
(a _ k,b _ k)\neq(a _ l,b _ l)\ (1\leq k\lt l\leq M)
入力はすべて整数

入力

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

N M
a _ 1 b _ 1
a _ 2 b _ 2
\vdots
a _ M b _ M

出力

すでに置かれているコマに取られずに自分のコマを置くことができる空マスの個数を出力せよ。

入力例 1

出力例 1

すでに置かれているコマは、以下の図で青く示されたマスに置かれたコマを取ることができます。

よって、あなたがすでに置かれているコマに取られないように自分のコマを置くことができるマスは残りの 38 マスです。

入力例 2

1000000000 1
1 1

出力例 2

999999999999999997

10 ^ {18} マスのうち、置くことができないマスはマス (1,1),(2,3),(3,2) の 3 マスのみです。

答えが 2 ^ {32} 以上になる場合があることに注意してください。

入力例 3

出力例 3

Score : 300 points

Problem Statement

There is a grid of N^2 squares with N rows and N columns. Let (i,j) denote the square at the i-th row from the top (1\leq i\leq N) and j-th column from the left (1\leq j\leq N).

Each square is either empty or has a piece placed on it. There are M pieces placed on the grid, and the k-th (1\leq k\leq M) piece is placed on square (a_k,b_k).

You want to place your piece on an empty square in such a way that it cannot be captured by any of the existing pieces.

A piece placed on square (i,j) can capture pieces that satisfy any of the following conditions:

Placed on square (i+2,j+1)
Placed on square (i+1,j+2)
Placed on square (i-1,j+2)
Placed on square (i-2,j+1)
Placed on square (i-2,j-1)
Placed on square (i-1,j-2)
Placed on square (i+1,j-2)
Placed on square (i+2,j-1)

Here, conditions involving non-existent squares are considered to never be satisfied.

For example, a piece placed on square (4,4) can capture pieces placed on the squares shown in blue in the following figure:

How many squares can you place your piece on?

Constraints

1\leq N\leq10^9
1\leq M\leq2\times10^5
1\leq a_k\leq N,1\leq b_k\leq N\ (1\leq k\leq M)
(a_k,b_k)\neq(a_l,b_l)\ (1\leq k\lt l\leq M)
All input values are integers.

Input

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

N M
a_1 b_1
a_2 b_2
\vdots
a_M b_M

Output

Print the number of empty squares where you can place your piece without it being captured by any existing pieces.

Sample Input 1

Sample Output 1

The existing pieces can capture pieces placed on the squares shown in blue in the following figure:

Therefore, you can place your piece on the remaining 38 squares.

Sample Input 2

1000000000 1
1 1

Sample Output 2

999999999999999997

Out of 10^{18} squares, only 3 squares cannot be used: squares (1,1), (2,3), and (3,2).

Note that the answer may be 2^{32} or greater.

Sample Input 3