/* ACMプログラミングコンテスト 過去問 2008年国内予選 Problem A ■問題 (http://sparth.u-aizu.ac.jp/icpc2008/d_problem.php?lang=jp) 太郎と花子はそれぞれカードを何枚か持っている.各カードには点数が書かれている.太郎のカードと花子のカードを 1 枚ずつ交換して,それぞれの持つカードの合計点数が等しくなるようにしたい.どのカードとどのカードを交換したらよいか. ただし,カードを交換しなくても合計点数が等しい場合でも,必ずカードの交換を行うものとする. Input 入力は,いくつかのデータセットからなる.各データセットは次の形式で与えられる. n m s1 s2 ... sn sn+1 sn+2 ... sn+m 各データセットの最初の行は空白ひとつで区切られたふたつの数 n と m を含み, n は太郎のカードの枚数,m は花子のカードの枚数を表す.続く n+m 行には,各カードの点数が 1 行にひとつずつ並ぶ.最初の n 個の点数 (s1 から sn まで) は太郎のカードの点数,残りの m 個の点数 (sn+1 から sn+m まで) は花子のカードの点数を表す. n および m は 100 以下の正の整数とし,カードの点数は 0 以上 100 以下の整数値とする. 入力の終わりは,空白ひとつで区切られたふたつの 0 を含む 1 行で示される. Output 各データセットに対し,ふたつの数を 1 行にひとつの空白で区切って出力せよ.最初の数は太郎が花子に渡すカードの点数, 2 番目の数は花子が太郎に渡すカードの点数である.なお,合計を等しくするようなカードの交換の方法が複数ある場合は,交換するカードの点数の和が最小となるものを出力すること. カードの点数の合計を等しくするような交換が存在しない場合は -1 のみを含む 1 行を出力すること.出力形式に従わない余計な文字を含んではならない. ■解答例 カードが配布された時点での太郎と花子のカードの合計を、sum_0、sum_1とするとこの問題は以下のように表すことができる。 (sum_0 + sum_1)/2 == sum_0 - card0 + card1 ここで、card0は太郎が交換しようとしているカード、card1は花子が交換しようとしているカードである。この式からcard0が与えられたときに期待するcard1は以下のように求められる。 card1 = (sum_0+sum_1)/2 - sum_0 + card0 また、交換する組み合わせが複数ある場合には、交換する2枚のカードの数が最も小さいカードを選択する必要があるため、以下の制限があることになる。 min(card0 + card1) 以上を踏まえ、解答を得るためのアルゴリズムは、次のようである。 1. 太郎および花子のカードのすべてに対して、期待する交換カード、および、交換した場合の2枚のカードの合計を計算する。 2. その合計によって太郎、花子のカードを区別せずに昇順によってソートする。 3. ソートされたカードの最初から順に、期待する交換カードを以降のカードから検索し、発見できればそれを解答とする。 4. すべてのカードの組み合わせを確認しても期待するカードが見つからない場合には-1を出力する。 最悪ケース(解答が見つからない)場合のデータを走査する回数は、  1(読み込み) + 1(期待する交換カードの計算) + n*(n-1)/2(相手カードの検索) である。但し、期待するカードがマイナスの値の場合、相手カードの検索は行わない。 */ import java.io.*; import java.util.*; public class Exp2008_A { /** カードの数値、どちらのプレイヤのカードか、また、このカードを交換する場合に相手のどの数字と交換できるか */ static class Datum{ int value; int player; int pair; }; /** メイン関数 */ public static void main(String[] args) throws Exception{ // ファイルからの読み込み BufferedReader br = new BufferedReader(new FileReader(args[0])); // 結果を出力するファイル PrintWriter pw = new PrintWriter(new FileWriter(args[1])); // 読み込んだ1行がこの変数に入る。 String line=null; int n,m; while(true){ // ファイルから1行読み込む。 line=br.readLine(); // 太郎のカード数nと、花子のカード数mを読み込む。 String[] parts = line.split(" "); n = Integer.parseInt(parts[0]); m = Integer.parseInt(parts[1]); if(n==0 && m==0){ break; } // カード情報を読み込む、また、同時に合計を計算する。 Vector data = new Vector(); int[] sums = new int[2]; for(int cnt=0;cnt<(n+m);cnt++){ line = br.readLine(); Datum datum = new Datum(); datum.value = Integer.parseInt(line); datum.player = cnt(){ public int compare(Datum o1,Datum o2){ int v1 = o1.value+o1.pair; int v2 = o2.value+o2.pair; return v1>v2?1:(v1 0){ for(int cnt2=cnt1+1;cards[0]==0 && cnt2