AtCoder Daily Training MEDIUM 2024/05/30 20:30start

C - Slimes

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

配点 : 200 点

問題文

A 匹のスライムがいます。

すぬけくんが 1 回叫ぶたびに、スライムは K 倍に増殖します。

スライムが B 匹以上になるには、すぬけくんは最小で何回叫ぶ必要があるでしょうか？

制約

1 \leq A \leq B \leq 10^9
2 \leq K \leq 10^9
入力は全て整数

入力

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

A B K

出力

答えを出力せよ。

入力例 1

1 4 2

出力例 1

はじめ、スライムが 1 匹います。すぬけくんが 1 回叫ぶとスライムは 2 匹になり、 2 回叫ぶとスライムは 4 匹になります。4 匹以上になるためには、最小で 2 回叫ぶ必要があります。

入力例 2

7 7 10

出力例 2

はじめからスライムは 7 匹います。

入力例 3

31 415926 5

出力例 3

Score : 200 points

Problem Statement

There are A slimes.

Each time Snuke shouts, the slimes multiply by K times.

In order to have B or more slimes, at least how many times does Snuke need to shout?

Constraints

1 \leq A \leq B \leq 10^9
2 \leq K \leq 10^9
All values in input are integers.

Input

Input is given from Standard Input in the following format:

A B K

Output

Print the answer.

Sample Input 1

1 4 2

Sample Output 1

We start with one slime. After Snuke's first shout, we have two slimes; after his second shout, we have four slimes. Thus, he needs to shout at least twice to have four or more slimes.

Sample Input 2

7 7 10

Sample Output 2

We have seven slimes already at the start.

Sample Input 3

31 415926 5

Sample Output 3

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

E - Matrix Reducing

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

配点 : 300 点

問題文

H_1 行 W_1 列の行列 A と、H_2 行 W_2 列の行列 B が与えられます。

1 \leq i \leq H_1 かつ 1 \leq j \leq W_1 を満たす整数の組 (i, j) について、行列 A の i 行目 j 列目の要素は A_{i, j} です。
1 \leq i \leq H_2 かつ 1 \leq j \leq W_2 を満たす整数の組 (i, j) について、行列 B の i 行目 j 列目の要素は B_{i, j} です。

行列 A に対して、下記の 2 つの操作のうちどちらかを行うことを、好きなだけ（ 0 回でも良い）繰り返すことができます。

A の行を任意に 1 つ選んで削除する。
A の列を任意に 1 つ選んで削除する。

行列 A を行列 B に一致させることができるかどうかを判定して下さい。

制約

1 \leq H_2 \leq H_1 \leq 10
1 \leq W_2 \leq W_1 \leq 10
1 \leq A_{i, j} \leq 10^9
1 \leq B_{i, j} \leq 10^9
入力中の値はすべて整数

入力

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

H_1 W_1
A_{1, 1} A_{1, 2} \ldots A_{1, W_1}
A_{2, 1} A_{2, 2} \ldots A_{2, W_1}
\vdots
A_{H_1, 1} A_{H_1, 2} \ldots A_{H_1, W_1}
H_2 W_2
B_{1, 1} B_{1, 2} \ldots B_{1, W_2}
B_{2, 1} B_{2, 2} \ldots B_{2, W_2}
\vdots
B_{H_2, 1} B_{H_2, 2} \ldots B_{H_2, W_2}

出力

行列 A を行列 B に一致させることができる場合は Yes を、一致させることができない場合は No を出力せよ。ジャッジは英小文字と英大文字を厳密に区別することに注意せよ。

入力例 1

4 5
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
2 3
6 8 9
16 18 19

出力例 1

Yes

初期状態の行列 A から 2 列目を削除すると、行列 A は

1 3 4 5
6 8 9 10
11 13 14 15
16 18 19 20

となります。そこからさらに 3 行目を削除すると、行列 A は

1 3 4 5
6 8 9 10
16 18 19 20

となります。そこからさらに 1 行目を削除すると、行列 A は

6 8 9 10
16 18 19 20

となります。そこからさらに 4 列目を削除すると、行列 A は

6 8 9
16 18 19

となります。これは行列 B と一致します。操作の繰り返しによって行列 A を行列 B に一致させることができるので Yes を出力します。

入力例 2

出力例 2

No

どのように操作を行っても、行列 A を行列 B に一致させることはできません。よって、No を出力します。

Score : 300 points

Problem Statement

You are given a matrix A with H_1 rows and W_1 columns, and a matrix B with H_2 rows and W_2 columns.

For all integer pairs (i, j) such that 1 \leq i \leq H_1 and 1 \leq j \leq W_1, the element at the i-th row and j-th column of matrix A is A_{i, j}.
For all integer pairs (i, j) such that 1 \leq i \leq H_2 and 1 \leq j \leq W_2, the element at the i-th row and j-th column of matrix B is B_{i, j}.

You may perform the following operations on the matrix A any number of (possibly 0) times in any order:

Choose an arbitrary row of A and remove it.
Choose an arbitrary column of A and remove it.

Determine if it is possible to make the matrix A equal the matrix B.

Constraints

1 \leq H_2 \leq H_1 \leq 10
1 \leq W_2 \leq W_1 \leq 10
1 \leq A_{i, j} \leq 10^9
1 \leq B_{i, j} \leq 10^9
All values in input are integers.

Input

Input is given from Standard Input in the following format:

H_1 W_1
A_{1, 1} A_{1, 2} \ldots A_{1, W_1}
A_{2, 1} A_{2, 2} \ldots A_{2, W_1}
\vdots
A_{H_1, 1} A_{H_1, 2} \ldots A_{H_1, W_1}
H_2 W_2
B_{1, 1} B_{1, 2} \ldots B_{1, W_2}
B_{2, 1} B_{2, 2} \ldots B_{2, W_2}
\vdots
B_{H_2, 1} B_{H_2, 2} \ldots B_{H_2, W_2}

Output

Print Yes if it is possible to make the matrix A equal the matrix B; print No otherwise. Note that the judge is case-sensitive.

Sample Input 1

4 5
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
2 3
6 8 9
16 18 19

Sample Output 1

Yes

Removing the 2-nd column from the initial A results in:

1 3 4 5
6 8 9 10
11 13 14 15
16 18 19 20

Then, removing the 3-rd row from A results in:

1 3 4 5
6 8 9 10
16 18 19 20

Then, removing the 1-st row from A results in:

6 8 9 10
16 18 19 20

Then, removing the 4-th column from A results in:

6 8 9
16 18 19

Now the matrix equals the matrix B.
Thus, we can make the matrix A equal the matrix B by repeating the operations, so Yes should be printed.

Sample Input 2

Sample Output 2

No

Regardless of how we perform the operations, we cannot make the matrix A equal the matrix B, so No should be printed.

F - Triangle?

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

配点 : 300 点

問題文

xy 平面上に 1 から N までの番号が付いた N 個の点があります。
点 i は座標 (X_i,Y_i) にあり、相異なる 2 点は異なる位置に存在します。
この N 点から 3 点を選ぶとき、選ばれた 3 点を線分で結んだ図形が正の面積を持つ三角形になるような点の選び方の総数を求めてください。

制約

入力は全て整数である
3 \le N \le 300
-10^9 \le X_i,Y_i \le 10^9
i \neq j ならば (X_i,Y_i) \neq (X_j,Y_j)

入力

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

N
X_1 Y_1
X_2 Y_2
\dots
X_N Y_N

出力

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

入力例 1

出力例 1

点を図示すると、以下のようになります。

三角形をなすような点の選び方は、 \{1,2,3\},\{1,3,4\},\{2,3,4\} の 3 つです。

入力例 2

20
224 433
987654321 987654321
2 0
6 4
314159265 358979323
0 0
-123456789 123456789
-1000000000 1000000000
124 233
9 -6
-4 0
9 5
-7 3
333333333 -333333333
-9 -1
7 -10
-1 5
324 633
1000000000 -1000000000
20 0

出力例 2

Score : 300 points

Problem Statement

In the xy-plane, we have N points numbered 1 through N.
Point i is at the coordinates (X_i,Y_i). Any two different points are at different positions.
Find the number of ways to choose three of these N points so that connecting the chosen points with segments results in a triangle with a positive area.

Constraints

All values in input are integers.
3 \le N \le 300
-10^9 \le X_i,Y_i \le 10^9
(X_i,Y_i) \neq (X_j,Y_j) if i \neq j.

Input

Input is given from Standard Input in the following format:

N
X_1 Y_1
X_2 Y_2
\dots
X_N Y_N

Output

Print the answer as an integer.

Sample Input 1

Sample Output 1

The figure below illustrates the points.

There are three ways to choose points that form a triangle: \{1,2,3\},\{1,3,4\},\{2,3,4\}.

Sample Input 2

20
224 433
987654321 987654321
2 0
6 4
314159265 358979323
0 0
-123456789 123456789
-1000000000 1000000000
124 233
9 -6
-4 0
9 5
-7 3
333333333 -333333333
-9 -1
7 -10
-1 5
324 633
1000000000 -1000000000
20 0

Sample Output 2

G - Rectangles

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

配点 : 400 点

問題文

2 次元平面上に N 個の相異なる点があり、1,2,\ldots ,N の番号がついています。点 i\,(1 \leq i \leq N) の座標は (x_i,y_i) です。

これらの点のうち 4 つを頂点とし、全ての辺が x 軸または y 軸に平行であるような長方形はいくつありますか？

制約

4 \leq N \leq 2000
0 \leq x_i, y_i \leq 10^9
(x_i,y_i) \neq (x_j,y_j) (i \neq j)
入力は全て整数である。

入力

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

N
x_1 y_1
x_2 y_2
 \vdots 
x_N y_N

出力

答えを出力せよ。

入力例 1

出力例 1

点 1 、点 2 、点 3 、点 4 を頂点とする長方形、

点 1 、点 2 、点 5 、点 6 を頂点とする長方形、

点 3 、点 4 、点 5 、点 6 を頂点とする長方形

の合計 3 つです。

入力例 2

出力例 2

入力例 3

出力例 3

Score : 400 points

Problem Statement

We have N distinct points on a two-dimensional plane, numbered 1,2,\ldots,N. Point i (1 \leq i \leq N) has the coordinates (x_i,y_i).

How many rectangles are there whose vertices are among the given points and whose edges are parallel to the x- or y-axis?

Constraints

4 \leq N \leq 2000
0 \leq x_i, y_i \leq 10^9
(x_i,y_i) \neq (x_j,y_j) (i \neq j)
All values in input are integers.

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

Output

Print the answer.

Sample Input 1

Sample Output 1

There are three such rectangles:

the rectangle whose vertices are Points 1, 2, 3, 4,

the rectangle whose vertices are Points 1, 2, 5, 6,

and the rectangle whose vertices are Points 3, 4, 5, 6.

Sample Input 2

Sample Output 2

Sample Input 3