ブルーブリッジ:チップテスト

タイトル

問題の説明はn(2≦n≦20)ブロックチップがあり、良いチップと悪いチップがあり、良いチップが悪いチップより多いことが知られている.各チップは他のチップをテストするために使用できます.他のチップをチップでテストすると、テストされたチップが良いか悪いかを正確に与えることができます.一方、悪いチップで他のチップをテストすると、良いか悪いかのテスト結果がランダムに与えられます(すなわち、この結果は被テストチップの実際の良し悪しとは関係ありません).すべてのチップのテスト結果を示し、どのチップが良いチップなのかを尋ねます.入力フォーマット入力データの第1の動作は、チップ個数を表す整数nである.2行目からn+1行目n*nのテーブルで、1行n個のデータが表示されます.表中の各データは0または1であり、このn行のi行目j列目(1≦i,j≦n)のデータは、iブロック目チップでjブロック目チップをテストしたときに得られたテスト結果を示し、1は良い、0は悪い、i=jの場合は一律に1(このチップが自分に対するテスト結果を示さない.コアシートは自分に対してテストできない)である.出力フォーマットは、すべての良いチップの番号付けサンプルを小さい順に出力3 1 0 1 0 1 0 1 0 1 0 1サンプル出力1 3

ぶんせき

**最も正しい考え方:**良いチップは悪いチップより多いので、各チップを他のチップn個と比較する場合、テストの結果がn/2より大きい限り、これが良いチップであることを証明し、チップの位置を出力すればよい.各列単位で1の個数(和を求めればよい)を計算し、sumが半分を超えると良いチップとなる.
**説明:**この問題は実は肝心な問題は一つで、他のチップが一つのチップに対する判断結果が1の個数が0より大きい個数であれば、これは良いチップであると判断することができる.どうしてですか.タイトルでは、悪いチップの判断はすぐに1でなければ0ではないので、良いチップ(検出される)の判断に対しては、悪い判断(検出者)でこれが良いと判断し、表示1と表示0の確率は50%であり、もう一つ良いチップ(検出者)もこの良いチップ(検出される)を判断すれば、この結果は必ず1であり、したがって、この表示1の総数は必ず表示0の個数より大きい.
#コード解析

import java.util.Scanner;

public class   {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int[][] arr=new int[n][n];
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				arr[i][j]=sc.nextInt();
			}
		}
		sc.close();
		
		for(int i=0;i<n;i++){
			int sum1=0;
			int sum0=0;
			for(int j=0;j<n;j++){
				if(i==j)
					continue;
				else if(arr[j][i]==1)
						sum1++;
					else
						sum0++;
			}
			if(sum1>=sum0)
				System.out.print((i+1) +" ");
		}
	}

}