A - AtCoder Quiz 2

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

配点 : 100 点

問題文

AtCoder 王国では、競技プログラミングの実力を測る検定試験が実施されています。

試験は 100 点満点であり、点数が高ければ高いほど、高いランクが認定されます。
ランクは以下のように定められています。

  • 0 点以上 40 点未満のとき、初級
  • 40 点以上 70 点未満のとき、中級
  • 70 点以上 90 点未満のとき、上級
  • 90 点以上のとき、エキスパート

高橋君は、この検定試験を受験し、X 点を取りました。

高橋君が認定されたランクより一つ高いランクとなるためには最低であと何点必要か求めてください。ただし、高橋君がエキスパートと認定された場合、それより高いランクは存在しないため expert と出力してください。

制約

  • 0 \leq X \leq 100
  • X は整数

入力

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

X

出力

答えを出力せよ。


入力例 1

56

出力例 1

14

高橋君は 56 点を取り、中級と認定されました。一つ高いランクである上級となるためには、最低であと 14 点必要です。


入力例 2

32

出力例 2

8

入力例 3

0

出力例 3

40

入力例 4

100

出力例 4

expert

高橋君は満点を取り、エキスパートと認定されました。これより高いランクは存在しないため、expert と出力します。

Score : 100 points

Problem Statement

In the Kingdom of AtCoder, there is a standardized test of competitive programming proficiency.

An examinee will get a score out of 100 and obtain a rank according to the score, as follows:

  • Novice, for a score not less than 0 but less than 40;
  • Intermediate, for a score not less than 40 but less than 70;
  • Advanced, for a score not less than 70 but less than 90;
  • Expert, for a score not less than 90.

Takahashi took this test and got X points.

Find the minimum number of extra points needed to go up one rank higher. If, however, his rank was Expert, print expert, as there is no higher rank than that.

Constraints

  • 0 \leq X \leq 100
  • X is an integer.

Input

Input is given from Standard Input in the following format:

X

Output

Print the answer.


Sample Input 1

56

Sample Output 1

14

He got 56 points and was certified as Intermediate. In order to reach the next rank of Advanced, he needs at least 14 more points.


Sample Input 2

32

Sample Output 2

8

Sample Input 3

0

Sample Output 3

40

Sample Input 4

100

Sample Output 4

expert

He got full points and was certified as Expert. There is no rank higher than that, so print expert.

B - Past ABCs

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

配点 : 100 点

問題文

長さ 6 の文字列 S が与えられます。S の先頭 3 文字は ABC であり、末尾 3 文字は数字であることが保証されます。

Sが、このコンテスト開始以前に AtCoder上で開催され終了したコンテストの略称であるかどうか判定してください。

ただし、文字列 T が「このコンテスト開始以前に AtCoder上で開催され終了したコンテストの略称」であるとは、以下の 348 個の文字列のうちいずれかに等しいことと定めます。

ABC001, ABC002, \ldots, ABC314, ABC315, ABC317, ABC318, \ldots, ABC348, ABC349

特に ABC316 が含まれないことに注意してください。

制約

  • S は先頭 3 文字が ABC、末尾 3 文字が数字である長さ 6 の文字列

入力

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

S

出力

Sが、このコンテスト開始以前に AtCoder上で開催され終了したコンテストの略称であるなら Yes、そうでないなら No と出力せよ。


入力例 1

ABC349

出力例 1

Yes

ABC349 は先週AtCoder上で開催され終了したコンテストの略称です。


入力例 2

ABC350

出力例 2

No

ABC350 はこのコンテストです。まだ終了していません。


入力例 3

ABC316

出力例 3

No

ABC316 はAtCoder上で開催されていません。

Score: 100 points

Problem Statement

You are given a string S of length 6. It is guaranteed that the first three characters of S are ABC and the last three characters are digits.

Determine if S is the abbreviation of a contest held and concluded on AtCoder before the start of this contest.

Here, a string T is "the abbreviation of a contest held and concluded on AtCoder before the start of this contest" if and only if it equals one of the following 348 strings:

ABC001, ABC002, \ldots, ABC314, ABC315, ABC317, ABC318, \ldots, ABC348, ABC349.

Note that ABC316 is not included.

Constraints

  • S is a string of length 6 where the first three characters are ABC and the last three characters are digits.

Input

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

S

Output

If S is the abbreviation of a contest held and concluded on AtCoder before the start of this contest, print Yes; otherwise, print No.


Sample Input 1

ABC349

Sample Output 1

Yes

ABC349 is the abbreviation of a contest held and concluded on AtCoder last week.


Sample Input 2

ABC350

Sample Output 2

No

ABC350 is this contest, which has not concluded yet.


Sample Input 3

ABC316

Sample Output 3

No

ABC316 was not held on AtCoder.

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 - Daily Cookie 2

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

配点 : 200 点

問題文

A 問題と似た設定の問題です。A 問題とは、高橋君が食べるクッキーの選び方および求めるものが異なります。

N 個の箱が横一列に並んでおり、そのうちのいくつかの箱にはクッキーが入っています。

各箱の状態は長さ N の文字列 S によって表されます。 具体的には、左から i\ (1\leq i\leq N) 番目の箱は、S の i 文字目が @ のときクッキーが 1 枚入っており、. のとき空き箱です。

高橋君は今からの D 日間、一日一回ずつ、その時点でクッキーが入っている箱のうち最も右にある箱のクッキーを選んで食べます。

N 個の箱それぞれについて、D 日間が経過した後にその箱にクッキーが入っているかを求めてください。

なお、S には @ が D 個以上含まれることが保証されます。

制約

  • 1\leq D \leq N \leq 100
  • N,D は整数
  • S は @ と . からなる長さ N の文字列
  • S には @ が D 個以上含まれる

入力

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

N D
S

出力

長さ N の文字列を出力せよ。 出力する文字列の i\ (1\leq i\leq N) 文字目は、D 日間が経過した後に左から i 番目の箱にクッキーが入っているならば @、入っていないならば . とせよ。


入力例 1

5 2
.@@.@

出力例 1

.@...

高橋君は以下のように行動します。

  • 1 日目:左から 2,3,5 番目の箱にクッキーが入っている。このうちで最も右にある、左から 5 番目の箱に入っているクッキーを選んで食べる。
  • 2 日目:左から 2,3 番目の箱にクッキーが入っている。このうちで最も右にある、左から 3 番目の箱に入っているクッキーを選んで食べる。
  • 2 日間が経過した後、左から 2 番目の箱にのみクッキーが入っている。

よって、正しい出力は .@... です。


入力例 2

3 3
@@@

出力例 2

...

入力例 3

10 4
@@@.@@.@@.

出力例 3

@@@.......

Score: 200 points

Problem Statement

This problem shares a similar setting with Problem A. The way Takahashi chooses cookies and what you are required to find are different from Problem A.

There are N boxes arranged in a row, and some of these boxes contain cookies.

The state of these boxes is represented by a string S of length N. Specifically, the i-th box (1\leq i \leq N) from the left contains one cookie if the i-th character of S is @, and is empty if it is ..

Over the next D days, Takahashi will choose and eat one cookie per day from among the cookies in these boxes. On each day, he chooses the cookie in the rightmost box that contains a cookie at that point.

Determine, for each of the N boxes, whether it will contain a cookie after D days have passed.

It is guaranteed that S contains at least D occurrences of @.

Constraints

  • 1 \leq D \leq N \leq 100
  • N and D are integers.
  • S is a string of length N consisting of @ and ..
  • S contains at least D occurrences of @.

Input

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

N D
S

Output

Print a string of length N. The i-th character (1 \leq i \leq N) of the string should be @ if the i-th box from the left contains a cookie after D days have passed, and . otherwise.


Sample Input 1

5 2
.@@.@

Sample Output 1

.@...

Takahashi acts as follows:

  • Day 1: There are cookies in the 2nd, 3rd, and 5th boxes from the left. Among these, the rightmost is the 5th box. He eats the cookie in this box.
  • Day 2: There are cookies in the 2nd and 3rd boxes. Among these, the rightmost is the 3rd box. He eats the cookie in this box.
  • After two days have passed, only the 2nd box from the left contains a cookie.

Therefore, the correct output is .@....


Sample Input 2

3 3
@@@

Sample Output 2

...

Sample Input 3

10 4
@@@.@@.@@.

Sample Output 3

@@@.......
E - Knight Fork

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

配点 : 300 点

問題文

xy 座標平面上の 2 つの格子点 (x_1, y_1), (x_2, y_2) からの距離がともに \sqrt{5} である格子点は存在しますか?

注記

xy 座標平面上にある点のうち、x 座標と y 座標がともに整数である点を格子点と呼びます。
また、xy 平面上の 2 点 (a, b), (c, d) の距離をユークリッド距離 \sqrt{(a - c)^2 + (b-d)^2} として定義します。

参考として、xy 平面の (0, 0) の上に黒丸を、(0, 0) からの距離が \sqrt{5} となる格子点の上に白丸を書いた図は以下のようになります。(x,y いずれかが整数となる部分に目盛り線を引いています。)

image

制約

  • -10^9 \leq x_1 \leq 10^9
  • -10^9 \leq y_1 \leq 10^9
  • -10^9 \leq x_2 \leq 10^9
  • -10^9 \leq y_2 \leq 10^9
  • (x_1, y_1) \neq (x_2, y_2)
  • 入力はすべて整数である。

入力

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

x_1 y_1 x_2 y_2

出力

条件を満たす格子点が存在する場合は Yes を、存在しない場合は No を出力せよ。


入力例 1

0 0 3 3

出力例 1

Yes
  • 点 (2,1) と (x_1, y_1) の距離は \sqrt{(0-2)^2 + (0-1)^2} = \sqrt{5}
  • 点 (2,1) と (x_2, y_2) の距離は \sqrt{(3-2)^2 + (3-1)^2} = \sqrt{5}
  • 点 (2, 1) は格子点

なので点 (2, 1) は条件を満たします。よって Yes を出力します。
なお、点 (1, 2) も条件を満たすことが同様にして確認できます。


入力例 2

0 1 2 3

出力例 2

No

条件を満たす格子点は存在しません。よって No を出力します。


入力例 3

1000000000 1000000000 999999999 999999999

出力例 3

Yes

点 (10^9 + 1, 10^9 - 2) および点 (10^9 - 2, 10^9 + 1)が条件を満たします。

Score : 300 points

Problem Statement

On an xy-coordinate plane, is there a lattice point whose distances from two lattice points (x_1, y_1) and (x_2, y_2) are both \sqrt{5}?

Notes

A point on an xy-coordinate plane whose x and y coordinates are both integers is called a lattice point.
The distance between two points (a, b) and (c, d) is defined to be the Euclidean distance between them, \sqrt{(a - c)^2 + (b-d)^2}.

The following figure illustrates an xy-plane with a black circle at (0, 0) and white circles at the lattice points whose distances from (0, 0) are \sqrt{5}. (The grid shows where either x or y is an integer.)

image

Constraints

  • -10^9 \leq x_1 \leq 10^9
  • -10^9 \leq y_1 \leq 10^9
  • -10^9 \leq x_2 \leq 10^9
  • -10^9 \leq y_2 \leq 10^9
  • (x_1, y_1) \neq (x_2, y_2)
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

x_1 y_1 x_2 y_2

Output

If there is a lattice point satisfying the condition, print Yes; otherwise, print No.


Sample Input 1

0 0 3 3

Sample Output 1

Yes
  • The distance between points (2,1) and (x_1, y_1) is \sqrt{(0-2)^2 + (0-1)^2} = \sqrt{5};
  • the distance between points (2,1) and (x_2, y_2) is \sqrt{(3-2)^2 + (3-1)^2} = \sqrt{5};
  • point (2, 1) is a lattice point,

so point (2, 1) satisfies the condition. Thus, Yes should be printed.
One can also assert in the same way that (1, 2) also satisfies the condition.


Sample Input 2

0 1 2 3

Sample Output 2

No

No lattice point satisfies the condition, so No should be printed.


Sample Input 3

1000000000 1000000000 999999999 999999999

Sample Output 3

Yes

Point (10^9 + 1, 10^9 - 2) and point (10^9 - 2, 10^9 + 1) satisfy the condition.