AtCoder Daily Training MEDIUM 2025/05/15 16:30start

C - Second Best

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

配点 : 200 点

問題文

長さ N の整数列 A=(A_1,\ldots,A_N) が与えられます。ここで A_1,A_2,\ldots,A_N は相異なります。

A の中で二番目に大きい要素は A の何番目の要素でしょうか。

制約

2\leq N\leq 100
1\leq A_i \leq 10^9
A_1,A_2,\ldots,A_N は相異なる
入力される数値は全て整数

入力

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

N 
A_1 A_2 \ldots A_{N}

出力

A の中で二番目に大きい要素が A の X 番目であるとき、X を整数として出力せよ。

入力例 1

4
8 2 5 1

出力例 1

A の中で二番目に大きい要素は A_3 なので 3 を出力してください。

入力例 2

8
1 2 3 4 5 10 9 11

出力例 2

Score : 200 points

Problem Statement

You are given an integer sequence A=(A_1,\ldots,A_N) of length N. Here, A_1, A_2, \ldots, A_N are all distinct.

Which element in A is the second largest?

Constraints

2 \leq N \leq 100
1 \leq A_i \leq 10^9
A_1, A_2, \ldots, A_N are all distinct.
All input values are integers.

Input

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

N 
A_1 A_2 \ldots A_{N}

Output

Print the integer X such that the X-th element in A is the second largest.

Sample Input 1

4
8 2 5 1

Sample Output 1

The second largest element in A is A_3, so print 3.

Sample Input 2

8
1 2 3 4 5 10 9 11

Sample Output 2

D - Ticket Gate Log

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

配点 : 250 点

問題文

高橋君は改札機の利用履歴を集計しました。しかし、高橋君はうっかりいくつかの入退場記録を消してしまいました。高橋君は消してしまった記録の復元を試みようとしています。

i, o のみからなる文字列 S が与えられます。 S の任意の位置に文字を 0 文字以上挿入することで、変更後の文字列が以下の条件を満たすようにしたいです。

長さが偶数であり、奇数文字目が i で偶数文字目が o である。

挿入する必要のある文字数の最小値を求めて下さい。なお、問題の制約下で、有限個の文字を適切に挿入することで、S が条件をみたすようにできることが証明できます。

制約

S は i, o からなる長さ 1 以上 100 以下の文字列

入力

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

出力

答えを出力せよ。

入力例 1

ioi

出力例 1

3 文字目のあとに o を挿入して ioio とすることで、条件を満たすことができます。0 文字以下の挿入で条件を満たすことはできません。

入力例 2

iioo

出力例 2

1 文字目のあとに o を、3 文字目のあとに i を挿入することで、条件を満たすことができます。1 文字以下の挿入で条件を満たすことはできません。

入力例 3

io

出力例 3

S がすでに条件を満たします。

Score : 250 points

Problem Statement

Takahashi aggregated usage records from ticket gates. However, he accidentally erased some records of entering and exiting stations. He is trying to restore the erased records.

You are given a string S consisting of i and o. We want to insert zero or more characters at arbitrary positions in S so that the resulting string satisfies the following conditions:

Its length is even, and every odd-numbered (1st, 3rd, ...) character is i while every even-numbered (2nd, 4th, ...) character is o.

Find the minimum number of characters that need to be inserted. It can be proved under the constraints of this problem that by inserting an appropriate finite number of characters, S can be made to satisfy the conditions.

Constraints

S is a string of length between 1 and 100, consisting of i and o.

Input

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

Output

Print the answer.

Sample Input 1

ioi

Sample Output 1

We can insert o after the 3rd character to form ioio to satisfy the conditions. The conditions cannot be satisfied by inserting zero or fewer characters.

Sample Input 2

iioo

Sample Output 2

We can insert o after the 1st character and i after the 3rd character to satisfy the conditions. The conditions cannot be satisfied by inserting one or fewer characters.

Sample Input 3

io

Sample Output 3

S already satisfies the conditions.

E - Sigma Problem

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

配点 : 300 点

問題文

正整数 x,y に対して f(x,y) を「(x+y) を 10^8 で割ったあまり」として定義します。

長さ N の正整数列 A=(A_1,\ldots,A_N) が与えられます。次の式の値を求めてください。

\displaystyle \sum_{i=1}^{N-1}\sum_{j=i+1}^N f(A_i,A_j)

制約

2\leq N\leq 3\times 10^5
1\leq A_i < 10^8
入力される数値は全て整数

入力

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

N 
A_1 \ldots A_N

出力

答えを出力せよ。

入力例 1

3
3 50000001 50000002

出力例 1

100000012

f(A_1,A_2)=50000004
f(A_1,A_3)=50000005
f(A_2,A_3)=3

なので、答えは f(A_1,A_2)+f(A_1,A_3)+f(A_2,A_3) = 100000012 です。

総和を 10^8 で割ったあまりを求めるわけではないことに注意してください。

入力例 2

5
1 3 99999999 99999994 1000000

出力例 2

303999988

Score: 300 points

Problem Statement

For positive integers x and y, define f(x, y) as the remainder of (x + y) divided by 10^8.

You are given a sequence of positive integers A = (A_1, \ldots, A_N) of length N. Find the value of the following expression:

\displaystyle \sum_{i=1}^{N-1}\sum_{j=i+1}^N f(A_i,A_j).

Constraints

2 \leq N \leq 3\times 10^5
1 \leq A_i < 10^8
All input values are integers.

Input

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

N 
A_1 \ldots A_N

Output

Print the answer.

Sample Input 1

3
3 50000001 50000002

Sample Output 1

100000012

f(A_1,A_2)=50000004
f(A_1,A_3)=50000005
f(A_2,A_3)=3

Thus, the answer is f(A_1,A_2) + f(A_1,A_3) + f(A_2,A_3) = 100000012.

Note that you are not asked to compute the remainder of the sum divided by 10^8.

Sample Input 2

5
1 3 99999999 99999994 1000000

Sample Output 2

303999988

F - Even Digits

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

配点 : 300 点

問題文

非負整数 n が次の条件を満たすとき、n を 良い整数 と呼びます。

n を 10 進法で表したときに、偶数の数字 (0, 2, 4, 6, 8) のみが登場する。

例えば 0、68 および 2024 は良い整数です。

整数 N が与えられます。良い整数のうち小さい方から N 番目の整数を求めてください。

制約

1 \leq N \leq 10^{12}
N は整数

入力

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

出力

小さい方から N 番目の良い整数を出力せよ。

入力例 1

出力例 1

良い整数を小さい方から順に並べると 0, 2, 4, 6, 8, 20, 22, 24, 26, 28, \dots となります。
小さい方から 8 番目の良い整数は 24 なので、これを出力します。

入力例 2

出力例 2

入力例 3

31415926535

出力例 3

2006628868244228

Score: 300 points

Problem Statement

A non-negative integer n is called a good integer when it satisfies the following condition:

All digits in the decimal notation of n are even numbers (0, 2, 4, 6, and 8).

For example, 0, 68, and 2024 are good integers.

You are given an integer N. Find the N-th smallest good integer.

Constraints

1 \leq N \leq 10^{12}
N is an integer.

Input

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

Output

Print the N-th smallest good integer.

Sample Input 1

Sample Output 1

The good integers in ascending order are 0, 2, 4, 6, 8, 20, 22, 24, 26, 28, \dots.
The eighth smallest is 24, which should be printed.

Sample Input 2

Sample Output 2

Sample Input 3

31415926535

Sample Output 3

2006628868244228

G - Cross Explosion

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

配点 : 400 点

問題文

縦 H マス、横 W マスのグリッドがあります。上から i 行目、左から j 列目のマスを (i, j) と表します。
はじめ、全てのマスには壁が 1 個ずつ立てられています。
以下で説明されるクエリを Q 個与えられる順に処理した後に、残っている壁の個数を求めてください。

q 番目のクエリでは整数 R_q, C_q が与えられます。
あなたは (R_q, C_q) に爆弾を置いて壁を爆破します。その結果、以下の処理が行われます。

(R_q, C_q) に壁が存在する場合は、その壁を破壊して処理を終了する。
(R_q, C_q) に壁が存在しない場合は、(R_q, C_q) から上下左右に見て最初に現れる壁を破壊する。厳密に述べると、以下の 4 個の処理が同時に行われる。
- (i, C_q) に壁が存在して (k, C_q) (i \lt k \lt R_q) に壁が存在しないような i \lt R_q が存在する時、(i, C_q) に存在する壁を破壊する。
- (i, C_q) に壁が存在して (k, C_q) (R_q \lt k \lt i) に壁が存在しないような i \gt R_q が存在する時、(i, C_q) に存在する壁を破壊する。
- (R_q, j) に壁が存在して (R_q, k) (j \lt k \lt C_q) に壁が存在しないような j \lt C_q が存在する時、(R_q, j) に存在する壁を破壊する。
- (R_q, j) に壁が存在して (R_q, k) (C_q \lt k \lt j) に壁が存在しないような j \gt C_q が存在する時、(R_q, j) に存在する壁を破壊する。

制約

1 \leq H, W
H \times W \leq 4 \times 10^5
1 \leq Q \leq 2 \times 10^5
1 \leq R_q \leq H
1 \leq C_q \leq W
入力される値は全て整数

入力

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

H W Q
R_1 C_1
R_2 C_2
\vdots
R_Q C_Q

出力

クエリを全て処理した後に、残っている壁の個数を出力せよ。

入力例 1

出力例 1

クエリを処理する手順を説明すると次のようになります。

1 番目のクエリでは (R_1, C_1) = (1, 2) である。 (1, 2) に壁は存在するので (1, 2) の壁が爆破される。
2 番目のクエリでは (R_2, C_2) = (1, 2) である。 (1, 2) に壁は存在しないので、(1, 2) から上下左右に見て最初に現れる壁である (2,2),(1,1),(1,3) が爆破される。
3 番目のクエリでは (R_2, C_2) = (1, 3) である。 (1, 3) に壁は存在しないので、(1, 3) から上下左右に見て最初に現れる壁である (2,3),(1,4) が爆破される。

全てのクエリを処理した後に残っている壁は (2, 1), (2, 4) の 2 個です。

入力例 2

出力例 2

入力例 3

出力例 3

Score : 400 points

Problem Statement

There is a grid with H rows and W columns. Let (i, j) denote the cell at the i-th row from the top and j-th column from the left.
Initially, there is one wall in each cell.
After processing Q queries explained below in the order they are given, find the number of remaining walls.

In the q-th query, you are given two integers R_q and C_q.
You place a bomb at (R_q, C_q) to destroy walls. As a result, the following process occurs.

If there is a wall at (R_q, C_q), destroy that wall and end the process.
If there is no wall at (R_q, C_q), destroy the first walls that appear when looking up, down, left, and right from (R_q, C_q). More precisely, the following four processes occur simultaneously:
- If there exists an i \lt R_q such that a wall exists at (i, C_q) and no wall exists at (k, C_q) for all i \lt k \lt R_q, destroy the wall at (i, C_q).
- If there exists an i \gt R_q such that a wall exists at (i, C_q) and no wall exists at (k, C_q) for all R_q \lt k \lt i, destroy the wall at (i, C_q).
- If there exists a j \lt C_q such that a wall exists at (R_q, j) and no wall exists at (R_q, k) for all j \lt k \lt C_q, destroy the wall at (R_q, j).
- If there exists a j \gt C_q such that a wall exists at (R_q, j) and no wall exists at (R_q, k) for all C_q \lt k \lt j, destroy the wall at (R_q, j).

Constraints

1 \leq H, W
H \times W \leq 4 \times 10^5
1 \leq Q \leq 2 \times 10^5
1 \leq R_q \leq H
1 \leq C_q \leq W
All input values are integers.

Input

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

H W Q
R_1 C_1
R_2 C_2
\vdots
R_Q C_Q

Output

Print the number of remaining walls after processing all queries.

Sample Input 1

Sample Output 1

The process of handling the queries can be explained as follows:

In the 1st query, (R_1, C_1) = (1, 2). There is a wall at (1, 2), so the wall at (1, 2) is destroyed.
In the 2nd query, (R_2, C_2) = (1, 2). There is no wall at (1, 2), so the walls at (2,2),(1,1),(1,3), which are the first walls that appear when looking up, down, left, and right from (1, 2), are destroyed.
In the 3rd query, (R_3, C_3) = (1, 3). There is no wall at (1, 3), so the walls at (2,3),(1,4), which are the first walls that appear when looking up, down, left, and right from (1, 3), are destroyed.

After processing all queries, there are two remaining walls, at (2, 1) and (2, 4).

Sample Input 2

Sample Output 2

Sample Input 3