시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 198 | 67 | 34 | 29.310% |
두 논리식이 주어졌을 때, 두 논리식이 논리적으로 같은지 아닌지를 판별하는 프로그램을 작성하시오.
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 같은지 비교해야 할 두 논리식이 주어진다. 입력으로 주어지는 식은 26개의 변수 a-z, 이항 연산자 |, &, ^,(OR, AND, XOR), 단항 연산자 ~(NOT), 괄호로 이루어져 있다.
이외의 다른 문자는 무시해야 하고, C언어 연산자 우선순위를 따른다. 두 입력식은 구분되어 있지 않다. 두 논리식을 구분하는 것도 구현해야 한다.
이러한 문제를 풀 때는 보통 각 식을 정규화 한 뒤, 두 정규화 식이 같은지 판별하는 방법을 사용한다. 각각의 논리식은 10개 이하의 변수, 100개 이하의 연산자로 이루어져 있다.
각각의 테스트 케이스에 대해서, 두 논리식이 같다면,
Data set N: Equivalent
다르다면
Data set N: Different
를 출력한다. N은 테스트 케이스 번호이고, 1번부터 시작한다.
3 a ^b&(b|a)~b^ a a^b&(b|a)(a^(b&(b|a))) ~~~~z~~z
Data set 1: Different Data set 2: Equivalent Data set 3: Equivalent
ICPC > Regionals > North America > Greater New York Region > 2003 Greater New York Programming Contest E번