ブルーブリッジカップBASIC-23基礎練習チップテスト

問題の説明は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
分析:テーマにはいくつかのキーがあります:1.「良いチップは悪いチップより多い」2.悪いチップで他のチップをテストすると、良いか悪いかのテスト結果がランダムに与えられます.したがって、現在のチップの悪い評価が良い評価より大きい場合にのみ、これが悪いチップであることを確定することができるが、逆に、現在のチップの良い評価が悪い評価より大きい場合、悪いチップは信用できないため、良いチップであることを確定することはできない.だから、私たちはまず悪いチップを見つけて、それから新しい情報に基づいて判断を更新するしかありません.実はよく考えてみると、この問題は完全に正確ではありません.なぜなら、すべてが1である可能性がありますが、悪いチップが存在しているからです.悪いチップが嘘をつくからだ.

#include
#include
using namespace std;
int map[21][21];
vectorbad;
bool book[21];
int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            cin >> map[i][j];
        }
    }
    int len = - 1;
    while(len != bad.size()) {
        len = int(bad.size());
        for (int i = 1; i <= n; i++) {
            if(book[i] == true) continue;
            int cnt = 0;
            for (int j = 1; j <= n; j++) {
                if(map[j][i] == 1 && i != j && book[j] == false) {
                    cnt ++;
                }
            }
            if (cnt < n / 2) { // 
                bad.push_back(i);
                book[i] = true;
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        if (book[i] == false) {
            cout << i << " ";
        }
    }
    return 0;
}