ブルーブリッジカップ練習——チップテスト

1808 ワード

タイトルの説明
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 

サンプル出力

1 3

正しい考え方:テーマは悪いチップが他のチップをテストする結果がランダムであることを教えて、しかも良いチップの数は必ず悪いチップの数より多いことを教えて、私达は悪いチップが他のチップをテストする結果がすべて間違っていることを想定して、マトリックスの1列を単位にして、そのすべての行の和を見て、もしこの和がn/2より大きいならば、良いチップの数が悪いチップの数より大きくて、テストが正確で、このチップは良いチップです;そうでなければ、このチップが不良チップであることを示す
JAva実装:
import java.math.BigInteger; import java.util.ArrayList; import java.util.HashSet; import java.util.Iterator; import java.util.Scanner; import java.util.Set; import java.util.Vector; public class Main {        public static void main(String[] args)     {         Scanner sc=new Scanner(System.in);         int n=sc.nextInt();         int [][]a=new int[n][n];         int []c=new int[20];         int count=0;         for(int i=0;i             for(int j=0;j                 a[i][j]=sc.nextInt();             }         }         for(int j=0;j             int sum=0;             for(int i=0;i                 sum+=a[i][j];             }             if(sum>n/2) {                 c[count++]=j+1;             }         }         for(int i=0;i             if(i!=count-1){                System.out.print(c[i]+"");             }             else                 System.out.print(c[i]);         }     } }