A - 321-like Checker

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

以下の条件を満たす正整数 x を 321-like Number と呼びます。

  • x の各桁を上から見ると狭義単調減少になっている。
  • すなわち、x が d 桁の整数だとすると、 1 \le i < d を満たす全ての整数 i について以下の条件を満たす。
    • ( x の上から i 桁目 ) > ( x の上から i+1 桁目 )

なお、 1 桁の正整数は必ず 321-like Number であることに注意してください。

例えば、 321,96410,1 は 321-like Number ですが、 123,2109,86411 は 321-like Number ではありません。

N が入力として与えられるので、 N が 321-like Number なら Yes 、そうでないなら No と出力してください。

制約

  • 入力は全て整数
  • 1 \le N \le 99999

入力

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

N

出力

N が 321-like Number なら Yes 、そうでないなら No と出力せよ。


入力例 1

321

出力例 1

Yes

N=321 に対して、以下が成り立ちます。

  • 上から 1 桁目の 3 は上から 2 桁目の 2 より大きい。
  • 上から 2 桁目の 2 は上から 3 桁目の 1 より大きい。

以上より、 321 は 321-like Number です。


入力例 2

123

出力例 2

No

N=123 について、例えば以下が成り立ちます。

  • 上から 1 桁目の 1 は上から 2 桁目の 2 より大きくない。

このことから、 123 は 321-like Number ではありません。


入力例 3

1

出力例 3

Yes

入力例 4

86411

出力例 4

No

Score : 100 points

Problem Statement

A positive integer x is called a 321-like Number when it satisfies the following condition.

  • The digits of x are strictly decreasing from top to bottom.
  • In other words, if x has d digits, it satisfies the following for every integer i such that 1 \le i < d:
    • (the i-th digit from the top of x) > (the (i+1)-th digit from the top of x).

Note that all one-digit positive integers are 321-like Numbers.

For example, 321, 96410, and 1 are 321-like Numbers, but 123, 2109, and 86411 are not.

You are given N as input. Print Yes if N is a 321-like Number, and No otherwise.

Constraints

  • All input values are integers.
  • 1 \le N \le 99999

Input

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

N

Output

Print Yes if N is a 321-like Number, and No otherwise.


Sample Input 1

321

Sample Output 1

Yes

For N=321, the following holds:

  • The first digit from the top, 3, is greater than the second digit from the top, 2.
  • The second digit from the top, 2, is greater than the third digit from the top, 1.

Thus, 321 is a 321-like Number.


Sample Input 2

123

Sample Output 2

No

For N=123, the following holds:

  • The first digit from the top, 1, is not greater than the second digit from the top, 2.

Thus, 123 is not a 321-like Number.


Sample Input 3

1

Sample Output 3

Yes

Sample Input 4

86411

Sample Output 4

No
B - Insert

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

長さ N の整数列 A と整数 K,X が与えられます。
整数列 A の K 要素目の直後に整数 X を 1 つ挿入した整数列 B を出力してください。

制約

  • 入力は全て整数
  • 1 \le K \le N \le 100
  • 1 \le A_i,X \le 100

入力

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

N K X
A_1 A_2 \dots A_N

出力

整数列 A の K 要素目の直後に整数 X を 1 つ挿入した整数列 B を、以下の形式で出力せよ。

B_1 B_2 \dots B_{N+1}

入力例 1

4 3 7
2 3 5 11

出力例 1

2 3 5 7 11

K=3, X=7, A=(2,3,5,11) のとき、 B=(2,3,5,7,11) です。


入力例 2

1 1 100
100

出力例 2

100 100

入力例 3

8 8 3
9 9 8 2 4 4 3 5

出力例 3

9 9 8 2 4 4 3 5 3

Score : 100 points

Problem Statement

You are given an integer sequence A of length N and integers K and X.
Print the integer sequence B obtained by inserting the integer X immediately after the K-th element of the sequence A.

Constraints

  • All input values are integers.
  • 1 \le K \le N \le 100
  • 1 \le A_i, X \le 100

Input

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

N K X
A_1 A_2 \dots A_N

Output

Print the integer sequence B obtained by inserting the integer X immediately after the K-th element of the sequence A, in the following format:

B_1 B_2 \dots B_{N+1}

Sample Input 1

4 3 7
2 3 5 11

Sample Output 1

2 3 5 7 11

For K=3, X=7, and A=(2,3,5,11), we get B=(2,3,5,7,11).


Sample Input 2

1 1 100
100

Sample Output 2

100 100

Sample Input 3

8 8 3
9 9 8 2 4 4 3 5

Sample Output 3

9 9 8 2 4 4 3 5 3
C - Broken Rounding

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

非負整数 X に対し、 i=0,1,\dots,K-1 の順に次の操作を行ったとき、操作を全て終えた時点での X を求めてください。

  • X の 10^i の位以下を四捨五入する。
    • 厳密には、 X を「 |Y-X| が最小となる 10^{i+1} の倍数のうち最大のもの」である Y に置き換える。
    • 具体例を挙げる。
      • 273 の 10^1 の位以下を四捨五入すれば 300 となる。
      • 999 の 10^2 の位以下を四捨五入すれば 1000 となる。
      • 100 の 10^9 の位以下を四捨五入すれば 0 となる。
      • 1015 の 10^0 の位以下を四捨五入すれば 1020 となる。

制約

  • X,K は整数
  • 0 \le X < 10^{15}
  • 1 \le K \le 15

入力

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

X K

出力

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


入力例 1

2048 2

出力例 1

2100

操作の過程で、 X は 2048 \rightarrow 2050 \rightarrow 2100 と変化します。


入力例 2

1 15

出力例 2

0

入力例 3

999 3

出力例 3

1000

入力例 4

314159265358979 12

出力例 4

314000000000000

X は 32bit 整数型に収まらない可能性があります。

Score : 200 points

Problem Statement

Given a non-negative integer X, perform the following operation for i=1,2,\dots,K in this order and find the resulting X.

  • Round X off to the nearest 10^i.
    • Formally, replace X with Y that is "the largest multiple of 10^i that minimizes |Y-X|."
    • Here are some examples:
      • Rounding 273 off to the nearest 10^2 yields 300.
      • Rounding 999 off to the nearest 10^3 yields 1000.
      • Rounding 100 off to the nearest 10^{10} yields 0.
      • Rounding 1015 off to the nearest 10^1 yields 1020.

Constraints

  • X and K are integers.
  • 0 \le X < 10^{15}
  • 1 \le K \le 15

Input

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

X K

Output

Print the answer as an integer.


Sample Input 1

2048 2

Sample Output 1

2100

X changes as 2048 \rightarrow 2050 \rightarrow 2100 by the operations.


Sample Input 2

1 15

Sample Output 2

0

Sample Input 3

999 3

Sample Output 3

1000

Sample Input 4

314159265358979 12

Sample Output 4

314000000000000

X may not fit into a 32-bit integer type.

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 - Max MEX

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

長さ N の非負整数列 A が与えられます。
A から K 要素を選んで順序を保ったまま抜き出した列を B としたとき、 MEX(B) としてありえる最大値を求めてください。

但し、数列 X に対して MEX(X) は以下の条件を満たす唯一の非負整数 m として定義されます。

  • 0 \le i < m を満たす全ての整数 i が X に含まれる。
  • m が X に含まれない。

制約

  • 入力は全て整数
  • 1 \le K \le N \le 3 \times 10^5
  • 0 \le A_i \le 10^9

入力

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

N K
A_1 A_2 \dots A_N

出力

答えを出力せよ。


入力例 1

7 3
2 0 2 3 2 1 9

出力例 1

3

この入力では A=(2,0,2,3,2,1,9) であり、ここから K=3 要素を選んで抜き出して数列 B を得ます。例えば、

  • 1,2,3 要素目を抜き出した時、 MEX(B)=MEX(2,0,2)=1
  • 3,4,6 要素目を抜き出した時、 MEX(B)=MEX(2,3,1)=0
  • 2,6,7 要素目を抜き出した時、 MEX(B)=MEX(0,1,9)=2
  • 2,3,6 要素目を抜き出した時、 MEX(B)=MEX(0,2,1)=3

のようになります。
達成可能な MEX の最大値は 3 です。

Score : 300 points

Problem Statement

You are given a length-N sequence of non-negative integers.
When B is a sequence obtained by choosing K elements from A and concatenating them without changing the order, find the maximum possible value of MEX(B).

Here, for a sequence X, we define MEX(X) as the unique non-negative integer m that satisfies the following conditions:

  • Every integer i such that 0 \le i < m is contained in X.
  • m is not contained in X.

Constraints

  • All values in the input are integers.
  • 1 \le K \le N \le 3 \times 10^5
  • 0 \le A_i \le 10^9

Input

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

N K
A_1 A_2 \dots A_N

Output

Print the answer.


Sample Input 1

7 3
2 0 2 3 2 1 9

Sample Output 1

3

In this input, A=(2,0,2,3,2,1,9), and you obtain the sequence B by picking K=3 elements. For example,

  • If the 1-st, 2-nd, and 3-rd elements are chosen, MEX(B)=MEX(2,0,2)=1.
  • If the 3-rd, 4-th, and 6-th elements are chosen, MEX(B)=MEX(2,3,1)=0.
  • If the 2-nd, 6-th, and 7-th elements are chosen, MEX(B)=MEX(0,1,9)=2.
  • If the 2-nd, 3-rd, and 6-th elements are chosen, MEX(B)=MEX(0,2,1)=3.

The maximum possible MEX is 3.