新規
編集
添付
時間制限:1000ミリ秒
メモリ制限:65536KB
Special Judge
陪審員交渉
問題 
遠くの国フロブニアでは、裁判の評決は公衆から選ばれたメンバーからなる陪審員によって決定される。裁判は幾度となく行われるので、陪審員も毎回選ばなければならない。これは次のような方法によってなされる。最初に、公衆のなかからランダムに何人かが選ばれる。それらプールの中のそれぞれの人について、被告側と原告側がそれぞれ各人に対する優先順位をあらわす0～20の番号をつける。0は全てにおいて良くないことを意味し、逆に20はその人は陪審員として理想的と判断されたことを表す。
これらの優先度に基づいて、裁判所は陪審員を選択する。公平は裁判を保証するため、各陪審員が被告側と原告側のどちらにより好まれているかの方向性は、可能な限り公平であるようべきである。したがって、陪審員は両方を満足させる方法で選ばれる必要がある。
これをもっと明確にしよう: n人の陪審員候補と、それぞれの陪審員iについて2つの値di(被告側の評価)とpi(原告側の評価)が与えられる。あなたはm人の陪審員を選ばなくてはならない。Jを{1,..., n}の部分集合で要素数がmであるようなものとすると、D(J) = sum(dk)かつP(J) = sum(pk)、(ただしkはJの要素)の2つはそれぞれ被告側と原告側による評価の合計とする。
Jが最適であるとは、|D(J) - P(J)|の値が最小であるときである。もし|D(J) - P(J)|を最小にするJが何通りかある場合は、陪審員は両方にとって可能な限り理想に近いほうがいいので、D(J) + P(J)が最大であるようなJを選ぶこと。
あなたは、陪審員候補を与えられたときに最適な陪審員の組を選ぶ選択プロセスを実装しなければならない。
入力
入力ファイルはいくつかの陪審員選択の要求を含む。各要求は2つの整数n,mを含む行ではじまる。nは陪審員候補の人数で、mは選びたい陪審員の人数である。
これらの値は1<=n<=200, 1<=m<=20、そしてもちろんm<=nを満たす。続くn行はそれぞれ2つの整数piとdi(i = 1,...,n)を含む。要求の間は空行によって区切られる。
ファイルは、n=m=0なる要求によって終わる。
出力
各要求について、まず要求の番号を含む1行を出力すること('Jury #1', 'Jury #2', など)。
次の行にはあなたの選んだJについて、上記に示したD(J)とP(J)の値を出力し、その次の行には選ばれたm人の陪審員の番号を昇順で出力せよ。陪審員の番号の前には全て空白文字を入れること。
各テストケースの後には空行を出力すること。
入力例
4 2 1 2 2 3 4 1 6 2 0 0
出力例
Jury #1 Best jury has value 6 for prosecution and value 4 for defence: 2 3
ヒント
もしあなたの解が非効率なアルゴリズムを基にしているのなら、それは割り当てられた時間内には動作しないかもしれない。
出典
Southwestern European Regional Contest 1996
