창고의 경보 장치는 센서 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()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 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>, 크레이콘은 빈값에 담고, C는 enum { NO, YES, UNKNOWN }을 만들어요. 함정 하나: 언어의 and·or를 그대로 쓰면 왼쪽에 무엇이 왔느냐에 따라 답이 달라져요. Python None and False는 None인데 False and None은 False이고, False or None은 None이에요. JS null && false는 null, 크레이콘 빈값 && 거짓도 빈값이에요. 첫 예시의 둘째 측정에서 ? and no가 no가 되지 못해 판정이 unknown으로 나와요. 함정 둘: not이에요. Python not None, JS !null, 크레이콘 !빈값은 모두 참이고, 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);}