AtCoder Daily Training EASY 2025/03/04 15:30start

A - Median?

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

整数 a, b, c が与えられます。b がこれらの整数の中央値であるかどうか判定してください。

制約

1 \leq a, b, c \leq 100
入力は全て整数

入力

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

a b c

出力

b が与えられた整数の中央値であるならば Yes、そうでないならば No と出力せよ。

入力例 1

5 3 2

出力例 1

Yes

与えられた整数を小さい順に並べると 2, 3, 5 となり、b はこれらの整数の中央値です。

入力例 2

2 5 3

出力例 2

No

b は与えられた整数の中央値ではありません。

入力例 3

100 100 100

出力例 3

Yes

Score : 100 points

Problem Statement

Given integers a, b, and c, determine if b is the median of these integers.

Constraints

1 \leq a, b, c \leq 100
All values in input are integers.

Input

Input is given from Standard Input in the following format:

a b c

Output

If b is the median of the given integers, then print Yes; otherwise, print No.

Sample Input 1

5 3 2

Sample Output 1

Yes

The given integers are 2, 3, 5 when sorted in ascending order, of which b is the median.

Sample Input 2

2 5 3

Sample Output 2

No

b is not the median of the given integers.

Sample Input 3

100 100 100

Sample Output 3

Yes

B - September

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

英小文字からなる 12 個の文字列 S_1,S_2,\ldots,S_{12} があります。

S_i の長さが i であるような整数 i (1 \leq i \leq 12) がいくつあるか求めてください。

制約

S_i は英小文字からなる長さ 1 以上 100 以下の文字列である。(1 \leq i \leq 12)

入力

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

S_1
S_2
\vdots
S_{12}

出力

S_i の長さが i であるような整数 i (1 \leq i \leq 12) がいくつあるか出力せよ。

入力例 1

january
february
march
april
may
june
july
august
september
october
november
december

出力例 1

S_i の長さが i であるような整数 i は 9 の 1 つのみです。よって、1 と出力します。

入力例 2

ve
inrtfa
npccxva
djiq
lmbkktngaovl
mlfiv
fmbvcmuxuwggfq
qgmtwxmb
jii
ts
bfxrvs
eqvy

出力例 2

S_i の長さが i であるような整数 i は 4,8 の 2 つです。よって、2 と出力します。

Score : 100 points

Problem Statement

There are 12 strings S_1, S_2, \ldots, S_{12} consisting of lowercase English letters.

Find how many integers i (1 \leq i \leq 12) satisfy that the length of S_i is i.

Constraints

Each S_i is a string of length between 1 and 100, inclusive, consisting of lowercase English letters. (1 \leq i \leq 12)

Input

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

S_1
S_2
\vdots
S_{12}

Output

Print the number of integers i (1 \leq i \leq 12) such that the length of S_i is i.

Sample Input 1

january
february
march
april
may
june
july
august
september
october
november
december

Sample Output 1

There is only one integer i such that the length of S_i is i: 9. Thus, print 1.

Sample Input 2

ve
inrtfa
npccxva
djiq
lmbkktngaovl
mlfiv
fmbvcmuxuwggfq
qgmtwxmb
jii
ts
bfxrvs
eqvy

Sample Output 2

There are two integers i such that the length of S_i is i: 4 and 8. Thus, print 2.

C - First Query Problem

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

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

クエリが Q 個与えられるので、与えられた順番に処理してください。クエリは次の 2 種類のいずれかです。

1 k x : A _ k の値を x に変更する。
2 k : A _ k の値を出力する。

制約

1 \leq N \leq 10 ^ 5
1 \leq Q \leq 10 ^ 5
0 \leq A _ i \leq 10 ^ 9\ (1\leq i\leq N)
どのクエリについても、1\leq k\leq N
1 番目の形式のクエリについて、0\leq x\leq 10 ^ 9
2 番目の形式のクエリが 1 つ以上存在する
入力はすべて整数

入力

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

N
A _ 1 A _ 2 \ldots A _ N
Q
\operatorname{query} _ 1
\operatorname{query} _ 2
\vdots
\operatorname{query} _ Q

ただし、\operatorname{query} _ i は i 個目のクエリを表しており、次の形式のいずれかで与えられる。

1 k x

2 k

出力

2 番目の形式のクエリの回数を q 回として q 行出力せよ。 j\ (1\leq j\leq q) 行目には、2 番目の形式のクエリのうち j 個目のものに対する答えを出力せよ。

入力例 1

出力例 1

はじめ、A=(1,3,5) です。

1 つめのクエリにおいて、A=(1,3,5) です。A _ 2=3 なので、3 を出力します。
2 つめのクエリにおいて、A=(1,3,5) です。A _ 3=5 なので、5 を出力します。
3 つめのクエリでは、A _ 3 の値を 0 に変更し、A=(1,3,0) となります。
4 つめのクエリにおいて、A=(1,3,0) です。A _ 3=0 なので、0 を出力します。
5 つめのクエリでは、A _ 2 の値を 8 に変更し、A=(1,8,0) となります。
6 つめのクエリにおいて、A=(1,8,0) です。A _ 2=8 なので、8 を出力します。
7 つめのクエリにおいて、A=(1,8,0) です。A _ 1=1 なので、1 を出力します。

入力例 2

5
22 2 16 7 30
10
1 4 0
1 5 0
2 2
2 3
2 4
2 5
1 4 100
1 5 100
2 3
2 4

出力例 2

入力例 3

7
478 369 466 343 541 42 165
20
2 1
1 7 729
1 6 61
1 6 838
1 3 319
1 4 317
2 4
1 1 673
1 3 176
1 5 250
1 1 468
2 6
1 7 478
1 5 595
2 6
1 6 599
1 6 505
2 3
2 5
2 1

出力例 3

Score : 200 points

Problem Statement

You are given an integer N and a sequence A=(A _ 1,A _ 2,\ldots,A _ N) of length N.

Given Q queries, process them in the given order. Each query is of one of the following two kinds:

1 k x : set the value A _ k to x.
2 k : print the value A _ k.

Constraints

1 \leq N \leq 10 ^ 5
1 \leq Q \leq 10 ^ 5
0 \leq A _ i \leq 10 ^ 9\ (1\leq i\leq N)
1\leq k\leq N for all queries.
0\leq x\leq 10 ^ 9 for all queries of the first kind.
There is at least one query of the second kind.
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
Q
\operatorname{query} _ 1
\operatorname{query} _ 2
\vdots
\operatorname{query} _ Q

Here, \operatorname{query} _ i denotes the i-th query, given in one of the following formats:

1 k x

2 k

Output

Print q lines, where q is the number of queries of the second kind. The j-th (1\leq j\leq q) line should contain the response to the j-th such query.

Sample Input 1

Sample Output 1

Initially, A=(1,3,5).

For the 1-st query, A=(1,3,5), where A _ 2=3, so 3 should be printed.
For the 2-nd query, A=(1,3,5), where A _ 3=5, so 5 should be printed.
The 3-rd query sets the value A _ 3 to 0, making A=(1,3,0).
For the 4-th query, A=(1,3,0), where A _ 3=0, so 0 should be printed.
The 5-th query sets the value A _ 2 to 8, making A=(1,8,0).
For the 6-th query, A=(1,8,0), where A _ 2=8, so 8 should be printed.
For the 7-th query, A=(1,8,0), where A _ 1=1, so 1 should be printed.

Sample Input 2

5
22 2 16 7 30
10
1 4 0
1 5 0
2 2
2 3
2 4
2 5
1 4 100
1 5 100
2 3
2 4

Sample Output 2

Sample Input 3

7
478 369 466 343 541 42 165
20
2 1
1 7 729
1 6 61
1 6 838
1 3 319
1 4 317
2 4
1 1 673
1 3 176
1 5 250
1 1 468
2 6
1 7 478
1 5 595
2 6
1 6 599
1 6 505
2 3
2 5
2 1

Sample Output 3

D - A Reverse

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

整数 L,R と、英小文字のみからなる文字列 S が与えられます。
S の L 文字目から R 文字目までの部分を反転した(すなわち、 L 文字目から R 文字目までの文字の並びを逆にした)文字列を出力してください。

制約

S は英小文字のみからなる。
1 \le |S| \le 10^5 (|S| は S の長さ)
L,R は整数
1 \le L \le R \le |S|

入力

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

L R
S

出力

問題文の指示通り出力せよ。

入力例 1

3 7
abcdefgh

出力例 1

abgfedch

abcdefgh の 3 文字目から 7 文字目までの部分を反転すると、 abgfedch となります。

入力例 2

1 7
reviver

出力例 2

reviver

操作を行った結果が元の文字列と同一であることもあります。

入力例 3

4 13
merrychristmas

出力例 3

meramtsirhcyrs

Score : 200 points

Problem Statement

You are given integers L, R, and a string S consisting of lowercase English letters.
Print this string after reversing (the order of) the L-th through R-th characters.

Constraints

S consists of lowercase English letters.
1 \le |S| \le 10^5 (|S| is the length of S.)
L and R are integers.
1 \le L \le R \le |S|

Input

Input is given from Standard Input in the following format:

L R
S

Output

Print the specified string.

Sample Input 1

3 7
abcdefgh

Sample Output 1

abgfedch

After reversing the 3-rd through 7-th characters of abcdefgh, we have abgfedch.

Sample Input 2

1 7
reviver

Sample Output 2

reviver

The operation may result in the same string as the original.

Sample Input 3

4 13
merrychristmas

Sample Output 3

meramtsirhcyrs

E - Make Takahashi Happy

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

H 行 W 列のマス目があります。 1 \leq i \leq H かつ 1 \leq j \leq W を満たす 2 つの整数 i, j について、上から i 行目、左から j 列目のマス（以下、(i, j) と表す）には、整数 A_{i, j} が書かれています。

いま、高橋君は (1, 1) にいます。これから高橋君は「いまいるマスから右または下に隣接するマスに移動する」ことを繰り返して、(H, W) まで移動します。ただし、その過程でマス目の外部に移動することは出来ません。

その結果、高橋君が通ったマス（始点 (1, 1) と終点 (H, W) を含む）に書かれた整数がすべて異なるとき、高橋君は嬉しくなります。高橋君の移動経路として考えられるもののうち、高橋君が嬉しくなるものの個数を出力してください。

制約

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

入力

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

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

出力

答えを出力せよ。

入力例 1

出力例 1

高橋君の移動経路として考えられるものは下記の 6 通りです。

(1, 1) \rightarrow (1, 2) \rightarrow (1, 3) \rightarrow (2, 3) \rightarrow (3, 3)：通ったマスに書かれた整数は 3, 2, 2, 3, 4 であり、高橋君は嬉しくなりません。
(1, 1) \rightarrow (1, 2) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (3, 3)：通ったマスに書かれた整数は 3, 2, 1, 3, 4 であり、高橋君は嬉しくなりません。
(1, 1) \rightarrow (1, 2) \rightarrow (2, 2) \rightarrow (3, 2) \rightarrow (3, 3)：通ったマスに書かれた整数は 3, 2, 1, 5, 4 であり、高橋君は嬉しくなります。
(1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (3, 3)：通ったマスに書かれた整数は 3, 2, 1, 3, 4 であり、高橋君は嬉しくなりません。
(1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (3, 2) \rightarrow (3, 3)：通ったマスに書かれた整数は 3, 2, 1, 5, 4 であり、高橋君は嬉しくなります。
(1, 1) \rightarrow (2, 1) \rightarrow (3, 1) \rightarrow (3, 2) \rightarrow (3, 3)：通ったマスに書かれた整数は 3, 2, 1, 5, 4 であり、高橋君は嬉しくなります。

よって、高橋君が嬉しくなる移動経路は、上で 3, 5, 6 番目に述べた 3 個です。

入力例 2

10 10
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80
81 82 83 84 85 86 87 88 89 90
91 92 93 94 95 96 97 98 99 100

出力例 2

この例では、高橋君は考えられるどの経路を通っても嬉しくなります。

Score : 300 points

Problem Statement

There is a grid with H horizontal rows and W vertical columns. For two integers i and j such that 1 \leq i \leq H and 1 \leq j \leq W, the square at the i-th row from the top and j-th column from the left (which we denote by (i, j)) has an integer A_{i, j} written on it.

Takahashi is currently at (1,1). From now on, he repeats moving to an adjacent square to the right of or below his current square until he reaches (H, W). When he makes a move, he is not allowed to go outside the grid.

Takahashi will be happy if the integers written on the squares he visits (including initial (1, 1) and final (H, W)) are distinct. Find the number of his possible paths that make him happy.

Constraints

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

Input

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

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

Output

Print the answer.

Sample Input 1

Sample Output 1

There are six possible paths:

(1, 1) \rightarrow (1, 2) \rightarrow (1, 3) \rightarrow (2, 3) \rightarrow (3, 3): the integers written on the squares he visits are 3, 2, 2, 3, 4, so he will not be happy.
(1, 1) \rightarrow (1, 2) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (3, 3): the integers written on the squares he visits are 3, 2, 1, 3, 4, so he will not be happy.
(1, 1) \rightarrow (1, 2) \rightarrow (2, 2) \rightarrow (3, 2) \rightarrow (3, 3): the integers written on the squares he visits are 3, 2, 1, 5, 4, so he will be happy.
(1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (3, 3): the integers written on the squares he visits are 3, 2, 1, 3, 4, so he will not be happy.
(1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (3, 2) \rightarrow (3, 3): the integers written on the squares he visits are 3, 2, 1, 5, 4, so he will be happy.
(1, 1) \rightarrow (2, 1) \rightarrow (3, 1) \rightarrow (3, 2) \rightarrow (3, 3): the integers written on the squares he visits are 3, 2, 1, 5, 4, so he will be happy.

Thus, the third, fifth, and sixth paths described above make him happy.

Sample Input 2

10 10
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80
81 82 83 84 85 86 87 88 89 90
91 92 93 94 95 96 97 98 99 100

Sample Output 2

In this example, every possible path makes him happy.