AtCoder Daily Training EASY 2026/09/03 16:00start

A - Filter

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

配点 : 100 点

問題文

長さ N の整数列 A=(A _ 1,A _ 2,\ldots,A _ N) が与えられます。

A から偶数だけすべて取り出し、もとの順番を保って出力してください。

制約

1\leq N\leq 100
1\leq A _ i\leq 100\ (1\leq i\leq N)
A には 1 つ以上偶数が含まれる
入力はすべて整数

入力

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

N
A _ 1 A _ 2 \ldots A _ N

出力

A から偶数を取り出した列を、空白区切りで 1 行に出力せよ。

入力例 1

5
1 2 3 5 6

出力例 1

2 6

A=(1,2,3,5,6) です。このうち偶数なのは A _ 2=2,A _ 5=6 の 2 つなので、2 と 6 をこの順に空白区切りで出力してください。

入力例 2

5
2 2 2 3 3

出力例 2

2 2 2

A の中には同じ要素がある場合もあります。

入力例 3

10
22 3 17 8 30 15 12 14 11 17

出力例 3

22 8 30 12 14

Score : 100 points

Problem Statement

You are given a sequence of N integers: A=(A _ 1,A _ 2,\ldots,A _ N).

Print all even numbers in A without changing the order.

Constraints

1\leq N\leq 100
1\leq A _ i\leq 100\ (1\leq i\leq N)
A contains at least one even number.
All values in the input are integers.

Input

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

N
A _ 1 A _ 2 \ldots A _ N

Output

Print a line containing the sequence of all even numbers in A, with spaces in between.

Sample Input 1

5
1 2 3 5 6

Sample Output 1

2 6

We have A=(1,2,3,5,6). Among them are two even numbers, A _ 2=2 and A _ 5=6, so print 2 and 6 in this order, with a space in between.

Sample Input 2

5
2 2 2 3 3

Sample Output 2

2 2 2

A may contain equal elements.

Sample Input 3

10
22 3 17 8 30 15 12 14 11 17

Sample Output 3

22 8 30 12 14

B - Not Found

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

配点 : 100 点

問題文

英小文字からなる長さ 1 以上 25 以下の文字列 S が与えられます。
S に含まれない英小文字をひとつ出力してください。
但し、そのようなものが複数ある場合はどれを出力しても構いません。

制約

S は英小文字からなる長さ 1 以上 25 以下の文字列

入力

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

出力

S に含まれない英小文字をひとつ出力せよ。そのようなものが複数ある場合はどれを出力しても構わない。

入力例 1

出力例 1

S= a です。
a 以外の英小文字、 b, c, ..., z が正解となります。

入力例 2

abcdfhijklmnopqrstuvwxyz

出力例 2

S 中に含まれない英小文字は e と g です。

入力例 3

qazplwsxokmedcijnrfvuhbgt

出力例 3

Score : 100 points

Problem Statement

You are given a string S of length between 1 and 25 consisting of lowercase English letters.
Output one lowercase English letter that does not appear in S.
If there are multiple such letters, you may output any one of them.

Constraints

S is a string of length between 1 and 25 (inclusive) consisting of lowercase English letters.

Input

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

Output

Output one lowercase English letter that does not appear in S. If there are multiple such letters, you may output any one of them.

Sample Input 1

Sample Output 1

S= a.
Any lowercase English letter other than a (that is, b, c, …, or z) is a correct answer.

Sample Input 2

abcdfhijklmnopqrstuvwxyz

Sample Output 2

The lowercase English letters not included in S are e and g.

Sample Input 3

qazplwsxokmedcijnrfvuhbgt

Sample Output 3

C - Mongeness

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

配点 : 200 点

問題文

縦 H 行、横 W 列のマス目があり、各マスには 1 つの整数が書かれています。上から i 行目、左から j 列目のマスに書かれている整数は A_{i, j} です。

マス目が下記の条件を満たすかどうかを判定してください。

1 \leq i_1 < i_2 \leq H および 1 \leq j_1 < j_2 \leq W を満たすすべての整数の組 (i_1, i_2, j_1, j_2) について、A_{i_1, j_1} + A_{i_2, j_2} \leq A_{i_2, j_1} + A_{i_1, j_2} が成り立つ。

制約

2 \leq H, W \leq 50
1 \leq A_{i, j} \leq 10^9
入力はすべて整数

入力

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

H W
A_{1, 1} A_{1, 2} \cdots A_{1, W}
A_{2, 1} A_{2, 2} \cdots A_{2, W}
\vdots
A_{H, 1} A_{H, 2} \cdots A_{H, W}

出力

マス目が問題文中の条件を満たす場合は Yes と出力し、条件を満たさない場合は No と出力せよ。

入力例 1

出力例 1

Yes

1 \leq i_1 < i_2 \leq H および 1 \leq j_1 < j_2 \leq W を満たす整数の組 (i_1, i_2, j_1, j_2) は 9 個存在し、それらすべてについて A_{i_1, j_1} + A_{i_2, j_2} \leq A_{i_2, j_1} + A_{i_1, j_2} が成り立ちます。例えば、

(i_1, i_2, j_1, j_2) = (1, 2, 1, 2) について、A_{i_1, j_1} + A_{i_2, j_2} = 2 + 1 \leq 3 + 1 = A_{i_2, j_1} + A_{i_1, j_2}
(i_1, i_2, j_1, j_2) = (1, 2, 1, 3) について、A_{i_1, j_1} + A_{i_2, j_2} = 2 + 3 \leq 3 + 4 = A_{i_2, j_1} + A_{i_1, j_2}
(i_1, i_2, j_1, j_2) = (1, 2, 2, 3) について、A_{i_1, j_1} + A_{i_2, j_2} = 1 + 3 \leq 1 + 4 = A_{i_2, j_1} + A_{i_1, j_2}
(i_1, i_2, j_1, j_2) = (1, 3, 1, 2) について、A_{i_1, j_1} + A_{i_2, j_2} = 2 + 4 \leq 6 + 1 = A_{i_2, j_1} + A_{i_1, j_2}
(i_1, i_2, j_1, j_2) = (1, 3, 1, 3) について、A_{i_1, j_1} + A_{i_2, j_2} = 2 + 1 \leq 6 + 4 = A_{i_2, j_1} + A_{i_1, j_2}

が成り立ちます。残りの (i_1, i_2, j_1, j_2) = (1, 3, 2, 3), (2, 3, 1, 2), (2, 3, 1, 3), (2, 3, 2, 3) についても同様に確認できます。
よって、Yes を出力します。

入力例 2

2 4
4 3 2 1
5 6 7 8

出力例 2

No

問題文中の条件を満たさないので、No を出力します。
例えば、(i_1, i_2, j_1, j_2) = (1, 2, 1, 4) について、A_{i_1, j_1} + A_{i_2, j_2} = 4 + 8 > 5 + 1 = A_{i_2, j_1} + A_{i_1, j_2} です。

Score : 200 points

Problem Statement

We have a grid with H horizontal rows and W vertical columns, where each square contains an integer. The integer written on the square at the i-th row from the top and j-th column from the left is A_{i, j}.

Determine whether the grid satisfies the condition below.

A_{i_1, j_1} + A_{i_2, j_2} \leq A_{i_2, j_1} + A_{i_1, j_2} holds for every quadruple of integers (i_1, i_2, j_1, j_2) such that 1 \leq i_1 < i_2 \leq H and 1 \leq j_1 < j_2 \leq W.

Constraints

2 \leq H, W \leq 50
1 \leq A_{i, j} \leq 10^9
All values in input are integers.

Input

Input is given from Standard Input in the following format:

H W
A_{1, 1} A_{1, 2} \cdots A_{1, W}
A_{2, 1} A_{2, 2} \cdots A_{2, W}
\vdots
A_{H, 1} A_{H, 2} \cdots A_{H, W}

Output

If the grid satisfies the condition in the Problem Statement, print Yes; otherwise, print No.

Sample Input 1

Sample Output 1

Yes

There are nine quadruples of integers (i_1, i_2, j_1, j_2) such that 1 \leq i_1 < i_2 \leq H and 1 \leq j_1 < j_2 \leq W. For all of them, A_{i_1, j_1} + A_{i_2, j_2} \leq A_{i_2, j_1} + A_{i_1, j_2} holds. Some examples follow.

For (i_1, i_2, j_1, j_2) = (1, 2, 1, 2), we have A_{i_1, j_1} + A_{i_2, j_2} = 2 + 1 \leq 3 + 1 = A_{i_2, j_1} + A_{i_1, j_2}.
For (i_1, i_2, j_1, j_2) = (1, 2, 1, 3), we have A_{i_1, j_1} + A_{i_2, j_2} = 2 + 3 \leq 3 + 4 = A_{i_2, j_1} + A_{i_1, j_2}.
For (i_1, i_2, j_1, j_2) = (1, 2, 2, 3), we have A_{i_1, j_1} + A_{i_2, j_2} = 1 + 3 \leq 1 + 4 = A_{i_2, j_1} + A_{i_1, j_2}.
For (i_1, i_2, j_1, j_2) = (1, 3, 1, 2), we have A_{i_1, j_1} + A_{i_2, j_2} = 2 + 4 \leq 6 + 1 = A_{i_2, j_1} + A_{i_1, j_2}.
For (i_1, i_2, j_1, j_2) = (1, 3, 1, 3), we have A_{i_1, j_1} + A_{i_2, j_2} = 2 + 1 \leq 6 + 4 = A_{i_2, j_1} + A_{i_1, j_2}.

We can also see that the property holds for the other quadruples: (i_1, i_2, j_1, j_2) = (1, 3, 2, 3), (2, 3, 1, 2), (2, 3, 1, 3), (2, 3, 2, 3).
Thus, we should print Yes.

Sample Input 2

2 4
4 3 2 1
5 6 7 8

Sample Output 2

No

We should print No because the condition is not satisfied.
This is because, for example, we have A_{i_1, j_1} + A_{i_2, j_2} = 4 + 8 > 5 + 1 = A_{i_2, j_1} + A_{i_1, j_2} for (i_1, i_2, j_1, j_2) = (1, 2, 1, 4).

D - 326-like Numbers

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

配点 : 200 点

問題文

3 桁の正整数であって、百の位の数と十の位の数の積が一の位の数と等しいものを 326-like number と呼びます。

例えば 326,400,144 は 326-like number であり、623,777,429 は 326-like number ではありません。

整数 N が与えられるので、N 以上の最小の 326-like number を求めてください。なお、制約の条件下で答えは必ず存在します。

制約

100 \leq N \leq 919
N は整数である

入力

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

出力

答えを出力せよ。

入力例 1

出力例 1

320,321,322,323,324,325 は 326-like number ではなく、326 は 326-like number です。

入力例 2

出力例 2

144 は 326-like number です。

入力例 3

出力例 3

Score : 200 points

Problem Statement

A 326-like number is a three-digit positive integer where the product of the hundreds and tens digits equals the ones digit.

For example, 326,400,144 are 326-like numbers, while 623,777,429 are not.

Given an integer N, find the smallest 326-like number greater than or equal to N. It always exists under the constraints.

Constraints

100 \leq N \leq 919
N is an integer.

Input

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

Output

Print the answer.

Sample Input 1

Sample Output 1

320,321,322,323,324,325 are not 326-like numbers, while 326 is a 326-like number.

Sample Input 2

Sample Output 2

144 is a 326-like number.

Sample Input 3

Sample Output 3

E - Sum of Min Query

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

配点 : 300 点

問題文

長さ N の整数列 A=(A_1,A_2,\ldots,A_N),B=(B_1,B_2,\ldots,B_N) が与えられます。

Q 個のクエリが与えられるので順に処理してください。 i 番目 (1\le i\le Q) のクエリは以下で説明されます。

文字 c_i と整数 X_i,V_i が与えられる。 c_i= A ならば A_{X_i} を、 c_i= B ならば B_{X_i} を V_i に変更する。その後、 \displaystyle \sum_{k=1}^N \min(A_k,B_k) を出力する。

制約

1\le N,Q \le 2 \times 10^5
1\le A_i,B_i \le 10^9
c_i は A か B のいずれか
1\le X_i \le N
1\le V_i \le 10^9
入力される数値は全て整数

入力

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

N Q
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_N
c_1 X_1 V_1
c_2 X_2 V_2
\vdots
c_Q X_Q V_Q

出力

Q 行出力せよ。 i 行目 (1\le i\le Q) には i 番目のクエリに対する答えを出力せよ。

入力例 1

出力例 1

7
9
9

1 番目のクエリでは A=(3,3,4,1),B=(2,7,1,8) となります。したがって、1 行目には \displaystyle \min(3,2)+\min(3,7) + \min(4 , 1)+\min(1,8) = 7 を出力してください。

2 番目のクエリでは A=(3,3,4,1),B=(2,7,3,8) となります。したがって、 2 行目には \displaystyle \min(3,2)+\min(3,7) + \min(4 , 3)+\min(1,8) = 9 を出力してください。

3 番目のクエリでは A=(7,3,4,1),B=(2,7,3,8) となります。したがって、 3 行目には \displaystyle \min(7,2)+\min(3,7) + \min(4 , 3)+\min(1,8) = 9 を出力してください。

入力例 2

出力例 2

1
1
1

入力例 3

5 3
100 100 100 100 100
100 100 100 100 100
A 4 21
A 2 99
B 4 57

出力例 3

421
420
420

Score : 300 points

Problem Statement

You are given length-N integer sequences: A=(A_1,A_2,\ldots,A_N) and B=(B_1,B_2,\ldots,B_N).

You are given Q queries to process in order. The i-th query (1\le i\le Q) is described as follows:

You are given a character c_i and integers X_i,V_i. If c_i= A, change A_{X_i} to V_i; if c_i= B, change B_{X_i} to V_i. Then, output \displaystyle \sum_{k=1}^N \min(A_k,B_k).

Constraints

1\le N,Q \le 2 \times 10^5
1\le A_i,B_i \le 10^9
c_i is either A or B.
1\le X_i \le N
1\le V_i \le 10^9
All input values are integers.

Input

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

N Q
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_N
c_1 X_1 V_1
c_2 X_2 V_2
\vdots
c_Q X_Q V_Q

Output

Output Q lines. The i-th line (1\le i\le Q) should contain the answer to the i-th query.

Sample Input 1

Sample Output 1

7
9
9

After the 1st query, A=(3,3,4,1),B=(2,7,1,8). Therefore, output \displaystyle \min(3,2)+\min(3,7) + \min(4 , 1)+\min(1,8) = 7 on the 1st line.

After the 2nd query, A=(3,3,4,1),B=(2,7,3,8). Therefore, output \displaystyle \min(3,2)+\min(3,7) + \min(4 , 3)+\min(1,8) = 9 on the 2nd line.

After the 3rd query, A=(7,3,4,1),B=(2,7,3,8). Therefore, output \displaystyle \min(7,2)+\min(3,7) + \min(4 , 3)+\min(1,8) = 9 on the 3rd line.

Sample Input 2

Sample Output 2

1
1
1

Sample Input 3

5 3
100 100 100 100 100
100 100 100 100 100
A 4 21
A 2 99
B 4 57

Sample Output 3

421
420
420