問題一覧 > 通常問題

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 が誤答したとき、それが人 iD 回目の誤答であるとして、人 i の点数が D 減少する(点数に下限はない)。
  • 最終時点で人 i より真に点数が大きい人の人数を R として、人 iR+1 位となる。

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

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

入力

T
N1 A1 W1 K1
N2 A2 W2 K2

NT AT WT KT
  • 入力はすべて整数
  • 1T100
  • 2Nt2×105
  • 0At,Wt109
  • 1KtNt
  • t=1TNt2×105
t 個目のテストケースでは N=Nt,A=At,W=Wt,K=Kt とした場合の答えを求めてください。

出力

各テストケースに対し、どのような結果であっても 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もしくは右上の雲マークをクリックしてアカウントを作成してください。