AtCoder Daily Training MEDIUM 2024/04/16 17:30start

C - Counterclockwise Rotation

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

配点 : 200 点

問題文

x 軸の正の向きが右、y 軸の正の向きが上であるような xy 座標平面において、点 (a,b) を原点を中心として反時計回りに d 度回転させた点を求めてください。

制約

-1000 \leq a,b \leq 1000
1 \leq d \leq 360
入力はすべて整数

入力

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

a b d

出力

求めるべき点を (a',b') とするとき、 a' と b' をこの順に空白区切りで出力せよ。
なお、各出力について、解との絶対誤差または相対誤差が 10^{−6} 以下であれば正解として扱われる。

入力例 1

2 2 180

出力例 1

-2 -2

(2,2) を原点を中心として反時計回りに 180 度回転させた点は、(2,2) を原点について対称な位置に移動させた点であり、(-2,-2) となります。

入力例 2

5 0 120

出力例 2

-2.49999999999999911182 4.33012701892219364908

(5,0) を原点を中心として反時計回りに 120 度回転させた点は (-\frac {5}{2} , \frac {5\sqrt{3}}{2}) です。
この例での出力はこれらの値と厳密には一致しませんが、誤差が十分に小さいため正解として扱われます。

入力例 3

0 0 11

出力例 3

0.00000000000000000000 0.00000000000000000000

(a,b) が原点(回転の中心)なので回転させても座標が変わりません。

入力例 4

15 5 360

出力例 4

15.00000000000000177636 4.99999999999999555911

360 度回転させたので座標が変わりません。

入力例 5

-505 191 278

出力例 5

118.85878514480690171240 526.66743699786547949770

Score : 200 points

Problem Statement

In an xy-coordinate plane whose x-axis is oriented to the right and whose y-axis is oriented upwards, rotate a point (a, b) around the origin d degrees counterclockwise and find the new coordinates of the point.

Constraints

-1000 \leq a,b \leq 1000
1 \leq d \leq 360
All values in input are integers.

Input

Input is given from Standard Input in the following format:

a b d

Output

Let the new coordinates of the point be (a', b'). Print a' and b' in this order, with a space in between.
Your output will be considered correct when, for each value printed, the absolute or relative error from the answer is at most 10^{-6}.

Sample Input 1

2 2 180

Sample Output 1

-2 -2

When (2, 2) is rotated around the origin 180 degrees counterclockwise, it becomes the symmetric point of (2, 2) with respect to the origin, which is (-2, -2).

Sample Input 2

5 0 120

Sample Output 2

-2.49999999999999911182 4.33012701892219364908

When (5, 0) is rotated around the origin 120 degrees counterclockwise, it becomes (-\frac {5}{2} , \frac {5\sqrt{3}}{2}).
This sample output does not precisely match these values, but the errors are small enough to be considered correct.

Sample Input 3

0 0 11

Sample Output 3

0.00000000000000000000 0.00000000000000000000

Since (a, b) is the origin (the center of rotation), a rotation does not change its coordinates.

Sample Input 4

15 5 360

Sample Output 4

15.00000000000000177636 4.99999999999999555911

A 360-degree rotation does not change the coordinates of a point.

Sample Input 5

-505 191 278

Sample Output 5

118.85878514480690171240 526.66743699786547949770

D - 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

E - Count Connected Components

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

配点 : 300 点

問題文

頂点に 1 から N の番号が、辺に 1 から M の番号がついた N 頂点 M 辺の単純無向グラフが与えられます。辺 i は頂点 u_i と頂点 v_i を結んでいます。
グラフに含まれる連結成分の個数を求めてください。

注釈

単純無向グラフ とは、単純で辺に向きの無いグラフのことをいいます。
グラフが単純であるとは、グラフが自己ループや多重辺を含まないことをいいます。

あるグラフの 部分グラフ とは、元のグラフのいくつかの頂点といくつかの辺を選んでできるグラフのことをいいます。
グラフが連結であるとは、グラフに含まれるすべての頂点同士が辺を経由して互いに行き来できることをいいます。
連結成分 とは、連結な部分グラフのうち、そのグラフを含んだより大きい連結な部分グラフが存在しないものをいいます。

制約

1 \leq N \leq 100
0 \leq M \leq \frac{N(N - 1)}{2}
1 \leq u_i, v_i \leq N
入力で与えられるグラフは単純
入力される値はすべて整数

入力

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

N M
u_1 v_1
u_2 v_2
\vdots
u_M v_M

出力

答えを出力せよ。

入力例 1

出力例 1

与えられるグラフに含まれる連結成分は次の 2 個です。

頂点 1, 2, 3 および辺 1, 2 からなる部分グラフ
頂点 4, 5 および辺 3 からなる部分グラフ

入力例 2

5 0

出力例 2

入力例 3

出力例 3

Score : 300 points

Problem Statement

You are given a simple undirected graph with N vertices numbered 1 to N and M edges numbered 1 to M. Edge i connects vertex u_i and vertex v_i.
Find the number of connected components in this graph.

Notes

A simple undirected graph is a graph that is simple and has undirected edges.
A graph is simple if and only if it has no self-loop or multi-edge.

A subgraph of a graph is a graph formed from some of the vertices and edges of that graph.
A graph is connected if and only if one can travel between every pair of vertices via edges.
A connected component is a connected subgraph that is not part of any larger connected subgraph.

Constraints

1 \leq N \leq 100
0 \leq M \leq \frac{N(N - 1)}{2}
1 \leq u_i, v_i \leq N
The given graph is simple.
All values in the input are integers.

Input

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

N M
u_1 v_1
u_2 v_2
\vdots
u_M v_M

Output

Print the answer.

Sample Input 1

Sample Output 1

The given graph contains the following two connected components:

a subgraph formed from vertices 1, 2, 3, and edges 1, 2;
a subgraph formed from vertices 4, 5, and edge 3.

Sample Input 2

5 0

Sample Output 2

Sample Input 3

Sample Output 3

F - 1111gal password

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

配点 : 300 点

問題文

整数 N が与えられるので、以下の条件を全て満たす整数 X の個数を 998244353 で割った余りを求めてください。

N 桁の正整数である。
X の各桁を上の位から順に X_1,X_2,\dots,X_N とする。このとき以下の条件を全て満たす。
- 全ての整数 1 \le i \le N に対して、 1 \le X_i \le 9
- 全ての整数 1 \le i \le N-1 に対して、 |X_i-X_{i+1}| \le 1

制約

N は整数
2 \le N \le 10^6

入力

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

出力

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

入力例 1

出力例 1

4 桁の整数として、例えば 1111,1234,7878,6545 が問題文中の条件を満たします。

入力例 2

出力例 2

入力例 3

出力例 3

248860093

998244353 で割った余りを求めることに注意してください。

Score : 300 points

Problem Statement

Given an integer N, find the number of integers X that satisfy all of the following conditions, modulo 998244353.

X is an N-digit positive integer.
Let X_1,X_2,\dots,X_N be the digits of X from top to bottom. They satisfy all of the following:
- 1 \le X_i \le 9 for all integers 1 \le i \le N;
- |X_i-X_{i+1}| \le 1 for all integers 1 \le i \le N-1.

Constraints

N is an integer.
2 \le N \le 10^6

Input

Input is given from Standard Input in the following format:

Output

Print the answer as an integer.

Sample Input 1

Sample Output 1

Some of the 4-digit integers satisfying the conditions are 1111,1234,7878,6545.

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3

248860093

Be sure to find the count modulo 998244353.

G - All Assign Point Add

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

配点 : 400 点

問題文

長さ N の数列 A = (A_1, A_2, \dots, A_N) が与えられます。

Q 個のクエリが与えられるので、順番にすべて処理してください。 q 番目 (1\leq q\leq Q) のクエリは以下の 3 つのいずれかの形式で、それぞれ次のようなクエリを表します。

1\ x _ q ： A のすべての要素に x _ q を代入する。
2\ i _ q\ x _ q ： A _ {i _ q} に x _ q を加える。
3\ i _ q ： A _ {i _ q} の値を出力する。

制約

1 \leq N \leq 2\times10^5
1 \leq Q \leq 2\times10^5
0 \leq A _ i \leq 10^9\ (1\leq i\leq N)
q 番目 (1\leq q\leq Q) のクエリが 2 番目もしくは 3 番目の形式のとき、1 \leq i _ q \leq N
q 番目 (1\leq q\leq Q) のクエリが 1 番目もしくは 2 番目の形式のとき、0 \leq x _ q \leq 10^9
3 番目の形式のクエリが存在する
入力される値はすべて整数

入力

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

N
A_1 A_2 \dots A_N
Q
\operatorname{query}_1
\operatorname{query}_2
\vdots
\operatorname{query}_Q

ただし、\operatorname{query}_q は q 番目のクエリであり、1 x, 2 i x, 3 i の形式のいずれかで与えられる。

出力

\operatorname{query}_q が 3 番目の形式であるような q\ (1\leq q\leq Q) の個数を X として、X 行出力せよ。 j\ (1\leq j\leq X) 行目にはそのようなクエリのうち j 番目のクエリに対する答えを出力せよ。

入力例 1

出力例 1

1
8
5

はじめ、A=(3,1,4,1,5) です。それぞれのクエリでは、以下のような処理が行われます。

A_2=1 なので、1 を出力します。
A_3 に 4 を加えます。A=(3,1,8,1,5) となります。
A_3=8 なので、8 を出力します。
A の要素すべてに 1 を代入します。A=(1,1,1,1,1) となります。
A_3 に 4 を加えます。A=(1,1,5,1,1) となります。
A_3=5 なので、5 を出力します。

入力例 2

1
1000000000
8
2 1 1000000000
2 1 1000000000
2 1 1000000000
2 1 1000000000
2 1 1000000000
2 1 1000000000
2 1 1000000000
3 1

出力例 2

8000000000

A の要素の値が 32\operatorname{bit} 整数に収まらない可能性があることに注意してください。

入力例 3

10
1 8 4 15 7 5 7 5 8 0
20
2 7 0
3 7
3 8
1 7
3 3
2 4 4
2 4 9
2 10 5
1 10
2 4 2
1 10
2 3 1
2 8 11
2 3 14
2 1 9
3 8
3 8
3 1
2 6 5
3 7

出力例 3

Score : 400 points

Problem Statement

You are given a sequence A = (A_1, A_2, \dots, A_N) of length N.

Given Q queries, process all of them in order. The q-th (1\leq q\leq Q) query is in one of the following three formats, which represents the following queries:

1\ x _ q: assign x_q to every element of A.
2\ i _ q\ x _ q: add x_q to A _ {i _ q}.
3\ i _ q: print the value of A _ {i _ q}.

Constraints

1 \leq N \leq 2\times10^5
1 \leq Q \leq 2\times10^5
0 \leq A _ i \leq 10^9\ (1\leq i\leq N)
If the q-th (1\leq q\leq Q) query is in the second or third format, 1 \leq i _ q \leq N.
If the q-th (1\leq q\leq Q) query is in the first or second format, 0 \leq x _ q \leq 10^9.
There exists a query in the third format.
All values in the input are integers.

Input

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

N
A_1 A_2 \dots A_N
Q
\operatorname{query}_1
\operatorname{query}_2
\vdots
\operatorname{query}_Q

Here, \operatorname{query}_q denotes the q-th query, which is in one of following formats: 1 x, 2 i x, and 3 i.

Output

Print X lines, where X is the number of q's (1\leq q\leq Q) such that \operatorname{query}_q is in the third format. The j-th (1\leq j\leq X) line should contain the answer to the j-th such query.

Sample Input 1

Sample Output 1

1
8
5

Initially, A=(3,1,4,1,5). The queries are processed as follows:

A_2=1, so print 1.
Add 4 to A_3, making A=(3,1,8,1,5).
A_3=8, so print 8.
Assign 1 to every element of A, making A=(1,1,1,1,1).
Add 4 to A_3, making A=(1,1,5,1,1).
A_3=5, so print 5.

Sample Input 2

1
1000000000
8
2 1 1000000000
2 1 1000000000
2 1 1000000000
2 1 1000000000
2 1 1000000000
2 1 1000000000
2 1 1000000000
3 1

Sample Output 2

8000000000

Note that the elements of A may not fit into a 32-bit integer type.

Sample Input 3

10
1 8 4 15 7 5 7 5 8 0
20
2 7 0
3 7
3 8
1 7
3 3
2 4 4
2 4 9
2 10 5
1 10
2 4 2
1 10
2 3 1
2 8 11
2 3 14
2 1 9
3 8
3 8
3 1
2 6 5
3 7

Sample Output 3