問題一覧 > 通常問題

No.1440 The Quiz Competition

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 17
作問者 : first_vilfirst_vil / テスター : 👑 NachiaNachia
0 ProblemId : 5712 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-03-26 23:24:18

問題文

先日、Vil君が司会を務めるクイズ大会が開催されました。大会のルールは以下のようなものです。

  • 開始時点で参加者の点数は全員 $0$ である。
  • 人 $i$ が正答したとき、人 $i$ の点数が $1$ 増加する。
  • 人 $i$ が誤答したとき、それが人 $i$ の $D$ 回目の誤答であるとして、人 $i$ の点数が $D$ 減少する(点数に下限はない)。
  • 最終時点で人 $i$ より真に点数が大きい人の人数を $R$ として、人 $i$ は $R+1$ 位となる。

この大会には $N$ 人が参加し、$N$ 人合計で $A$ 回の正答と $W$ 回の誤答があったことが分かっています。このとき $K$ 位の人の点数として考えられる最大値を求めてください。どのような結果であっても $K$ 位が現れない場合はそのことを報告してください。

$T$ 個のテストケースそれぞれについて答えてください。

入力

$T$
$N_1\ A_1\ W_1\ K_1$
$N_2\ A_2\ W_2\ K_2$
$\vdots$
$N_T\ A_T\ W_T\ K_T$
  • 入力はすべて整数
  • $1 \le T \le 100$
  • $2 \le N_t \le 2 \times 10^5$
  • $0 \le A_t,W_t \le 10^9$
  • $1 \le K_t \le N_t$
  • $\displaystyle \sum_{t=1}^{T}N_t \le 2 \times 10^5$
$t$ 個目のテストケースでは $N=N_t,A=A_t,W=W_t,K=K_t$ とした場合の答えを求めてください。

出力

各テストケースに対し、どのような結果であっても $K$ 位が現れない場合は :( を、そうでない場合は $K$ 位の人の点数として考えられる最大値を出力し、改行してください。

サンプル

サンプル1
入力
3
4 9 3 2
7 8 1 7
7 1 0 6
出力
4
0
:(

$1$ つ目のテストケースでは、例えば以下のようにすると $2$ 位の点数が $4$ となります(正答をo、誤答をxとしてそれぞれの回数を表しています)。

$1:\ $ooooo
$2:\ $oooo
$3:\ $x 
$4:\ $xx

$2$ つ目のテストケースでは、例えば $5$ 人が $1$ 回の正答、別の $1$ 人が $3$ 回の正答と $1$ 回の誤答をすると、$7$ 位の点数が $0$ となります。

$3$ つ目のテストケースでは、正答した $1$ 人が $1$ 位、それ以外が $2$ 位となるので $6$ 位は現れません。

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