仓库的警报装置把 s 个传感器的值用 g 个门组合起来，决定是否响警报。 传递值的电线有编号：i 号传感器的值在 i 号电线上，第 i 个门的结果在 s + i 号电线上。 第一行是 s、g 和测量次数 q，接下来 g 行依次给出各个门。 门的一行是 "and a b"、"or a b"、"xor a b"、"not a" 之一，a 和 b 是编号比这个门的结果电线小的电线。 a 和 b 可以是同一根电线。 最后一个门的结果就是警报。 接下来 q 行每行给出一次测量，一次测量是 1 号到 s 号传感器的 s 个值。 传感器的值是 yes 或 no，但坏掉的传感器的值无法知道，写作 ?。 对每次测量求两样东西。 第一样是判定：把不知道的值当作第三种值“未知”，依次计算各个门后得到的警报的值。 and：两个值中只要有一个是 no 就是 no，否则只要有一个未知就是未知，其余情况是 yes。 or：两个值中只要有一个是 yes 就是 yes，否则只要有一个未知就是未知，其余情况是 no。 xor：只要有一个未知就是未知，否则两个值不同是 yes，相同是 no。 not：未知还是未知，yes 变 no，no 变 yes。 警报的值是未知时判定为 unknown，否则是 yes 或 no。 第二样是个数：给每个坏掉的传感器填入 yes 或 no 的所有方法中，使警报为 yes 的方法数。 坏掉的传感器有 u 个时共有 2^u 种方法，没有坏掉的传感器时只有按给出的值这一种方法。 对每次测量，把判定和个数用一个空格隔开输出在一行。 因为每个门是单独计算的，所以判定是 unknown 时个数也可能是 0 或 2^u。
输入
1 ≤ s ≤ 20，1 ≤ g ≤ 100，1 ≤ q ≤ 20。 第 i 个门的 a、b 在 1 到 s + i − 1 之间。 一次测量中 ? 不超过 8 个。 值之间用一个空格隔开
输出
每次测量一行：判定(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 种语言题解
比较一下各语言把真、假再加上“未知”这三种值放在哪里。 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 }。 陷阱一：直接用语言自带的 and、or，答案会随左边是什么而变。 Python 的 None and False 是 None，而 False and None 是 False，False or None 是 None。 JS 的 null && false 是 null，Craykon 的 空 && 假 也是 空。 在第一个样例的第二次测量里，? and no 没能变成 no，判定就成了 unknown。 陷阱二：not。 Python not None、JS !null、Craykon !空 都是真；在 C 里把未知记作 2 的话，!2 是 0。 陷阱三：先判断“只要有未知就是未知”，? and no 就成了 unknown。 and 要先找 no，or 要先找 yes。 陷阱四：xor 只写成 a !== b 的话，JS 里 null !== false 是 true，未知就消失了(第二个样例的第一次测量)。 陷阱五：在 Java 里 Boolean a = null 时，if (!a) 会在取值时因 NullPointerException 停下。 要先问是不是 null。 陷阱六：把 C++ 的 std::optional<bool> 写成 if (a || b)，问的不是值而是“里面有没有值”，所以即使里面是 false 也为真。 值要用 *a 取出。 陷阱七：数个数时，在 0 到 2^u − 1 的数 mask 中，第 j 位是第 j 个坏传感器的值。 用传感器编号 i 去看 mask >> i，在坏传感器编号靠后时就会出错(第一个样例的第三次测量)。 判定和个数量的是不同的东西。 第二个样例的 x or not x 不管 x 是什么都是 yes，但逐个门计算得到的是 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);}