AtCoder Daily Training MEDIUM 2023/11/2316:30start

C - Cat

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

配点 : 200 点

問題文

長さ N の文字列 S が与えられます。

S に連続して含まれる na を全て nya に置き換えて得られる文字列を答えてください。

制約

N は 1 以上 1000 以下の整数
S は英小文字からなる長さ N の文字列

入力

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

N
S

出力

答えを出力せよ。

入力例 1

4
naan

出力例 1

nyaan

naan に連続して含まれる na を全て nya に置き換えて得られる文字列は nyaan です。

入力例 2

4
near

出力例 2

near

S に na が連続して含まれないこともあります。

入力例 3

8
national

出力例 3

nyationyal

Score : 200 points

Problem Statement

You are given a string S of length N.

Find the string obtained by replacing all contiguous occurrences of na in S with nya.

Constraints

N is an integer between 1 and 1000, inclusive.
S is a string of length N consisting of lowercase English letters.

Input

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

N
S

Output

Print the answer.

Sample Input 1

4
naan

Sample Output 1

nyaan

Replacing all contiguous occurrences of na in naan with nya results in the string nyaan.

Sample Input 2

4
near

Sample Output 2

near

S may not contain a contiguous na.

Sample Input 3

8
national

Sample Output 3

nyationyal

D - typo

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

配点 : 200 点

問題文

文字列 S, T が与えられます。以下の操作を高々 1 回行うことで、S を T と一致させることができるかを判定してください。

S の隣り合う 2 文字を選び、入れ替える。

なお、上記の操作を一度も行わないことも可能です。

制約

S, T はそれぞれ英小文字のみからなる、長さ 2 以上 100 以下の文字列
S の長さと T の長さは等しい

入力

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

S
T

出力

問題文中の操作を高々 1 回行うことで S を T と一致させることができるなら Yes を、できないなら No を出力せよ。

入力例 1

abc
acb

出力例 1

Yes

S の 2 文字目と 3 文字目を入れ替えることで、S を T と一致させることができます。

入力例 2

aabb
bbaa

出力例 2

No

どのように操作を行っても、S を T と一致させることはできません。

入力例 3

abcde
abcde

出力例 3

Yes

S と T は既に一致しています。

Score : 200 points

Problem Statement

You are given two strings S and T. Determine whether it is possible to make S and T equal by doing the following operation at most once:

choose two adjacent characters in S and swap them.

Note that it is allowed to choose not to do the operation.

Constraints

Each of S and T is a string of length between 2 and 100 (inclusive) consisting of lowercase English letters.
S and T have the same length.

Input

Input is given from Standard Input in the following format:

S
T

Output

If it is possible to make S and T equal by doing the operation in Problem Statement at most once, print Yes; otherwise, print No.

Sample Input 1

abc
acb

Sample Output 1

Yes

You can swap the 2-nd and 3-rd characters of S to make S and T equal.

Sample Input 2

aabb
bbaa

Sample Output 2

No

There is no way to do the operation to make S and T equal.

Sample Input 3

abcde
abcde

Sample Output 3

Yes

S and T are already equal.

E - Collision 2

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

配点 : 300 点

問題文

xy 座標平面上に N 人の人がいます。人 i は (X_i, Y_i) にいます。すべての人は異なる地点にいます。

L, R からなる長さ N の文字列 S があります。
人 i は S_i = R ならば右向きに、S_i = L ならば左向きに、一斉に同じ速度で歩き始めます。ここで、右は x 軸の正の向き、左は x 軸の負の向きです。

たとえば (X_1, Y_1) = (2, 3), (X_2, Y_2) = (1, 1), (X_3, Y_3) =(4, 1), S = RRL の場合は次の図のように動きます。

反対の向きに歩いている人同士が同じ地点に来ることを「衝突」と呼びます。すべての人が歩き続けたとき、衝突は発生しますか？

制約

2 \leq N \leq 2 \times 10^5
0 \leq X_i \leq 10^9
0 \leq Y_i \leq 10^9
i \neq j ならば (X_i, Y_i) \neq (X_j, Y_j) である。
X_i, Y_i はすべて整数である。
S は L および R からなる長さ N の文字列である。

入力

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

N
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N
S

出力

衝突が発生するならば Yes を、発生しないならば No を出力せよ。

入力例 1

出力例 1

Yes

この入力は問題文にある例と同じケースです。
すべての人が歩き続けると人 2 と人 3 が衝突します。よって Yes を出力します。

入力例 2

出力例 2

No

人 1 と人 2 は同じ向きに歩いているので衝突することはありません。

入力例 3

出力例 3

Yes

Score : 300 points

Problem Statement

There are N people in an xy-plane. Person i is at (X_i, Y_i). The positions of all people are different.

We have a string S of length N consisting of L and R.
If S_i = R, Person i is facing right; if S_i = L, Person i is facing left. All people simultaneously start walking in the direction they are facing. Here, right and left correspond to the positive and negative x-direction, respectively.

For example, the figure below shows the movement of people when (X_1, Y_1) = (2, 3), (X_2, Y_2) = (1, 1), (X_3, Y_3) =(4, 1), S = RRL.

We say that there is a collision when two people walking in opposite directions come to the same position. Will there be a collision if all people continue walking indefinitely?

Constraints

2 \leq N \leq 2 \times 10^5
0 \leq X_i \leq 10^9
0 \leq Y_i \leq 10^9
(X_i, Y_i) \neq (X_j, Y_j) if i \neq j.
All X_i and Y_i are integers.
S is a string of length N consisting of L and R.

Input

Input is given from Standard Input in the following format:

N
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N
S

Output

If there will be a collision, print Yes; otherwise, print No.

Sample Input 1

Sample Output 1

Yes

This input corresponds to the example in the Problem Statement.
If all people continue walking, Person 2 and Person 3 will collide. Thus, Yes should be printed.

Sample Input 2

Sample Output 2

No

Since Person 1 and Person 2 walk in the same direction, they never collide.

Sample Input 3

Sample Output 3

Yes

F - ±1 Operation 1

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

配点 : 300 点

問題文

整数 X が与えられます。この X に以下を施すことを「操作」と呼びます。

以下の 2 つのうちどちらかを選択し、実行する。
- X に 1 を加算する。
- X から 1 を減算する。

初項 A 、公差 D 、項数 N の等差数列 S に含まれる数を「良い数」と呼びます。
「操作」を 0 回以上何度でも使って X を「良い数」にする時、必要な「操作」の最小回数を求めてください。

制約

入力は全て整数
-10^{18} \le X,A \le 10^{18}
-10^6 \le D \le 10^6
1 \le N \le 10^{12}

入力

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

X A D N

出力

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

入力例 1

6 2 3 3

出力例 1

A=2,D=3,N=3 であるため、 S=(2,5,8) です。
X=6 を「良い数」にするためには、 X から 1 を減算することを 1 度行えば良いです。
0 回の操作で X を「良い数」にすることはできません。

入力例 2

0 0 0 1

出力例 2

D=0 である場合もあります。また、操作を 1 回も必要としない場合もあります。

入力例 3

998244353 -10 -20 30

出力例 3

998244363

入力例 4

-555555555555555555 -1000000000000000000 1000000 1000000000000

出力例 4

Score : 300 points

Problem Statement

You are given an integer X. The following action on this integer is called an operation.

Choose and do one of the following.
- Add 1 to X.
- Subtract 1 from X.

The terms in the arithmetic progression S with N terms whose initial term is A and whose common difference is D are called good numbers.
Consider performing zero or more operations to make X a good number. Find the minimum number of operations required to do so.

Constraints

All values in input are integers.
-10^{18} \le X,A \le 10^{18}
-10^6 \le D \le 10^6
1 \le N \le 10^{12}

Input

Input is given from Standard Input in the following format:

X A D N

Output

Print the answer as an integer.

Sample Input 1

6 2 3 3

Sample Output 1

Since A=2,D=3,N=3, we have S=(2,5,8).
You can subtract 1 from X once to make X=6 a good number.
It is impossible to make X good in zero operations.

Sample Input 2

0 0 0 1

Sample Output 2

We might have D=0. Additionally, no operation might be required.

Sample Input 3

998244353 -10 -20 30

Sample Output 3

998244363

Sample Input 4

-555555555555555555 -1000000000000000000 1000000 1000000000000

Sample Output 4

G - Happy New Year 2023

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

配点 : 400 点

問題文

正整数 N が与えられます。N は、2 つの相異なる素数 p,q を用いて N=p^2q と表せることがわかっています。

p,q を求めてください。

T 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

入力は全て整数
1\leq T\leq 10
1\leq N \leq 9\times 10^{18}
N は、2 つの相異なる素数 p,q を用いて N=p^2q と表せる

入力

入力は以下の形式で標準入力から与えられる。ここで \text{test}_i は i 番目のテストケースを意味する。

T
\text{test}_1
\text{test}_2
\vdots
\text{test}_T

各テストケースは以下の形式で与えられる。

出力

T 行出力せよ。

i\ (1\leq i \leq T) 行目には、i 番目のテストケースにおける p,q を空白区切りで出力せよ。なお、この問題の制約下では、N=p^2q を満たす素数 p,q の組は 1 通りしか存在しないことが証明できる。

入力例 1

3
2023
63
1059872604593911

出力例 1

17 7
3 7
104149 97711

1 番目のテストケースについて、N=2023=17^2\times 7 です。よって、p=17,q=7 です。

Score : 400 points

Problem Statement

You are given a positive integer N. It is known that N can be represented as N=p^2q using two different prime numbers p and q.

Find p and q.

You have T test cases to solve.

Constraints

All values in the input are integers.
1\leq T\leq 10
1\leq N \leq 9\times 10^{18}
N can be represented as N=p^2q using two different prime numbers p and q.

Input

The input is given from Standard Input in the following format, where \text{test}_i represents the i-th test case:

T
\text{test}_1
\text{test}_2
\vdots
\text{test}_T

Each test case is in the following format:

Output

Print T lines.

The i-th (1\leq i \leq T) line should contain p and q for the i-th test case, separated by a space. Under the constraints of this problem, it can be proved that the pair of prime numbers p and q such that N=p^2q is unique.

Sample Input 1

3
2023
63
1059872604593911

Sample Output 1

17 7
3 7
104149 97711

For the first test case, we have N=2023=17^2\times 7. Thus, p=17 and q=7.