PAT(Advanced Level)1014:チップテスト

1014:チップテスト

時間制限:1 Secメモリ制限:128 MB

タイトルの説明

基礎練習チップテスト時間制限:1.0 sメモリ制限:512.0 MB問題記述は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

入力

しゅつりょく

#include 
#include 
#include 
#include 
#include 
#define MAX_SIZE 25
using namespace std;
 
vector cpus[MAX_SIZE]; // check;
set res;
queue check;
int n;
bool judge(int believe_index)
{
    while (!check.empty())
        check.pop();
    int i, j, temp;
    for (i = 0; i < n; i++)
    {
        check.push(i);
    }
    int t = 0;
    while (t < n)
    {
        j = check.size();
        for (i = 0; i < j; i++)
        {
            temp = check.front();
            check.pop();
            if (cpus[temp][t] == cpus[believe_index][t])
            {
                check.push(temp);
            }
        }
        t++;
    }
    if ((check.size()) >= (n - check.size()))
    {
        res.clear();
        j = check.size();
        for (i = 0; i < j; i++)
        {
            res.insert(check.front());
            check.pop();
        }
        return true;
    }
    return false;
}
int main()
{
    int temp;
    cin >> n;
    //input
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> temp;
            cpus[i].push_back(temp);
        }
    }
    //map
    bool isOk = false;
    for (int i = 0; i < n && !isOk; i++)
    {
        isOk = judge(i);
    }
    for (set::iterator it = res.begin(); it != res.end(); it++)
    {
        cout << (*it) + 1 << " ";
    }
    cout << endl;
    return 0;
}
/**************************************************************
    Problem: 1014
    User: 1151331112
    Language: C++
    Result:  
    Time:16 ms
    Memory:1556 kb
****************************************************************/