読者です 読者をやめる 読者になる 読者になる

JOI 2006 問題5

あなたはある機械の製造工場で品質管理の責任者をしている. この機械には, 部品として電源とモーターとケーブルが必要である. 製造工場には電源が a 個, モーターが b 個, ケーブルが c 個あり, それぞれ 1 から a まで, a+1 から a+b まで, a+b+1 から a+b+c までの番号が付いている. 困ったことに, 部品の中に故障しているものがあるかもしれない. 工場ではどの部品が故障していてどの部品が正常であるかを知りたい.

そこで, 工場では次の方法で部品を検査した. 電源とモーターとケーブルを1つずつ持ってきてつなぎ, 動作させてみる. このとき, 3つの部品がすべて正常であるときは正しく動作して「合格」とわかる. 3つの中に故障している部品が1つでも入っているときは正しく動作しないので「不合格」とわかる. (工場で作っている機械はとても精密なので, 故障した部品がまざっているのに偶然正しく動作してしまうなどということは起きないのだ.)

あなたには検査結果のリストが渡される. 検査結果のリストの各行には, 検査に使った電源とモーターとケーブルの番号と, 検査が合格だったか不合格だったかが書かれている.

検査結果のリストが与えられたとき, すべての部品を, 検査結果から確実に故障しているとわかる部品と, 確実に正常とわかる部品と, 検査結果からは故障しているとも正常であるとも決まらない部品に分類するプログラムを作成せよ.

入力ファイルの形式は以下の通りである.

1 行目には 3 個の整数が空白区切りで書かれており, 順に電源の個数 a, モーターの個数 b, ケーブルの個数 c を表す.
2 行目には 1 個の整数が書かれており, 検査結果のリストに含まれる検査の回数 N が書かれている.
続く N 行は検査結果のリストを表す. 各行には, 4 個の整数 i, j, k, r が1つの空白を区切りとして書かれており, 電源 i とモーター j とケーブル k をつないで検査した結果が, 「合格」 (r=1 のとき) か「不合格」 (r=0 のとき) だったことを表す.

a, b, c, N は 1 ≦ a, b, c ≦ 100, 1 ≦ N ≦ 1000 を満たす.

提出する出力ファイルは以下の通りである. 出力ファイルは a+b+c 行からなる.

i 行目 (1 ≦ i ≦ a+b+c):

  • 検査結果から部品 i が故障しているとわかる場合は 0 を出力する.
  • 検査結果から部品 i が正常とわかる場合は 1 を出力する.
  • 検査結果から部品 i が故障しているか正常であるかが決まらない場合は 2 を出力する.

拍子抜けするほど簡単である。

0,1,2のどれかが入る配列を用意する。2で初期化しておくと良い。

rが1であればi,j,kのすべてが1である。まずは、それをすべての場合で確認する。

0の場合はどれか2つが1であればもう1つは0になると言える。

#include <iostream>
using namespace std;
int main() {
 int a, b, c, n, i[1000], j[1000], k[1000], r[1000], e;
 int v[1000] = { 0 };
 while (1) {
  cin >> a >> b >> c;
  if (a == 0 && b == 0 && c == 0) return 0;
  cin >> n;
  for (e = 1; e <= a + b + c; e++) {
   v[e] = 2;
  }
  for (e = 0; e < n; e++) {
   cin >> i[e] >> j[e] >> k[e] >> r[e];
   if (r[e] == 1) {
    v[i[e]] = 1;
    v[j[e]] = 1;
    v[k[e]] = 1;
   }
  }
  for (e = 0; e < n; e++) {
   if (r[e] == 0) {
    if (v[i[e]] == 1 && v[j[e]] == 1) {
     v[k[e]] = 0;
    }
    else if (v[i[e]] == 1 && v[k[e]] == 1) {
     v[j[e]] = 0;
    }
    else if (v[j[e]] == 1 && v[k[e]] == 1) {
     v[i[e]] = 0;
    }
   }
  }
  for (e = 1; e <= a + b + c; e++) {
   cout << v[e] << endl;
  }
 }
 return 0;
}