【ブルーブリッジカップ】基礎練習チップテスト
6629 ワード
問題はn n n n(2≦n n n≦20)ブロックチップが記述され,良し悪しが記述され,良し悪しチップは良し悪しチップより多いことが知られている.各チップは他のチップをテストするために使用できます.他のチップをチップでテストすると、テストされたチップが良いか悪いかを正確に与えることができます.一方、悪いチップで他のチップをテストすると、良いか悪いかのテスト結果がランダムに与えられます(すなわち、この結果は被テストチップの実際の良し悪しとは関係ありません).すべてのチップのテスト結果を示し、どのチップが良いチップなのかを尋ねます.入力フォーマット入力データの第1の動作は、チップ個数を表す整数n n n nである.2行目からn+1 n+1 n+1行目n表中の各データは0または1であり、このn n n n行目のi i i行目j j j列目(1≦i i i,j≦n n)のデータは、i i iブロック目iチップでj jブロック目jチップを試験したときに得られた試験結果を示し、1は良く、0は悪く、i=j i=j i=j i=j i=jの場合は一律1(このチップ対自身の試験結果は表に示さない.チップは自身を試験できない).出力フォーマットは、すべての良いチップの番号付けサンプルを小さい順に出力3 1 0 1 0 1 0 1 0 1 0 1サンプル出力1 3
個人的な考え方:良いチップが悪いチップより多い以上、テストされたチップが0の個数が半数以上であれば、悪いチップであることを証明することができる.では、悪いチップを除いた残りは良いチップです.
個人的な考え方:良いチップが悪いチップより多い以上、テストされたチップが0の個数が半数以上であれば、悪いチップであることを証明することができる.では、悪いチップを除いた残りは良いチップです.
#include
using namespace std;
int n;
int a[25][25];
bool vis[25];
int main() {
cin >> n;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
cin >> a[i][j];
}
}
for (int j = 1; j <= n; ++j) {
int cnt = 0;
for (int i = 1; i <= n; ++i) {
if (i != j) {
if (a[i][j] == 0) {
cnt++;
}
}
}
if (cnt >= (n + 1)/2) {
vis[j] = true;
}
}
for (int i = 1; i <= n; ++i) {
if (!vis[i])
cout << i << " ";
}
return 0;
}