/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 500 点
問題文
N 枚のカードがあり、i \, (1 \leq i \leq N) 番目のカードには整数 A_i が書かれています。
高橋君は、これらのカードから好きな枚数選びます。ただし、各 i \, (1 \leq i \leq N - 1) について、i 番目のカードと i + 1 番目のカードの少なくとも一方を選ぶ必要があります。
以下の値を求めてください。
- 選んだカードに書かれた整数の平均値としてあり得る最大値
- 選んだカードに書かれた整数の中央値としてあり得る最大値
ただし、n 個の整数の中央値は、それらのうち小さい方から数えて \lceil \frac{n}{2} \rceil 番目であるものとします。ここで、\lceil x \rceil は x 以上の最小の整数を表します。
制約
- 2 \leq N \leq 10^5
- 1 \leq A_i \leq 10^{9}
- 入力は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
N A_1 \ldots A_N
出力
2 行出力せよ。1 行目には選んだカードに書かれた整数の平均値としてあり得る最大値を、2 行目には選んだカードに書かれた整数の中央値としてあり得る最大値を出力せよ。 平均値の出力については、正しい値との相対誤差または絶対誤差が 10^{-3} 以下であれば正答とみなされる。
入力例 1
6 2 1 2 1 1 10
出力例 1
4 2
2 番目、4 番目、6 番目のカードを選ぶと、書かれた整数の平均は \frac{12}{3} = 4 となり、これが最大です。
1 番目、3 番目、5 番目、6 番目のカードを選ぶと、書かれた整数の中央値は 2 となり、これが最大です。
入力例 2
7 3 1 4 1 5 9 2
出力例 2
5.250000000 4
平均値の出力については誤差が認められるので、例えば 5.2491 と出力しても正答とみなされます。ただし、中央値は正確な値を出力しなければなりません。
Score : 500 points
Problem Statement
We have N cards. The i-th card (1 \leq i \leq N) has an integer A_i written on it.
Takahashi will choose any number of cards from these. However, for each i (1 \leq i \leq N - 1), at least one of the i-th and (i+1)-th cards must be chosen.
Find the following values.
- The maximum possible average of the integers written on the chosen cards
- The maximum possible median of the integers written on the chosen cards
Here, the median of the n integers is defined to be the \lceil \frac{n}{2} \rceil-th smallest of them, where \lceil x \rceil is the smallest integer not less than x.
Constraints
- 2 \leq N \leq 10^5
- 1 \leq A_i \leq 10^{9}
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N A_1 \ldots A_N
Output
Print two lines. The first and second lines should contain the maximum possible average and maximum possible median of the integers written on the chosen cards, respectively. For the average, your output will be considered correct when its relative or absolute error from the exact answer is at most 10^{-3}.
Sample Input 1
6 2 1 2 1 1 10
Sample Output 1
4 2
Choosing the 2-nd, 4-th, and 6-th cards makes the average of the written integers \frac{12}{3} = 4, which is the maximum possible.
Choosing the 1-st, 3-rd, 5-th, and 6-th cards makes the median of the written integers 2, which is the maximum possible.
Sample Input 2
7 3 1 4 1 5 9 2
Sample Output 2
5.250000000 4
For the average, your output may contain some degree of error: for example, the output 5.2491 is still considered correct. For the median, however, the exact value must be printed.