倉庫の警報装置は、s 個のセンサーの値を g 個のゲートでまとめて、警報を鳴らすかどうかを決める。 値が流れる電線には番号があり、i 番のセンサーの値は i 番の電線に、i 番目のゲートの結果は s + i 番の電線に乗る。 1行目に s、g、測定の回数 q が、続く g 行にゲートが順に与えられる。 ゲートの行は "and a b"、"or a b"、"xor a b"、"not a" のどれかで、a と b はそのゲートの結果の電線より番号が小さい電線である。 a と b が同じ電線のこともある。 最後のゲートの結果が警報である。 続く q 行に測定が1行に1つずつ与えられ、測定はセンサー1番から s 番までの値 s 個である。 センサーの値は yes か no だが、故障したセンサーは値が分からないので ? と書かれる。 測定ごとに2つのものを求めよ。 1つ目は判定で、分からない値を「不明」という3つ目の値として、ゲートを順に計算したときの警報の値である。 and は2つの値のうち1つでも no なら no、そうでなく1つでも不明なら不明、それ以外は yes である。 or は2つの値のうち1つでも yes なら yes、そうでなく1つでも不明なら不明、それ以外は no である。 xor は1つでも不明なら不明、そうでなく2つの値が異なれば yes、同じなら no である。 not は不明なら不明、yes なら no、no なら yes である。 判定は、警報の値が不明なら unknown、そうでなければ yes か no である。 2つ目は個数で、故障したセンサーそれぞれに yes か no を入れるすべての方法のうち、警報が yes になる方法の数である。 故障したセンサーが u 個なら方法は 2^u 通りで、故障したセンサーがなければ方法は与えられた値そのままの1通りである。 測定ごとに、判定と個数を空白1つで区切って1行に出力せよ。 ゲートを1つずつ別々に計算するので、判定が unknown でも個数が 0 や 2^u になることがある。
入力
1 ≤ s ≤ 20、1 ≤ g ≤ 100、1 ≤ q ≤ 20。 i 番目のゲートの a、b は 1 以上 s + i − 1 以下。 1つの測定に ? は8個以下。 値は空白1つで区切って与えられる
出力
測定ごとに1行: 判定(yes、no、unknown)と個数
例 1 · stdin
3 3 4
and 1 2
not 3
or 5 4
yes yes no
? no yes
? no ?
no ? no
stdout
yes 1
no 0
unknown 2
yes 2
例 2 · stdin
2 3 4
not 1
or 1 3
xor 4 2
? no
? yes
yes ?
no no
stdout
unknown 2
unknown 0
unknown 1
yes 1
main.py
エラー一覧00F8 ↓ · ⇧F8 ↑
入力(stdin)
実行すると、これらの行が順に input()・標準入力に渡されます(実行中に入力を求めません)。
$ 準備完了
コードを入力して解くにはパソコンで開いてください。モバイルでは問題と解答を見られます。
ほかの言語では？言語別の解答を見る · 8 言語の解答
真・偽に「不明」を加えた3つの値を、言語ごとにどこに入れるかを比べます。 C# の bool? はこの問題の規則そのままです。 a & b、a | b、a ^ b、!a が null を不明として扱うので、null & false は false、null | true は true、!null は null です。 ただし a && b は bool? には使えずコンパイルエラー(CS0019)で、条件では x == true と聞きます。 ほかの言語は関数を自分で作ります。 不明を Python は None、JS・TS は null(TS の型は boolean | null)、Java は Boolean の null、C++ は空の std::optional<bool>、Craykon は なし に入れ、C は enum { NO, YES, UNKNOWN } を作ります。 罠その1: 言語の and・or をそのまま使うと、左に何が来たかで答えが変わります。 Python None and False は None なのに False and None は False で、False or None は None です。 JS null && false は null、Craykon なし && 偽 も なし です。 1つ目の例の2番目の測定で ? and no が no にならず、判定が unknown になります。 罠その2: not です。 Python not None、JS !null、Craykon !なし はどれも真で、C で不明を 2 にすると !2 は 0 です。 罠その3: 「1つでも不明なら不明」を先に見ると ? and no が unknown になります。 and は no を、or は yes を先に探します。 罠その4: xor を a !== b だけで書くと、JS では null !== false が true なので不明が消えます(2つ目の例の最初の測定)。 罠その5: Java で Boolean a = null のとき if (!a) は値を取り出すところで NullPointerException で止まります。 null かどうかを先に聞きます。 罠その6: C++ の std::optional<bool> を if (a || b) と使うと、値ではなく「値が入っているか」を聞くので、false が入っていても真です。 値は *a で取り出します。 罠その7: 個数を数えるとき、0 から 2^u − 1 までの数 mask の j 番目のビットは j 番目の故障センサーの値です。 センサー番号 i で mask >> i を見ると、故障センサーが後ろの番号のときに間違えます(1つ目の例の3番目の測定)。 判定と個数は別のものを測っています。 2つ目の例の x or not x は x が何でも yes ですが、ゲートを1つずつ計算すると unknown です。
Pythonmain.py · 71 行
import sysdef and3(a, b): if a is False or b is False: return False # 한쪽이 거짓이면 다른 쪽을 몰라도 거짓 if a is None or b is None: return None return Truedef or3(a, b): if a is True or b is True: return True if a is None or b is None: return None return Falsedef xor3(a, b): if a is None or b is None: return None return a != bdef not3(a): return None if a is None else not adef evaluate(gates, wires): """wires 앞쪽에 센서 값이 들어 있다. 게이트를 차례로 계산해 마지막 전선의 값을 돌려준다.""" wires = wires[:] for op, a, b in gates: if op == "and": wires.append(and3(wires[a], wires[b])) elif op == "or": wires.append(or3(wires[a], wires[b])) elif op == "xor": wires.append(xor3(wires[a], wires[b])) else: wires.append(not3(wires[a])) return wires[-1]def main(): lines = sys.stdin.read().split("\n") s, g, q = map(int, lines[0].split()) gates = [] for line in lines[1:1 + g]: parts = line.split() a = int(parts[1]) - 1 b = int(parts[2]) - 1 if len(parts) == 3 else a gates.append((parts[0], a, b)) word = {"yes": True, "no": False, "?": None} out = [] for line in lines[1 + g:1 + g + q]: sensors = [word[w] for w in line.split()] result = evaluate(gates, sensors) unknown = [i for i in range(s) if sensors[i] is None] count = 0 for mask in range(1 << len(unknown)): for j, i in enumerate(unknown): # mask의 j번째 비트 = j번째 고장 센서 sensors[i] = (mask >> j) & 1 == 1 if evaluate(gates, sensors) is True: count += 1 name = "unknown" if result is None else ("yes" if result else "no") out.append(f"{name} {count}") print("\n".join(out))main()
JavaScriptmain.js · 42 行
const lines = require("fs").readFileSync(0, "utf8").split("\n");// 세 값 논리: true, false, null(모름)const and3 = (a, b) => (a === false || b === false ? false : a === null || b === null ? null : true);const or3 = (a, b) => (a === true || b === true ? true : a === null || b === null ? null : false);const xor3 = (a, b) => (a === null || b === null ? null : a !== b);const not3 = (a) => (a === null ? null : !a);// 앞쪽에 센서 값이 든 배열을 받아, 게이트를 차례로 계산한 마지막 전선의 값을 돌려준다function evaluate(gates, sensors) { const wires = sensors.slice(); for (const [op, a, b] of gates) { if (op === "and") wires.push(and3(wires[a], wires[b])); else if (op === "or") wires.push(or3(wires[a], wires[b])); else if (op === "xor") wires.push(xor3(wires[a], wires[b])); else wires.push(not3(wires[a])); } return wires[wires.length - 1];}const [s, g, q] = lines[0].trim().split(" ").map(Number);const gates = [];for (let i = 1; i <= g; i++) { const parts = lines[i].trim().split(" "); const a = Number(parts[1]) - 1; const b = parts.length === 3 ? Number(parts[2]) - 1 : a; gates.push([parts[0], a, b]);}const out = [];for (let t = 0; t < q; t++) { const sensors = lines[1 + g + t].trim().split(" ").map((w) => (w === "?" ? null : w === "yes")); const result = evaluate(gates, sensors); const unknown = []; for (let i = 0; i < s; i++) if (sensors[i] === null) unknown.push(i); let count = 0; for (let mask = 0; mask < 1 << unknown.length; mask++) { unknown.forEach((i, j) => { sensors[i] = ((mask >> j) & 1) === 1; }); // j번째 비트 = j번째 고장 센서 if (evaluate(gates, sensors) === true) count++; } out.push((result === null ? "unknown" : result ? "yes" : "no") + " " + count);}console.log(out.join("\n"));
TypeScriptmain.ts · 46 行
import { readFileSync } from "node:fs";type Tri = boolean | null; // null = 모름type Gate = { op: string; a: number; b: number };const lines: string[] = readFileSync(0, "utf8").split("\n");const and3 = (a: Tri, b: Tri): Tri => (a === false || b === false ? false : a === null || b === null ? null : true);const or3 = (a: Tri, b: Tri): Tri => (a === true || b === true ? true : a === null || b === null ? null : false);const xor3 = (a: Tri, b: Tri): Tri => (a === null || b === null ? null : a !== b);const not3 = (a: Tri): Tri => (a === null ? null : !a);// 앞쪽에 센서 값이 든 배열을 받아, 게이트를 차례로 계산한 마지막 전선의 값을 돌려준다function evaluate(gates: Gate[], sensors: Tri[]): Tri { const wires: Tri[] = sensors.slice(); for (const { op, a, b } of gates) { if (op === "and") wires.push(and3(wires[a], wires[b])); else if (op === "or") wires.push(or3(wires[a], wires[b])); else if (op === "xor") wires.push(xor3(wires[a], wires[b])); else wires.push(not3(wires[a])); } return wires[wires.length - 1];}const [s, g, q]: number[] = lines[0].trim().split(" ").map(Number);const gates: Gate[] = [];for (let i = 1; i <= g; i++) { const parts: string[] = lines[i].trim().split(" "); const a = Number(parts[1]) - 1; const b = parts.length === 3 ? Number(parts[2]) - 1 : a; gates.push({ op: parts[0], a, b });}const out: string[] = [];for (let t = 0; t < q; t++) { const sensors: Tri[] = lines[1 + g + t].trim().split(" ").map((w: string): Tri => (w === "?" ? null : w === "yes")); const result: Tri = evaluate(gates, sensors); const unknown: number[] = []; for (let i = 0; i < s; i++) if (sensors[i] === null) unknown.push(i); let count = 0; for (let mask = 0; mask < 1 << unknown.length; mask++) { unknown.forEach((i: number, j: number) => { sensors[i] = ((mask >> j) & 1) === 1; }); // j번째 비트 = j번째 고장 센서 if (evaluate(gates, sensors) === true) count++; } out.push((result === null ? "unknown" : result ? "yes" : "no") + " " + count);}console.log(out.join("\n"));
JavaMain.java · 80 行
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;public class Main { // 세 값 논리: Boolean.TRUE, Boolean.FALSE, null(모름). null을 boolean으로 풀면 NullPointerException이라 먼저 null인지 본다. static Boolean and3(Boolean a, Boolean b) { if ((a != null && !a) || (b != null && !b)) return false; if (a == null || b == null) return null; return true; } static Boolean or3(Boolean a, Boolean b) { if ((a != null && a) || (b != null && b)) return true; if (a == null || b == null) return null; return false; } static Boolean xor3(Boolean a, Boolean b) { if (a == null || b == null) return null; return a.booleanValue() != b.booleanValue(); } static Boolean not3(Boolean a) { return a == null ? null : !a; } static String[] op; static int[] ga, gb; // wires 앞쪽 s칸에 센서 값이 들어 있다. 게이트를 차례로 계산해 마지막 전선의 값을 돌려준다. static Boolean evaluate(Boolean[] wires, int s) { for (int i = 0; i < op.length; i++) { Boolean a = wires[ga[i]], b = wires[gb[i]]; Boolean r; switch (op[i]) { case "and": r = and3(a, b); break; case "or": r = or3(a, b); break; case "xor": r = xor3(a, b); break; default: r = not3(a); } wires[s + i] = r; } return wires[s + op.length - 1]; } public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); String[] head = in.readLine().trim().split(" "); int s = Integer.parseInt(head[0]), g = Integer.parseInt(head[1]), q = Integer.parseInt(head[2]); op = new String[g]; ga = new int[g]; gb = new int[g]; for (int i = 0; i < g; i++) { String[] parts = in.readLine().trim().split(" "); op[i] = parts[0]; ga[i] = Integer.parseInt(parts[1]) - 1; gb[i] = parts.length == 3 ? Integer.parseInt(parts[2]) - 1 : ga[i]; } StringBuilder out = new StringBuilder(); Boolean[] wires = new Boolean[s + g]; for (int t = 0; t < q; t++) { String[] words = in.readLine().trim().split(" "); int[] unknown = new int[s]; int u = 0; for (int i = 0; i < s; i++) { if (words[i].equals("?")) { wires[i] = null; unknown[u++] = i; } else wires[i] = words[i].equals("yes"); } Boolean result = evaluate(wires, s); int count = 0; for (int mask = 0; mask < (1 << u); mask++) { for (int j = 0; j < u; j++) wires[unknown[j]] = ((mask >> j) & 1) == 1; // j번째 비트 = j번째 고장 센서 if (Boolean.TRUE.equals(evaluate(wires, s))) count++; } out.append(result == null ? "unknown" : result ? "yes" : "no").append(' ').append(count).append('\n'); } System.out.print(out); }}
C#Main.cs · 66 行
using System;using System.Text;class Program{ static string[] op; static int[] ga, gb; // wires 앞쪽 s칸에 센서 값이 들어 있다. 게이트를 차례로 계산해 마지막 전선의 값을 돌려준다. // bool?의 &, |, ^, !는 null을 '모름'으로 다루는 세 값 논리 그대로다(false & null은 false, true | null은 true). static bool? Evaluate(bool?[] wires, int s) { for (int i = 0; i < op.Length; i++) { bool? a = wires[ga[i]], b = wires[gb[i]]; bool? r; switch (op[i]) { case "and": r = a & b; break; case "or": r = a | b; break; case "xor": r = a ^ b; break; default: r = !a; break; } wires[s + i] = r; } return wires[s + op.Length - 1]; } static void Main() { string[] head = Console.ReadLine().Trim().Split(' '); int s = int.Parse(head[0]), g = int.Parse(head[1]), q = int.Parse(head[2]); op = new string[g]; ga = new int[g]; gb = new int[g]; for (int i = 0; i < g; i++) { string[] parts = Console.ReadLine().Trim().Split(' '); op[i] = parts[0]; ga[i] = int.Parse(parts[1]) - 1; gb[i] = parts.Length == 3 ? int.Parse(parts[2]) - 1 : ga[i]; } var sb = new StringBuilder(); var wires = new bool?[s + g]; for (int t = 0; t < q; t++) { string[] words = Console.ReadLine().Trim().Split(' '); var unknown = new int[s]; int u = 0; for (int i = 0; i < s; i++) { if (words[i] == "?") { wires[i] = null; unknown[u++] = i; } else wires[i] = words[i] == "yes"; } bool? result = Evaluate(wires, s); int count = 0; for (int mask = 0; mask < (1 << u); mask++) { for (int j = 0; j < u; j++) wires[unknown[j]] = ((mask >> j) & 1) == 1; // j번째 비트 = j번째 고장 센서 if (Evaluate(wires, s) == true) count++; } sb.Append(result == null ? "unknown" : result == true ? "yes" : "no").Append(' ').Append(count).Append('\n'); } Console.Write(sb); }}
C++main.cpp · 81 行
#include <iostream>#include <optional>#include <string>#include <vector>using namespace std;using Tri = optional<bool>; // 비어 있으면 모름. if (x)는 '값이 있나'를 묻는 것이라 값은 *x로 꺼낸다Tri and3(Tri a, Tri b) { if ((a && !*a) || (b && !*b)) return false; // 한쪽이 거짓이면 다른 쪽을 몰라도 거짓 if (!a || !b) return nullopt; return true;}Tri or3(Tri a, Tri b) { if ((a && *a) || (b && *b)) return true; if (!a || !b) return nullopt; return false;}Tri xor3(Tri a, Tri b) { if (!a || !b) return nullopt; return *a != *b;}Tri not3(Tri a) { if (!a) return nullopt; return !*a;}struct Gate { string op; int a, b;};// wires 앞쪽 s칸에 센서 값이 들어 있다. 게이트를 차례로 계산해 마지막 전선의 값을 돌려준다.Tri evaluate(const vector<Gate>& gates, vector<Tri>& wires, int s) { for (size_t i = 0; i < gates.size(); i++) { const Gate& gate = gates[i]; Tri a = wires[gate.a], b = wires[gate.b]; if (gate.op == "and") wires[s + i] = and3(a, b); else if (gate.op == "or") wires[s + i] = or3(a, b); else if (gate.op == "xor") wires[s + i] = xor3(a, b); else wires[s + i] = not3(a); } return wires.back();}int main() { int s, g, q; cin >> s >> g >> q; vector<Gate> gates(g); for (Gate& gate : gates) { cin >> gate.op >> gate.a; gate.a--; gate.b = gate.a; if (gate.op != "not") { cin >> gate.b; gate.b--; } } vector<Tri> wires(s + g); for (int t = 0; t < q; t++) { vector<int> unknown; for (int i = 0; i < s; i++) { string word; cin >> word; if (word == "?") { wires[i] = nullopt; unknown.push_back(i); } else wires[i] = word == "yes"; } Tri result = evaluate(gates, wires, s); int count = 0; int u = (int)unknown.size(); for (int mask = 0; mask < (1 << u); mask++) { for (int j = 0; j < u; j++) wires[unknown[j]] = ((mask >> j) & 1) == 1; // j번째 비트 = j번째 고장 센서 if (evaluate(gates, wires, s) == Tri(true)) count++; } cout << (!result ? "unknown" : *result ? "yes" : "no") << " " << count << "\n"; } return 0;}
Cmain.c · 79 行
#include <stdio.h>#include <string.h>/* 세 값 논리: C의 bool은 두 값뿐이라 열거형을 따로 만든다 */typedef enum { NO = 0, YES = 1, UNKNOWN = 2 } Tri;static Tri and3(Tri a, Tri b) { if (a == NO || b == NO) return NO; /* 한쪽이 거짓이면 다른 쪽을 몰라도 거짓 */ if (a == UNKNOWN || b == UNKNOWN) return UNKNOWN; return YES;}static Tri or3(Tri a, Tri b) { if (a == YES || b == YES) return YES; if (a == UNKNOWN || b == UNKNOWN) return UNKNOWN; return NO;}static Tri xor3(Tri a, Tri b) { if (a == UNKNOWN || b == UNKNOWN) return UNKNOWN; return a != b ? YES : NO;}static Tri not3(Tri a) { if (a == UNKNOWN) return UNKNOWN; return a == YES ? NO : YES;}static int s, g;static char op[100];static int ga[100], gb[100];static Tri wires[120];/* wires 앞쪽 s칸에 센서 값이 들어 있다. 게이트를 차례로 계산해 마지막 전선의 값을 돌려준다. */static Tri evaluate(void) { for (int i = 0; i < g; i++) { Tri a = wires[ga[i]], b = wires[gb[i]]; switch (op[i]) { case 'a': wires[s + i] = and3(a, b); break; case 'o': wires[s + i] = or3(a, b); break; case 'x': wires[s + i] = xor3(a, b); break; default: wires[s + i] = not3(a); } } return wires[s + g - 1];}int main(void) { int q; if (scanf("%d %d %d", &s, &g, &q) != 3) return 0; for (int i = 0; i < g; i++) { char name[8]; if (scanf("%7s %d", name, &ga[i]) != 2) return 0; op[i] = name[0]; ga[i]--; gb[i] = ga[i]; if (strcmp(name, "not") != 0) { if (scanf("%d", &gb[i]) != 1) return 0; gb[i]--; } } for (int t = 0; t < q; t++) { int unknown[20], u = 0; for (int i = 0; i < s; i++) { char word[8]; if (scanf("%7s", word) != 1) return 0; if (word[0] == '?') { wires[i] = UNKNOWN; unknown[u++] = i; } else wires[i] = word[0] == 'y' ? YES : NO; } Tri result = evaluate(); int count = 0; for (int mask = 0; mask < (1 << u); mask++) { for (int j = 0; j < u; j++) wires[unknown[j]] = ((mask >> j) & 1) ? YES : NO; /* j번째 비트 = j번째 고장 센서 */ if (evaluate() == YES) count++; } printf("%s %d\n", result == UNKNOWN ? "unknown" : result == YES ? "yes" : "no", count); } return 0;}
Craykonmain.cray · 143 行
// 세 값 논리: 참, 거짓, 빈값(모름)그리고3(a, b){ もし (a == 偽 || b == 偽) { 返す 偽; // 한쪽이 거짓이면 다른 쪽을 몰라도 거짓 } もし (a == なし || b == なし) { 返す なし; } 返す 真;}또는3(a, b){ もし (a == 真 || b == 真) { 返す 真; } もし (a == なし || b == なし) { 返す なし; } 返す 偽;}다름3(a, b){ もし (a == なし || b == なし) { 返す なし; } 返す a != b;}아님3(a){ もし (a == なし) { 返す なし; } 返す !a;}// wires 앞쪽 s칸에 센서 값이 들어 있다. 게이트를 차례로 계산해 마지막 전선의 값을 돌려준다.계산(ops, ga, gb, wires, s){ g = ops.個数; 繰り返す (i = 0; i < g; i++) { a = wires[ga[i]]; b = wires[gb[i]]; もし (ops[i] == "and") { wires[s + i] = 그리고3(a, b); } でなければ もし (ops[i] == "or") { wires[s + i] = 또는3(a, b); } でなければ もし (ops[i] == "xor") { wires[s + i] = 다름3(a, b); } でなければ { wires[s + i] = 아님3(a); } } 返す wires[s + g - 1];}head = コンソール.数読み();s = head[0];g = head[1];q = head[2];ops = [];ga = [];gb = [];繰り返す (i = 0; i < g; i++){ parts = コンソール.行読み().空白除去().分ける(" "); ops.追加(parts[0]); ga.追加(parts[1].数に() - 1); もし (parts.個数 == 3) { gb.追加(parts[2].数に() - 1); } でなければ { gb.追加(parts[1].数に() - 1); }}wires = 新リスト(s + g, なし);繰り返す (t = 0; t < q; t++){ words = コンソール.行読み().空白除去().分ける(" "); unknown = []; 繰り返す (i = 0; i < s; i++) { もし (words[i] == "?") { wires[i] = なし; unknown.追加(i); } でなければ { wires[i] = words[i] == "yes"; } } result = 계산(ops, ga, gb, wires, s); u = unknown.個数; total = 1; 繰り返す (j = 0; j < u; j++) { total = total * 2; } count = 0; 繰り返す (mask = 0; mask < total; mask++) { rest = mask; 繰り返す (j = 0; j < u; j++) { wires[unknown[j]] = rest % 2 == 1; // j번째 비트 = j번째 고장 센서 rest = 数学.商(rest, 2); } もし (계산(ops, ga, gb, wires, s) == 真) { count = count + 1; } } name = "no"; もし (result == なし) { name = "unknown"; } でなければ もし (result) { name = "yes"; } コンソール.書く(name + " " + count);}