AtCoder Daily Training MEDIUM 2024/07/09 19:30start

C - Counterclockwise Rotation

Time Limit: 2 sec / Memory Limit: 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 - Perfect String

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

英大文字と英小文字からなる文字列のうち、以下の条件を全て満たすものを素晴らしい文字列ということとします。

英大文字が文字列の中に現れる。
英小文字が文字列の中に現れる。
全ての文字が相異なる。

例えば、AtCoder や Aa は素晴らしい文字列ですが、atcoder や Perfect は素晴らしい文字列ではありません。

文字列 S が与えられるので、S が素晴らしい文字列か判定してください。

制約

1 \le |S| \le 100
S は英大文字と英小文字からなる文字列である。

入力

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

出力

S が素晴らしい文字列ならば Yes を、そうでないならば No を出力せよ。

入力例 1

AtCoder

出力例 1

Yes

AtCoder は、英大文字が含まれ、英小文字も含まれ、かつ全ての文字が相異なるため素晴らしい文字列です。

入力例 2

Aa

出力例 2

Yes

A と a は違う文字であることに注意してください。この文字列は素晴らしい文字列です。

入力例 3

atcoder

出力例 3

No

英大文字が含まれていないため、素晴らしい文字列ではありません。

入力例 4

Perfect

出力例 4

No

2 文字目と 5 文字目が等しいため、素晴らしい文字列ではありません。

Score : 200 points

Problem Statement

Let us call a string consisting of uppercase and lowercase English alphabets a wonderful string if all of the following conditions are satisfied:

The string contains an uppercase English alphabet.
The string contains a lowercase English alphabet.
All characters in the string are pairwise distinct.

For example, AtCoder and Aa are wonderful strings, while atcoder and Perfect are not.

Given a string S, determine if S is a wonderful string.

Constraints

1 \le |S| \le 100
S is a string consisting of uppercase and lowercase English alphabets.

Input

Input is given from Standard Input in the following format:

Output

If S is a wonderful string, print Yes; otherwise, print No.

Sample Input 1

AtCoder

Sample Output 1

Yes

AtCoder is a wonderful string because it contains an uppercase English alphabet, a lowercase English alphabet, and all characters in the string are pairwise distinct.

Sample Input 2

Aa

Sample Output 2

Yes

Note that A and a are different characters. This string is a wonderful string.

Sample Input 3

atcoder

Sample Output 3

No

It is not a wonderful string because it does not contain an uppercase English alphabet.

Sample Input 4

Perfect

Sample Output 4

No

It is not a wonderful string because the 2-nd and the 5-th characters are the same.

E - ABC conjecture

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

正の整数 N が与えられます。

A\leq B\leq C かつ ABC\leq N であるような正の整数の組 (A,B,C) の個数を求めてください。

なお、制約の条件下で答えは 2^{63} 未満であることが保証されます。

制約

1 \leq N \leq 10^{11}
N は整数である

入力

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

出力

答えを出力せよ。

入力例 1

出力例 1

条件を満たす組は (1,1,1),(1,1,2),(1,1,3),(1,1,4),(1,2,2) の 5 つです。

入力例 2

出力例 2

入力例 3

100000000000

出力例 3

5745290566750

Score : 300 points

Problem Statement

You are given a positive integer N.

Find the number of triples of positive integers (A, B, C) such that A\leq B\leq C and ABC\leq N.

The Constraints guarantee that the answer is less than 2^{63}.

Constraints

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

Input

Input is given from Standard Input in the following format:

Output

Print the answer.

Sample Input 1

Sample Output 1

There are five such triples: (1,1,1),(1,1,2),(1,1,3),(1,1,4),(1,2,2).

Sample Input 2

Sample Output 2

Sample Input 3

100000000000

Sample Output 3

5745290566750

F - Sort

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

(1,2,\ldots,N) の並び替えである数列 A=(A_1,\ldots,A_N) が与えられます。
次の操作を 0 回以上 N-1 回以下行うことで、A を (1,2,\ldots,N) にしてください。

操作：1\leq i < j \leq N を満たす整数の組 (i,j) を自由に選ぶ。A の i 番目と j 番目の要素を入れ替える。

なお、制約の条件下で必ず A を (1,2,\ldots,N) にできることが証明できます。

制約

2 \leq N \leq 2\times 10^5
(A_1,\ldots,A_N) は (1,2,\ldots,N) の並び替えである
入力は全て整数である

入力

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

N
A_1 \ldots A_N

出力

操作回数を K として、K+1 行出力せよ。
1 行目には K を出力せよ。
l+1 行目 (1\leq l \leq K) には l 回目の操作で選ぶ整数 i,j を空白区切りで出力せよ。
問題文中の条件を満たすどのような出力も正解とみなされる。

入力例 1

5
3 4 1 2 5

出力例 1

2
1 3
2 4

操作により数列は次のように変化します。

最初 A=(3,4,1,2,5) である。
1 回目の操作で 1 番目の要素と 3 番目の要素を入れ替える。A=(1,4,3,2,5) になる。
2 回目の操作で 2 番目の要素と 4 番目の要素を入れ替える。A=(1,2,3,4,5) になる。

この他、次のような出力でも正解とみなされます。

入力例 2

4
1 2 3 4

出力例 2

入力例 3

3
3 1 2

出力例 3

2
1 2
2 3

Score: 300 points

Problem Statement

You are given a permutation A=(A_1,\ldots,A_N) of (1,2,\ldots,N).
Transform A into (1,2,\ldots,N) by performing the following operation between 0 and N-1 times, inclusive:

Operation: Choose any pair of integers (i,j) such that 1\leq i < j \leq N. Swap the elements at the i-th and j-th positions of A.

It can be proved that under the given constraints, it is always possible to transform A into (1,2,\ldots,N).

Constraints

2 \leq N \leq 2\times 10^5
(A_1,\ldots,A_N) is a permutation of (1,2,\ldots,N).
All input values are integers.

Input

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

N
A_1 \ldots A_N

Output

Let K be the number of operations. Print K+1 lines.
The first line should contain K.
The (l+1)-th line (1\leq l \leq K) should contain the integers i and j chosen for the l-th operation, separated by a space.
Any output that satisfies the conditions in the problem statement will be considered correct.

Sample Input 1

5
3 4 1 2 5

Sample Output 1

2
1 3
2 4

The operations change the sequence as follows:

Initially, A=(3,4,1,2,5).
The first operation swaps the first and third elements, making A=(1,4,3,2,5).
The second operation swaps the second and fourth elements, making A=(1,2,3,4,5).

Other outputs such as the following are also considered correct:

Sample Input 2

4
1 2 3 4

Sample Output 2

Sample Input 3

3
3 1 2

Sample Output 3

2
1 2
2 3

G - Cutting Woods

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

長さ L メートルの直線状の木材があります。
x = 1, 2, \dots, L - 1 に対して、木材の左端から x メートルの地点には目印として線 x が引かれています。

Q 個のクエリが与えられます。 i 番目のクエリは数の組 (c_i, x_i) によって表されます。
以下の説明に従ってクエリを i の昇順に処理してください。

c_i = 1 のとき : 線 x_i がある地点で木材を 2 つに切る。
c_i = 2 のとき : 線 x_i を含む木材を選び、その長さを出力する。

ただし c_i = 1, 2 の両方に対して、線 x_i はクエリを処理する時点で切られていないことが保証されます。

制約

1 \leq L \leq 10^9
1 \leq Q \leq 2 \times 10^5
c_i = 1, 2 (1 \leq i \leq Q)
1 \leq x_i \leq L - 1 (1 \leq i \leq Q)
全ての i (1 \leq i \leq Q) に対して次が成り立つ: 1 \leq j \lt i かつ (c_j,x_j) = (1, x_i) を満たす j は存在しない。
入力は全て整数である。

入力

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

L Q
c_1 x_1
c_2 x_2
\vdots
c_Q x_Q

出力

c_i = 2 を満たすクエリの回数と等しい行数だけ出力せよ。 j 行目では j 番目のそのようなクエリに対する答えを出力せよ。

入力例 1

出力例 1

5
3

1 番目のクエリ時点では木材は一度も切られていないので、線 2 を含む木材の長さは 5 メートルです。よって 5 を出力します。
2 番目のクエリによって、木材は 3 メートルの木材と 2 メートルの木材に分割されます。
3 番目のクエリ時点では線 2 を含む木材の長さは 3 メートルなので、3 を出力します。

入力例 2

出力例 2

入力例 3

出力例 3

Score : 400 points

Problem Statement

We have a long piece of timber with a length of L meters.
For each x = 1, 2, \dots, L - 1, there is a mark called Mark x at x meters from the left end of the piece.

You are given Q queries, the i-th of which is represented as a pair of numbers (c_i, x_i).
Process the queries in ascending order of i as described below.

If c_i = 1: cut the piece at Mark x_i into two.
If c_i = 2: choose the piece with Mark x_i on it and print its length.

Here, for both kinds of queries c_i = 1, 2, it is guaranteed that there will have been no cut at Mark x_i when the query is to be processed.

Constraints

1 \leq L \leq 10^9
1 \leq Q \leq 2 \times 10^5
c_i = 1, 2 (1 \leq i \leq Q)
1 \leq x_i \leq L - 1 (1 \leq i \leq Q)
For every i (1 \leq i \leq Q), the following holds: there is no j such that 1 \leq j \lt i and (c_j,x_j) = (1, x_i).
All values in input are integers.

Input

Input is given from Standard Input in the following format:

L Q
c_1 x_1
c_2 x_2
\vdots
c_Q x_Q

Output

Print the number of lines equal to the number of queries c_i = 2. In the j-th line, print the response to the j-th such query.

Sample Input 1

Sample Output 1

5
3

At the time of the first query, no cut has been made, so the piece with Mark 2 has a length of 5 meters. Thus, you should print 5.
In the second query, the piece is cut into two pieces with lengths of 3 and 2 meters.
At the time of the third query, the piece with Mark 2 has a length of 3 meters, so you should print 3.

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3