A warehouse alarm combines the values of s sensors through g gates to decide whether to ring.
The wires that carry values are numbered: the value of sensor i is on wire i, and the result of the i-th gate is on wire s + i.
The first line has s, g and the number of readings q, and the next g lines have the gates in order.
A gate line is one of "and a b", "or a b", "xor a b" and "not a", where a and b are wires with smaller numbers than the gate's result wire.
a and b may be the same wire.
The result of the last gate is the alarm.
The next q lines have one reading each, and a reading is the s values of sensors 1 to s.
A sensor value is yes or no, but a broken sensor's value cannot be known and is written as ?.
For each reading, find two things.
The first is the verdict: the value of the alarm when the gates are computed in order with a third value, 'unknown', for the values that are not known.
and is no if at least one of the two values is no, otherwise unknown if at least one is unknown, and yes in the remaining case.
or is yes if at least one of the two values is yes, otherwise unknown if at least one is unknown, and no in the remaining case.
xor is unknown if at least one value is unknown, otherwise yes if the two values differ and no if they are equal.
not is unknown for unknown, no for yes, and yes for no.
The verdict is unknown if the alarm value is unknown, and yes or no otherwise.
The second is the count: among all ways of putting yes or no into every broken sensor, the number of ways that make the alarm yes.
With u broken sensors there are 2^u ways, and with no broken sensor there is one way, the values as given.
For each reading, print the verdict and the count on one line, separated by a single space.
Because each gate is computed on its own, the count can be 0 or 2^u even when the verdict is unknown.
Input
1 ≤ s ≤ 20, 1 ≤ g ≤ 100, 1 ≤ q ≤ 20. For the i-th gate, a and b are between 1 and s + i − 1. A reading has at most 8 ?. Values are separated by single spaces
Output
One line per reading: the verdict (yes, no, unknown) and the count
Example 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
Example 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
Error List00F8 ↓ · ⇧F8 ↑
Input (stdin)
When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).
$ Ready
Open this on a computer to write and run code. On mobile you can read the problem and the solutions.
In other languagesShow solutions by language · 8 languages
Compare where each language keeps three values: true, false and 'unknown'. C# bool? follows exactly the rules of this problem. a & b, a | b, a ^ b and !a treat null as unknown, so null & false is false, null | true is true and !null is null. But a && b cannot be used on bool? and is a compile error (CS0019), and in a condition you ask x == true. The other languages write the functions by hand. Unknown is None in Python, null in JS/TS (the TS type is boolean | null), a null Boolean in Java, an empty std::optional<bool> in C++, null in Craykon, and C makes enum { NO, YES, UNKNOWN }. Trap one: with the language's own and/or the answer depends on what is on the left. Python None and False is None while False and None is False, and False or None is None. JS null && false is null, and Craykon null && false is null too. In the second reading of the first example ? and no fails to become no and the verdict comes out unknown. Trap two: not. Python not None, JS !null and Craykon !null are all true, and if C keeps unknown as 2, !2 is 0. Trap three: checking 'unknown if anything is unknown' first makes ? and no unknown. and looks for a no first, or looks for a yes first. Trap four: writing xor as just a !== b loses the unknown in JS, because null !== false is true (first reading of the second example). Trap five: in Java with Boolean a = null, if (!a) stops with a NullPointerException while taking the value out. Ask whether it is null first. Trap six: using C++ std::optional<bool> as if (a || b) asks whether a value is present, not what the value is, so it is true even when false is inside. Take the value out with *a. Trap seven: when counting with a number mask from 0 to 2^u − 1, bit j is the value of the j-th broken sensor. Looking at mask >> i with the sensor number i is wrong when the broken sensors have high numbers (third reading of the first example). The verdict and the count measure different things. x or not x in the second example is yes whatever x is, but computing gate by gate gives unknown.
Pythonmain.py · 71 lines
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 lines
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 lines
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 lines
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 lines
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 lines
#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 lines
#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 lines
// 세 값 논리: 참, 거짓, 빈값(모름)그리고3(a, b){ if (a == false || b == false) { return false; // 한쪽이 거짓이면 다른 쪽을 몰라도 거짓 } if (a == null || b == null) { return null; } return true;}또는3(a, b){ if (a == true || b == true) { return true; } if (a == null || b == null) { return null; } return false;}다름3(a, b){ if (a == null || b == null) { return null; } return a != b;}아님3(a){ if (a == null) { return null; } return !a;}// wires 앞쪽 s칸에 센서 값이 들어 있다. 게이트를 차례로 계산해 마지막 전선의 값을 돌려준다.계산(ops, ga, gb, wires, s){ g = ops.Count; for (i = 0; i < g; i++) { a = wires[ga[i]]; b = wires[gb[i]]; if (ops[i] == "and") { wires[s + i] = 그리고3(a, b); } else if (ops[i] == "or") { wires[s + i] = 또는3(a, b); } else if (ops[i] == "xor") { wires[s + i] = 다름3(a, b); } else { wires[s + i] = 아님3(a); } } return wires[s + g - 1];}head = Console.ReadNumbers();s = head[0];g = head[1];q = head[2];ops = [];ga = [];gb = [];for (i = 0; i < g; i++){ parts = Console.ReadLine().Trim().Split(" "); ops.Add(parts[0]); ga.Add(parts[1].ToNumber() - 1); if (parts.Count == 3) { gb.Add(parts[2].ToNumber() - 1); } else { gb.Add(parts[1].ToNumber() - 1); }}wires = NewList(s + g, null);for (t = 0; t < q; t++){ words = Console.ReadLine().Trim().Split(" "); unknown = []; for (i = 0; i < s; i++) { if (words[i] == "?") { wires[i] = null; unknown.Add(i); } else { wires[i] = words[i] == "yes"; } } result = 계산(ops, ga, gb, wires, s); u = unknown.Count; total = 1; for (j = 0; j < u; j++) { total = total * 2; } count = 0; for (mask = 0; mask < total; mask++) { rest = mask; for (j = 0; j < u; j++) { wires[unknown[j]] = rest % 2 == 1; // j번째 비트 = j번째 고장 센서 rest = Mathf.Quot(rest, 2); } if (계산(ops, ga, gb, wires, s) == true) { count = count + 1; } } name = "no"; if (result == null) { name = "unknown"; } else if (result) { name = "yes"; } Console.WriteLine(name + " " + count);}