AtCoder Daily Training MEDIUM 2025/06/11 16:00start

C - Base K

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

配点 : 200 点

問題文

整数 A,B が K 進法表記で与えられます。
A \times B を 10 進法表記で出力してください。

注記

K 進法表記については、Wikipedia「位取り記数法」を参照してください。

制約

2 \leq K \leq 10
1 \leq A,B \leq 10^5
A,B は K 進法表記で与えられる

入力

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

K
A B

出力

答えを出力せよ。

入力例 1

2
1011 10100

出力例 1

2 進法表記の 1011 を、10 進法表記すると 11 です。
2 進法表記の 10100 を、 10 進法表記すると 20 です。
11 \times 20 = 220 なので 220 を出力します。

入力例 2

7
123 456

出力例 2

7 進法表記の 123 を、10 進法表記すると 66 です。
7 進法表記の 456 を、 10 進法表記すると 237 です。
66 \times 237 = 15642 なので 15642 を出力します。

Score : 200 points

Problem Statement

You are given integers A and B, in base K.
Print A \times B in decimal.

Notes

For base-K representation, see Wikipedia's article on Positional notation.

Constraints

2 \leq K \leq 10
1 \leq A,B \leq 10^5
A and B are in base-K representation.

Input

Input is given from Standard Input in the following format:

K
A B

Output

Print the answer.

Sample Input 1

2
1011 10100

Sample Output 1

1011 in base 2 corresponds to 11 in base 10.
10100 in base 2 corresponds to 20 in base 10.
We have 11 \times 20 = 220, so print 220.

Sample Input 2

7
123 456

Sample Output 2

123 in base 7 corresponds to 66 in base 10.
456 in base 7 corresponds to 237 in base 10.
We have 66 \times 237 = 15642, so print 15642.

D - The Middle Day

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

配点 : 200 点

問題文

AtCoder 国の暦では、一年は 1,2,\dots,M 番目の月の M か月からなり、そのうち i 番目の月は 1,2,\dots,D_i 番目の日の D_i 日からなります。
さらに、 AtCoder 国の一年の日数は奇数、即ち D_1+D_2+\dots+D_M は奇数です。
一年の真ん中の日は何番目の月の何番目の日か求めてください。
言い換えると、 1 番目の月の 1 番目の日を 1 日目としたときの (D_1+D_2+\dots+D_M+1)/2 日目が何番目の月の何番目の日かを求めてください。

制約

入力は全て整数
1 \le M \le 100
1 \le D_i \le 100
D_1 + D_2 + \dots + D_M は奇数

入力

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

M
D_1 D_2 \dots D_M

出力

答えが a 番目の月の b 番目の日であるとき、以下の形式で出力せよ。

a b

入力例 1

12
31 28 31 30 31 30 31 31 30 31 30 31

出力例 1

7 2

この入力では、 1 年は 31+28+31+30+31+30+31+31+30+31+30+31=365 日からなります。
真ん中の日は (365+1)/2 = 183 日目であり、これを求めることを考えます。

1,2,3,4,5,6 番目の月に含まれる日数の合計は 181 日です。
7 番目の月の 1 番目の日は 182 日目です。
7 番目の月の 2 番目の日は 183 日目です。

以上から、答えが 7 番目の月の 2 番目の日であることが分かります。

入力例 2

1
1

出力例 2

1 1

入力例 3

6
3 1 4 1 5 9

出力例 3

5 3

Score : 200 points

Problem Statement

In the calendar of AtCoderLand, a year consists of M months: month 1, month 2, \dots, month M. The i-th month consists of D_i days: day 1, day 2, \dots, day D_i.
Furthermore, the number of days in a year is odd, that is, D_1+D_2+\dots+D_M is odd.
Find what day of what month is the middle day of the year.
In other words, let day 1 of month 1 be the first day, and find a and b such that the ((D_1+D_2+\dots+D_M+1)/2)-th day is day b of month a.

Constraints

All input values are integers.
1 \le M \le 100
1 \le D_i \le 100
D_1 + D_2 + \dots + D_M is odd.

Input

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

M
D_1 D_2 \dots D_M

Output

Let the answer be day b of month a, and print it in the following format:

a b

Sample Input 1

12
31 28 31 30 31 30 31 31 30 31 30 31

Sample Output 1

7 2

In this input, a year consists of 31+28+31+30+31+30+31+31+30+31+30+31=365 days.
Let us find the middle day, which is the ((365+1)/2 = 183)-th day.

Months 1,2,3,4,5,6 contain a total of 181 days.
Day 1 of month 7 is the 182-th day.
Day 2 of month 7 is the 183-th day.

Thus, the answer is day 2 of month 7.

Sample Input 2

1
1

Sample Output 2

1 1

Sample Input 3

6
3 1 4 1 5 9

Sample Output 3

5 3

E - Belt Conveyor

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

配点 : 300 点

問題文

縦 H マス、横 W マスのグリッドがあります。上から i 行目、左から j 列目のマスを (i,j) と表します。
(i,j) には文字 G_{i,j} が書きこまれています。ここで G_{i,j} は U, D, L, R のいずれかです。

あなたは (1,1) にいます。あなたは移動することができなくなるまで次の操作を繰り返します。

あなたは現在 (i,j) にいるとする。
G_{i,j} が U であり、かつ i \neq 1 ならば (i-1,j) へ移動する。
G_{i,j} が D であり、かつ i \neq H ならば (i+1,j) へ移動する。
G_{i,j} が L であり、かつ j \neq 1 ならば (i,j-1) へ移動する。
G_{i,j} が R であり、かつ j \neq W ならば (i,j+1) へ移動する。
それ以外の場合、あなたは移動することができない。

操作を終了した時点であなたがいるマスを出力してください。
ただし、あなたが操作を終了することなく無限に移動し続ける場合は -1 を出力してください。

制約

1 \leq H, W \leq 500
G_{i,j} は U, D, L, R のいずれかである。
H, W は整数である。

入力

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

H W
G_{1,1}G_{1,2}\dots G_{1,W}
G_{2,1}G_{2,2}\dots G_{2,W}
\vdots
G_{H,1}G_{H,2}\dots G_{H,W}

出力

操作を終了した時点であなたが (i,j) にいる場合は次の形式で出力せよ。

i j

また、無限に動き続ける場合は -1 を出力せよ。

入力例 1

2 3
RDU
LRU

出力例 1

1 3

あなたは (1, 1) \to (1, 2) \to (2, 2) \to (2, 3) \to (1, 3) の順に動いたあとに操作を終了します。よって答えは (1, 3) です。

入力例 2

2 3
RRD
ULL

出力例 2

-1

あなたは (1, 1) \to (1, 2) \to (1, 3) \to (2, 3) \to (2, 2) \to (2, 1) \to (1, 1) \to (1, 2) \to \dots というように無限に動き続けます。この場合は -1 を出力します。

入力例 3

9 44
RRDDDDRRRDDDRRRRRRDDDRDDDDRDDRDDDDDDRRDRRRRR
RRRDLRDRDLLLLRDRRLLLDDRDLLLRDDDLLLDRRLLLLLDD
DRDLRLDRDLRDRLDRLRDDLDDLRDRLDRLDDRLRRLRRRDRR
DDLRRDLDDLDDRLDDLDRDDRDDDDRLRRLRDDRRRLDRDRDD
RDLRRDLRDLLLLRRDLRDRRDRRRDLRDDLLLLDDDLLLLRDR
RDLLLLLRDLRDRLDDLDDRDRRDRLDRRRLDDDLDDDRDDLDR
RDLRRDLDDLRDRLRDLDDDLDDRLDRDRDLDRDLDDLRRDLRR
RDLDRRLDRLLLLDRDRLLLRDDLLLLLRDRLLLRRRRLLLDDR
RRRRDRDDRRRDDRDDDRRRDRDRDRDRRRRRRDDDRDDDDRRR

出力例 3

9 5

Score : 300 points

Problem Statement

We have a grid with H horizontal rows and W vertical columns. (i, j) denotes the square at the i-th row from the top and j-th column from the left.
(i,j) has a character G_{i,j} written on it. G_{i,j} is U, D, L, or R.

You are initially at (1,1). You repeat the following operation until you cannot make a move.

Let (i,j) be the square you are currently at.
If G_{i,j} is U and i \neq 1, move to (i-1,j).
If G_{i,j} is D and i \neq H, move to (i+1,j).
If G_{i,j} is L and j \neq 1, move to (i,j-1).
If G_{i,j} is R and j \neq W, move to (i,j+1).
Otherwise, you cannot make a move.

Print the square you end up at when you cannot make a move.
If you indefinitely repeat moving, print -1 instead.

Constraints

1 \leq H, W \leq 500
G_{i,j} is U, D, L, or R.
H and W are integers.

Input

Input is given from Standard Input in the following format:

H W
G_{1,1}G_{1,2}\dots G_{1,W}
G_{2,1}G_{2,2}\dots G_{2,W}
\vdots
G_{H,1}G_{H,2}\dots G_{H,W}

Output

If you end up at (i, j), print it in the following format:

i j

If you indefinitely repeat moving, print -1.

Sample Input 1

2 3
RDU
LRU

Sample Output 1

1 3

You will move as (1, 1) \to (1, 2) \to (2, 2) \to (2, 3) \to (1, 3), ending up here, so the answer is (1, 3).

Sample Input 2

2 3
RRD
ULL

Sample Output 2

-1

You will indefinitely repeat moving as (1, 1) \to (1, 2) \to (1, 3) \to (2, 3) \to (2, 2) \to (2, 1) \to (1, 1) \to (1, 2) \to \dots, so -1 should be printed in this case.

Sample Input 3

9 44
RRDDDDRRRDDDRRRRRRDDDRDDDDRDDRDDDDDDRRDRRRRR
RRRDLRDRDLLLLRDRRLLLDDRDLLLRDDDLLLDRRLLLLLDD
DRDLRLDRDLRDRLDRLRDDLDDLRDRLDRLDDRLRRLRRRDRR
DDLRRDLDDLDDRLDDLDRDDRDDDDRLRRLRDDRRRLDRDRDD
RDLRRDLRDLLLLRRDLRDRRDRRRDLRDDLLLLDDDLLLLRDR
RDLLLLLRDLRDRLDDLDDRDRRDRLDRRRLDDDLDDDRDDLDR
RDLRRDLDDLRDRLRDLDDDLDDRLDRDRDLDRDLDDLRRDLRR
RDLDRRLDRLLLLDRDRLLLRDDLLLLLRDRLLLRRRRLLLDDR
RRRRDRDDRRRDDRDDDRRRDRDRDRDRRRRRRDDDRDDDDRRR

Sample Output 3

9 5

F - Debug

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

配点 : 300 点

問題文

英大文字のみからなる文字列 S が与えられます。
S に対して、次の手順を行った後に得られる文字列を出力してください。

文字列が WA を（連続する）部分文字列として含む限り、次の操作を繰り返す。

文字列中に登場する WA のうち最も先頭のものを AC に置換する。

なお、本問題の制約下で、この操作は高々有限回しか繰り返されないことが証明できます。

制約

S は長さ 1 以上 3\times 10^5 以下の英大文字のみからなる文字列

入力

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

出力

S に対して、問題文中に記された手順を行った後に得られる文字列を出力せよ。

入力例 1

WACWA

出力例 1

ACCAC

最初、文字列は S=WACWA です。
この文字列には 1 文字目から 2 文字目、および、4 文字目から 5 文字目の 2 ヶ所に WA が部分文字列として含まれています。
1 回目の操作では、そのうち先頭のもの、すなわち 1 文字目から 2 文字目の部分を AC に置換し、文字列は ACCWA となります。
1 回目の操作後の文字列には 4 文字目から 5 文字目の 1 ヶ所にのみ WA が部分文字列として含まれているため、2 回目の操作ではこれを AC に置換し、文字列は ACCAC となります。
ACCAC は WA を部分文字列として含まないため、手順は終了します。よって、ACCAC を出力します。

入力例 2

WWA

出力例 2

ACC

最初、文字列は S=WWA です。
この文字列には 2 文字目から 3 文字目の 1 ヶ所にのみ WA が部分文字列として含まれているため、1 回目の操作ではこれを AC に置換し、文字列は WAC となります。
次に、1 回目の操作後の文字列は 1 文字目から 2 文字目の 1 ヶ所にのみ WA が部分文字列として含まれているため、2 回目の操作ではこれを AC に置換し、文字列は ACC となります。
ACC は WA を部分文字列として含まないため、手順は終了します。よって、ACC を出力します。

入力例 3

WWWWW

出力例 3

WWWWW

S には最初から WA が部分文字列として含まれてないため、操作は 1 回も行われず手順は終了します。よって、WWWWW を出力します。

Score : 300 points

Problem Statement

You are given a string S consisting of uppercase English letters.
Apply the following procedure to S, and then output the resulting string:

As long as the string contains WA as a (contiguous) substring, repeat the following operation:

Among all occurrences of WA in the string, replace the leftmost one with AC.

It can be proved under the constraints of this problem that this operation is repeated at most a finite number of times.

Constraints

S is a string of uppercase English letters with length between 1 and 3\times 10^5, inclusive.

Input

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

Output

Print the resulting string after performing the procedure described in the problem statement on S.

Sample Input 1

WACWA

Sample Output 1

ACCAC

Initially, the string is S= WACWA.
This string contains WA as a substring in two places: from the 1st to the 2nd character, and from the 4th to the 5th character.
In the first operation, we replace the leftmost occurrence (the substring from the 1st to the 2nd character) with AC, resulting in ACCWA.
After the first operation, the string contains WA as a substring in exactly one place: from the 4th to the 5th character.
In the second operation, we replace it with AC, resulting in ACCAC.
Since ACCAC does not contain WA as a substring, the procedure ends. Therefore, we output ACCAC.

Sample Input 2

WWA

Sample Output 2

ACC

Initially, the string is S= WWA.
This string contains WA as a substring in exactly one place: from the 2nd to the 3rd character.
In the first operation, we replace it with AC, resulting in WAC.
Then, after the first operation, the string contains WA in exactly one place: from the 1st to the 2nd character.
In the second operation, we replace it with AC, resulting in ACC.
Since ACC does not contain WA as a substring, the procedure ends. Therefore, we output ACC.

Sample Input 3

WWWWW

Sample Output 3

WWWWW

Since S does not contain WA as a substring from the start, no operations are performed and the procedure ends immediately. Therefore, we output WWWWW.

G - Many Segments 2

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

配点 : 400 点

問題文

長さ N の正整数列 L=(L_1,L_2,\ldots,L_N), R=(R_1,R_2,\ldots,R_N) と整数 M が与えられます。

以下の条件を共に満たす整数の組 (l,r) の個数を求めてください。

1\le l \le r \le M
全ての 1\le i\le N に対し区間 [l,r] は区間 [L_i,R_i] を完全には含まない。

制約

1\le N,M\le 2\times 10^5
1\le L_i\le R_i\le M
入力は全て整数

入力

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

N M
L_1 R_1
L_2 R_2
\vdots
L_N R_N

出力

答えを出力せよ。

入力例 1

2 4
1 2
3 4

出力例 1

(l,r)=(1,1),(2,2),(2,3),(3,3),(4,4) の 5 つが条件を満たします。

例えば (l,r)=(1,3) は条件を満たしません。これは、区間 [1,3] が区間 [1,2] を完全に含んでいるためです。

入力例 2

出力例 2

条件を満たす整数の組が存在しない場合もあります。

入力例 3

出力例 3

Score : 400 points

Problem Statement

You are given two sequences of positive integers of length N, L=(L_1,L_2,\ldots,L_N) and R=(R_1,R_2,\ldots,R_N), and an integer M.

Find the number of pairs of integers (l,r) that satisfy both of the following conditions:

1\le l \le r \le M
For every 1\le i\le N, the interval [l,r] does not completely contain the interval [L_i,R_i].

Constraints

1\le N,M\le 2\times 10^5
1\le L_i\le R_i\le M
All input values are integers.

Input

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

N M
L_1 R_1
L_2 R_2
\vdots
L_N R_N

Output

Print the answer.

Sample Input 1

2 4
1 2
3 4

Sample Output 1

The five pairs (l,r)=(1,1),(2,2),(2,3),(3,3),(4,4) satisfy the conditions.

For example, (l,r)=(1,3) does not satisfy the conditions because the interval [1,3] completely contains the interval [1,2].

Sample Input 2

Sample Output 2

There may be cases where no pairs of integers satisfy the conditions.

Sample Input 3