A - A Recursive Function

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

非負整数 x に対し定義される関数 f(x) は以下の条件を満たします。

  • f(0) = 1
  • 任意の正整数 k に対し f(k) = k \times f(k-1)

このとき、 f(N) を求めてください。

制約

  • N は 0 \le N \le 10 を満たす整数

入力

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

N

出力

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

入力例 1

2

出力例 1

2

f(2) = 2 \times f(1) = 2 \times 1 \times f(0) = 2 \times 1 \times 1 = 2 です。

入力例 2

3

出力例 2

6

f(3) = 3 \times f(2) = 3 \times 2 = 6 です。

入力例 3

0

出力例 3

1

入力例 4

10

出力例 4

3628800

Score : 100 points

Problem Statement

A function f(x) defined for non-negative integer x satisfies the following conditions:

  • f(0) = 1;
  • f(k) = k \times f(k-1) for all positive integers k.

Find f(N).

Constraints

  • N is an integer such that 0 \le N \le 10.

Input

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

N

Output

Print the answer as an integer.

Sample Input 1

2

Sample Output 1

2

We have f(2) = 2 \times f(1) = 2 \times 1 \times f(0) = 2 \times 1 \times 1 = 2.

Sample Input 2

3

Sample Output 2

6

We have f(3) = 3 \times f(2) = 3 \times 2 = 6.

Sample Input 3

0

Sample Output 3

1

Sample Input 4

10

Sample Output 4

3628800
B - First ABC

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

A, B, C からなる文字列 S が与えられます。S は A, B, C を全て含むことが保証されます。

S を左から 1 文字ずつ見ていったときに、はじめて次の条件を満たした状態になるのは、左から何文字目まで見たときですか？

  • A, B, C が全て 1 回以上出現している。

制約

  • 3 \leq N \leq 100
  • S は A, B, C からなる長さ N の文字列
  • S は A, B, C を全て含む

入力

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

N
S

出力

答えを出力せよ。

入力例 1

5
ACABB

出力例 1

4

左から 4 文字目までに A は 2 回, B は 1 回, C は 1 回出現していて、条件を満たします。
3 文字目以前では条件を満たさないので答えは 4 です。

入力例 2

4
CABC

出力例 2

3

左から 3 文字目までに A, B, C は 1 回ずつ出現していて、条件を満たします。

入力例 3

30
AABABBBABABBABABCABACAABCBACCA

出力例 3

17

Score : 100 points

Problem Statement

You are given a string S consisting of A, B, and C. S is guaranteed to contain all of A, B, and C.

If the characters of S are checked one by one from the left, how many characters will have been checked when the following condition is satisfied for the first time?

  • All of A, B, and C have appeared at least once.

Constraints

  • 3 \leq N \leq 100
  • S is a string of length N consisting of A, B, and C.
  • S contains all of A, B, and C.

Input

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

N
S

Output

Print the answer.

Sample Input 1

5
ACABB

Sample Output 1

4

In the first four characters from the left, A, B, and C appear twice, once, and once, respectively, satisfying the condition.
The condition is not satisfied by checking three or fewer characters, so the answer is 4.

Sample Input 2

4
CABC

Sample Output 2

3

In the first three characters from the left, each of A, B, and C appears once, satisfying the condition.

Sample Input 3

30
AABABBBABABBABABCABACAABCBACCA

Sample Output 3

17
C - Get Closer

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

二次元平面上の点 (0,0) から点 (A,B) に向かって距離 1 だけ移動します。移動後の座標を求めてください。

ただし、点 X から点 Y に向かって距離 d (\le 線分 XY の長さ) だけ移動すると、線分 XY 上で点 X からの距離が d であるような点に辿りつくものとします。
なお、制約より点 (0,0) と点 (A,B) の距離は 1 以上であることが保証されます。

制約

  • 入力は全て整数
  • 0 \le A,B \le 1000
  • (A,B) \neq (0,0)

入力

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

A B

出力

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

入力例 1

3 4

出力例 1

0.600000000000 0.800000000000

他にも、例えば 0.5999999999 0.8000000001 という出力も許容されます。

入力例 2

1 0

出力例 2

1.000000000000 0.000000000000

点 (A,B) に到着する場合もあります。

入力例 3

246 402

出力例 3

0.521964870245 0.852966983083

Score : 200 points

Problem Statement

From the point (0,0) in a two-dimensional plane, let us move the distance of 1 toward the point (A, B). Find our coordinates after the move.

Here, after moving the distance of d from a point X to a point Y (d \le length of the segment XY), we are at the point on the segment XY whose distance from X is d.
The Constraints guarantee that the distance between the points (0, 0) and (A, B) is at least 1.

Constraints

  • All values in input are integers.
  • 0 \le A,B \le 1000
  • (A,B) \neq (0,0)

Input

Input is given from Standard Input in the following format:

A B

Output

Let (x, y) be our coordinates after the move. Print x and y in this order, separated by a space.
Your output is considered correct when, for each printed value, the absolute or relative error from the judge's answer is at most 10^{−6}.

Sample Input 1

3 4

Sample Output 1

0.600000000000 0.800000000000

Printing 0.5999999999 0.8000000001, for example, would also be accepted.

Sample Input 2

1 0

Sample Output 2

1.000000000000 0.000000000000

We may arrive at (A, B).

Sample Input 3

246 402

Sample Output 3

0.521964870245 0.852966983083
D - Trimmed Mean

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

高橋君は体操の大会に参加しています。
大会では、5N 人の審査員それぞれが高橋君の演技に対して評点をつけ、それらを元に次のように高橋君の得点が決定されます。

  • 高い評点をつけた方から順に N 人の審査員による評点を無効にする。
  • 低い評点をつけた方から順に N 人の審査員による評点を無効にする。
  • 残りの 3N 人の審査員による評点の平均点を高橋君の得点とする。

より厳密には、審査員がつけた得点の多重集合 S (|S|=5N) に対して次の操作を行って得られたものが高橋君の得点となります。

  • 「S の最大の要素(複数ある場合はそのうちの 1 つ)を選び、S から取り除く」という操作を N 回繰り返す。
  • 「S の最小の要素(複数ある場合はそのうちの 1 つ)を選び、S から取り除く」という操作を N 回繰り返す。
  • S に残った 3N 個の要素の平均を高橋君の得点とする。

高橋君の演技に対する、i 人目 (1\leq i\leq 5N) の審査員の評点は X_i 点でした。 高橋君の得点を計算してください。

制約

  • 1\leq N\leq 100
  • 0\leq X_i\leq 100
  • 入力はすべて整数

入力

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

N
X_1 X_2 \ldots X_{5N}

出力

高橋君の得点を出力せよ。
なお、真の値との絶対誤差または相対誤差が 10^{-5} 以下であれば正解として扱われる。

入力例 1

1
10 100 20 50 30

出力例 1

33.333333333333336

N=1 であるので、評点が高い方と低い方からそれぞれ 1 人ずつの審査員による評点を無効にします。
1 番高い評点をつけた審査員は 2 人目 (100 点) であるため、これを無効にします。
また、1 番低い評点をつけた審査員は 1 人目 (10 点) であるため、これも無効にします。
よって、最終的な平均点は \displaystyle\frac{20+50+30}{3}=33.333\cdots となります。

出力は、真の値との絶対誤差または相対誤差が 10^{-5} 以下であれば正解として扱われる事に注意してください。

入力例 2

2
3 3 3 4 5 6 7 8 99 100

出力例 2

5.500000000000000

N=2 であるので、評点が高い方と低い方からそれぞれ 2 人ずつの審査員による評点を無効にします。
1,2 番目に高い評点をつけた審査員は順に 10 人目 (100 点), 9 人目 (99 点) であるため、これを無効にします。
1 番低い評点をつけた審査員は 1,2,3 人目 (3 点) の 3 人がいるため、このうち 2 人を無効とします。
よって、答えは \displaystyle\frac{3+4+5+6+7+8}{6}=5.5 となります。

1 番低い評点をつけた 3 人のうちどの 2 人を無効にしたかは、答えに影響しない事に注意してください。

Score : 200 points

Problem Statement

Takahashi is participating in a gymnastic competition.
In the competition, each of 5N judges grades Takahashi's performance, and his score is determined as follows:

  • Invalidate the grades given by the N judges who gave the highest grades.
  • Invalidate the grades given by the N judges who gave the lowest grades.
  • Takahashi's score is defined as the average of the remaining 3N judges' grades.

More formally, Takahashi's score is obtained by performing the following procedure on the multiset of the judges' grades S (|S|=5N):

  • Repeat the following operation N times: choose the maximum element (if there are multiple such elements, choose one of them) and remove it from S.
  • Repeat the following operation N times: choose the minimum element (if there are multiple such elements, choose one of them) and remove it from S.
  • Takahashi's score is defined as the average of the 3N elements remaining in S.

The i-th (1\leq i\leq 5N) judge's grade for Takahashi's performance was X_i points. Find Takahashi's score.

Constraints

  • 1\leq N\leq 100
  • 0\leq X_i\leq 100
  • All values in the input are integers.

Input

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

N
X_1 X_2 \ldots X_{5N}

Output

Print Takahashi's score.
Your answer will be considered correct if the absolute or relative error from the true value is at most 10^{-5}.

Sample Input 1

1
10 100 20 50 30

Sample Output 1

33.333333333333336

Since N=1, the grade given by one judge who gave the highest grade, and one with the lowest, are invalidated.
The 2-nd judge gave the highest grade (100 points), which is invalidated.
Additionally, the 1-st judge gave the lowest grade (10 points), which is also invalidated.
Thus, the average is \displaystyle\frac{20+50+30}{3}=33.333\cdots.

Note that the output will be considered correct if the absolute or relative error from the true value is at most 10^{-5}.

Sample Input 2

2
3 3 3 4 5 6 7 8 99 100

Sample Output 2

5.500000000000000

Since N=2, the grades given by the two judges who gave the highest grades, and two with the lowest, are invalidated.
The 10-th and 9-th judges gave the highest grades (100 and 99 points, respectively), which are invalidated.
Three judges, the 1-st, 2-nd, and 3-rd, gave the lowest grade (3 points), so two of them are invalidated.
Thus, the average is \displaystyle\frac{3+4+5+6+7+8}{6}=5.5.

Note that the choice of the two invalidated judges from the three with the lowest grades does not affect the answer.
E - Ameba

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

あなたはアメーバの観察記録をつけました。

最初 1 匹のアメーバがおり、番号は 1 です。

観察記録は時系列順に N 個あり、i 番目の観察記録は「番号 A_i のアメーバが分裂して消滅し、新たに 2 匹のアメーバが生まれ、それらにそれぞれ 2i,2i+1 と番号をつけた」というものです。
このとき、アメーバ A_i を アメーバ 2i,2i+1 の親と呼びます。

各 k=1,\ldots,2N+1 について、アメーバ k から何代親を遡るとアメーバ 1 になるか求めてください。

制約

  • 1 \leq N \leq 2\times 10^5
  • 観察記録は矛盾していない。すなわち
    • 1\leq A_i \leq 2i-1
    • A_i は相異なる整数

入力

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

N
A_1 A_2 \ldots A_N

出力

2N+1 行出力せよ。k 行目にはアメーバ k から何代親を遡るとアメーバ 1 になるかを出力せよ。

入力例 1

2
1 2

出力例 1

0
1
1
2
2

アメーバ 1 からアメーバ 2,3 が生まれ、アメーバ 2 からアメーバ 4,5 が生まれました。

  • アメーバ 1 は 0 代遡るとアメーバ 1 になります。
  • アメーバ 2 は 1 代遡るとアメーバ 1 になります。
  • アメーバ 3 は 1 代遡るとアメーバ 1 になります。
  • アメーバ 4 は 1 代遡るとアメーバ 2 になり、2 代遡るとアメーバ 1 になります。
  • アメーバ 5 は 1 代遡るとアメーバ 2 になり、2 代遡るとアメーバ 1 になります。

入力例 2

4
1 3 5 2

出力例 2

0
1
1
2
2
3
3
2
2

Score : 300 points

Problem Statement

You observed amoebae and kept some records.

Initially, there was one amoeba, numbered 1.

You made N records. According to the i-th record, the amoeba numbered A_i disappeared by dividing itself into two new amoebae, which were then numbered 2i and 2i+1.
Here, amoeba A_i is said to be the parent of amoebae 2i and 2i+1.

For each k=1,\ldots,2N+1, how many generations away is amoeba k from amoeba 1?

Constraints

  • 1 \leq N \leq 2\times 10^5
  • The records are consistent. That is:
    • 1\leq A_i \leq 2i-1.
    • A_i are distinct integers.

Input

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

N
A_1 A_2 \ldots A_N

Output

Print 2N+1 lines. The k-th line should contain the generation distance between amoeba 1 and amoeba k.

Sample Input 1

2
1 2

Sample Output 1

0
1
1
2
2

From amoeba 1, amoebae 2 and 3 were born. From amoeba 2, amoebae 4 and 5 were born.

  • Amoeba 1 is zero generations away from amoeba 1.
  • Amoeba 2 is one generation away from amoeba 1.
  • Amoeba 3 is one generation away from amoeba 1.
  • Amoeba 4 is one generation away from amoeba 2, and two generations away from amoeba 1.
  • Amoeba 5 is one generation away from amoeba 2, and two generations away from amoeba 1.

Sample Input 2

4
1 3 5 2

Sample Output 2

0
1
1
2
2
3
3
2
2