시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 50 | 20 | 16 | 47.059% |
논리식은 컴퓨터 프로그램에 자주 사용된다. 논리식은 다음으로 구성된다.
단항 연산자는 하나의 변수에 대해 동작하고, 이항 연산자는 두 개의 변수에 대해 동작한다. 자주 쓰이는 단항 연산자로 NOT이 있고, 자주 쓰이는 이항 연산자로 AND, OR, XOR, NAND, NOR 등이 있다.
논리 연산자는 '진리표'로써 정의할 수 있다. 이 진리표는 단항 연산자의 경우 1차원, 이항 연산자의 경우 2차원이다. 예를 들어, 다음 그림을 보자.
위쪽 여백과 왼쪽 여백 모두 첫 번째 피연산자가 false이고, 두 번째 피연산자가 true임에 주목하자.
논리식의 예시는 다음과 같다.
이 문제에서 논리식의 정확한 구조는 다음 문법으로 정의된다.
<expression> = <variable> | ( <expression> <operator> <expression> ) | ( <operator> <expression>) <variable> = <lowercase_letter> <operator> = <uppercase_letter> | <operator> <uppercase_letter>
(여기서 수직 막대 '|'는 'or'라고 발음하며, 문법을 정의할 때 사용하는 글자이다. 실제 식에서는 나타나지 않는다.) <lowercase_letter>와 <uppercase_letter>는 알파벳 대소문자이다.
어떤 경우에서는 모든 변수의 값이 정해지지 않아도 논리식을 계산할 수 있다. 위의 첫 번째 예시에서, y는 false이고, x와 z의 값은 모른다고 해 보자. 그러면 나머지 변수의 값이 무엇이든 해당 논리식은 항상 false로 계산됨을 알 수 있다. 반면, 같은 예시에서, x = true, y = true이고, z의 값은 모른다고 해보자. 그러면 z의 값을 알지 않고서는 논리식의 값을 결정할 수 없다.
입력은 하나 이상의 테스트 케이스로 이루어져 있다. 각 테스트 케이스마다 첫 줄에 100 이하의 음이 아닌 정수가 2개 주어지며, 각각 그 케이스에서 사용할 단항 연산자와 이항 연산자의 종류이다.
그 다음에는 아래 두 문단에서 설명하는 형식으로 각 연산자의 이름과 진리표 형태의 연산자 정의가 여러 줄에 걸쳐 주어진다. 모든 연산자의 이름은 20글자를 넘지 않으며, 서로 다르다.
우선 단항 연산자를 각각 2줄씩에 걸쳐 정의한다. 첫째 줄에는 연산자의 이름이 주어지고, 둘째 줄에는 두 개의 참/거짓 값이 주어지며, 이것이 그 연산자의 진리표가 된다. 피연산자의 순서는 위 그림에 주어진 것과 같이 false, true이다.
단항 연산자 다음에는 이항 연산자를 각각 3줄씩에 걸쳐 정의한다. 첫째 줄에는 연산자의 이름이 주어지고, 다음 두 줄에는 두 개씩의 참/거짓 값이 주어지며, 이것이 그 연산자의 진리표가 된다. 왼쪽 피연산자는 위 그림의 왼쪽 여백에, 오른쪽 피연산자는 위쪽 여백에 해당한다.
연산자를 모두 정의한 다음에는 위의 문법을 만족하는 유효한 논리식을 한 줄에 입력받는다. 변수와 연산자는 하나 이상의 띄어쓰기로 구분되어 있으며, 괄호로 묶인 식과 연산자 사이에는 띄어쓰기가 있을 수도 없을 수도 있다. 논리식에는 같은 변수가 두 번 이상 등장하지 않음이 보장된다. 논리식의 길이는 1 이상 500 이하이다.
논리식 다음에는 0개 이상의 변수의 값이 각각 한 줄로 주어진다. 각 줄은 아래 둘 중 하나의 형태이다.
<variable> true <variable> false
같은 변수는 두 번 이상 주어지지 않는다.
각 테스트 케이스의 끝에는 별표(*) 하나가 주어지며, 입력의 끝에는 음의 정수 두 개가 한 줄로 주어진다.
각 테스트 케이스마다 한 줄씩 케이스 번호를 표시하고, 그 뒤에 true, false, unknown 중 주어진 논리식에 알맞은 것을 문제에서 설명한 대로 출력한다.
출력 포맷은 예제 출력을 통해 확인할 수 있다.
1 2 NOT true false AND false false false true TWEEK true false true false (x AND (NOT(y TWEEK z))) x true y true * 1 1 MOCK true true NAND true true true false (x NAND (MOCK (y NAND z))) x false y false * 0 2 XOR false true true false FAKE true true false false ((p XOR q) FAKE r) p true q false * -1 -1
Case 1: unknown Case 2: true Case 3: false