問題一覧 > 通常問題

No.1309 テスト

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 4
作問者 : 👑 QCFiumQCFium / テスター : 👑 beetbeet
0 ProblemId : 4212 / 出題時の順位表
問題文最終更新日: 2020-12-06 00:02:31

問題文

$N(N$は奇数$)$ 人の人間がテストを受け、それぞれ $0$ 点以上 $P$ 点以下の整数得点を獲得しました。
あなたはテスト結果について $N$ 人の得点の中央値が $X$ 点、最頻値が $Y$ 点という情報を得ました。情報に合致する $N$ 人の得点が存在するならそのような $N$ 人の得点の総和として考えられる最大値を求めてください。存在しないならそのことを報告してください。

中央値とは $N$ 人の得点を昇順ソートしたときに1-indexedで前から $\frac{N + 1}{2}$ 個目の値のことです。
最頻値はその得点を取った人数が一番多い得点のことです。但しこの問題においてはそのような得点が複数ある場合それらの平均を最頻値とします。

一つのテストデータでちょうど $10$ 個のケースが与えられるので全てについて解いてください。

注意

この問題の実行時間制限は $4$ 秒です。
writer解は C++14 : 920 ms, Java11 : 1703 ms, PyPy3 : 3994 ms でACしています。

入力

$N_1\ P_1\ X_1\ Y_1$
$N_2\ P_2\ X_2\ Y_2$
$N_3\ P_3\ X_3\ Y_3$
$\hspace{25pt} \vdots$
$N_{10}\ P_{10}\ X_{10}\ Y_{10}$

入力は全て整数
$1 \le i \le 10$ のとき :
 $1 \le N_i \lt 1000$
 $N_i$ は奇数
 $1 \le P_i \le 10^9$
 $0 \le X_i \le P_i$
 $0 \le Y_i \le P_i$

出力

$10$ 行に渡って、$i$ 行目では $N = N_i, P = P_i, X = X_i, Y = Y_i$ としたときの情報に合致する $N$ 人の得点の総和として考えられる最大の値を出力してください。
但し、情報に合致するテスト結果が存在しないならばその行は-1を出力してください。

サンプル

サンプル1
入力
5 100 80 80
5 100 70 80
5 100 100 0
7 100 7 53
17 100 69 92
11 100 27 55
1 100 50 50
101 100 71 68
999 1000000000 500000000 500000001
999 1000000000 500000001 500000000
出力
440
400
-1
325
1379
650
50
8518
747999877246
749000000000

1行目 : 例えば$N$人の得点が {$80, 80, 80, 100, 100$} のとき中央値、最頻値ともに $80$ 点で条件を満たし、総和が $440$ で最大になります。
2行目 :
例えば {$66, 68, 70, 97, 99$} があります。
$1$度しか出現しないものも、$2$回以上出現するものが存在しないなら最頻値とすることに注意してください。
また、この場合全て出現回数が最大なのでそれらの平均の $80$ が最頻値とされます。
3行目 : ありえない場合-1を出力します。
4行目 : 例えば {$6, 6, 6, 7, 100, 100, 100$} が条件を満たすもののなかで総和が最大です。
5行目 : 例えば {$67, 67, 67, 68, 68, 68, 69, 69, 69, 92, 92, 92, 92, 99, 100, 100, 100$} 。
6行目 : {$25, 25, 26, 26, 27, 27, 98, 98, 99, 99, 100$}
7行目 : {$50$}

サンプル

サンプル2
入力
3 100 0 0
3 100 30 31
3 100 30 53
3 100 30 54
3 100 50 50
3 100 100 100
17 8 1 3
19 19 8 11
19 17 2 7
19 9 2 9
出力
100
93
159
-1
200
300
59
241
148
99

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。