2769번: 논리식 비교

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
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번부터 시작한다.

예제 입력 1

3
a ^b&(b|a)~b^ a
a^b&(b|a)(a^(b&(b|a)))
~~~~z~~z

예제 출력 1

Data set 1: Different
Data set 2: Equivalent
Data set 3: Equivalent

W3sicHJvYmxlbV9pZCI6IjI3NjkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIxN2NcdWI5YWNcdWMyZGQgXHViZTQ0XHVhZDUwIiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHRcdWI0NTAgXHViMTdjXHViOWFjXHVjMmRkXHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YjQ1MCBcdWIxN2NcdWI5YWNcdWMyZGRcdWM3NzQgXHViMTdjXHViOWFjXHVjODAxXHVjNzNjXHViODVjIFx1YWMxOVx1Yzc0MFx1YzljMCBcdWM1NDRcdWIyY2NcdWM5YzBcdWI5N2MgXHVkMzEwXHViY2M0XHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IFRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWQ1NWMgXHVjOTA0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWFjZTAsIFx1YWMxOVx1Yzc0MFx1YzljMCBcdWJlNDRcdWFkNTBcdWQ1NzRcdWM1N2MgXHVkNTYwIFx1YjQ1MCBcdWIxN2NcdWI5YWNcdWMyZGRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0IFx1YzJkZFx1Yzc0MCAyNlx1YWMxY1x1Yzc1OCBcdWJjYzBcdWMyMTggYS16LCBcdWM3NzRcdWQ1NmQgXHVjNWYwXHVjMGIwXHVjNzkwIHwsICZhbXA7LCBeLChPUiwgQU5ELCBYT1IpLCBcdWIyZThcdWQ1NmQgXHVjNWYwXHVjMGIwXHVjNzkwIH4oTk9UKSwgXHVhZDA0XHVkNjM4XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuJm5ic3A7PFwvcD5cclxuPHA+XHJcblx0XHVjNzc0XHVjNjc4XHVjNzU4IFx1YjJlNFx1Yjk3OCBcdWJiMzhcdWM3OTBcdWIyOTQgXHViYjM0XHVjMmRjXHVkNTc0XHVjNTdjIFx1ZDU1OFx1YWNlMCwgQ1x1YzViOFx1YzViNCBcdWM1ZjBcdWMwYjBcdWM3OTAgXHVjNmIwXHVjMTIwXHVjMjFjXHVjNzA0XHViOTdjIFx1YjUzMFx1Yjk3OFx1YjJlNC4gXHViNDUwIFx1Yzc4NVx1YjgyNVx1YzJkZFx1Yzc0MCBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjNzg4XHVjOWMwIFx1YzU0YVx1YjJlNC4gXHViNDUwIFx1YjE3Y1x1YjlhY1x1YzJkZFx1Yzc0NCBcdWFkNmNcdWJkODRcdWQ1NThcdWIyOTQgXHVhYzgzXHViM2M0IFx1YWQ2Y1x1ZDYwNFx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1Yzc3NFx1YjdlY1x1ZDU1YyBcdWJiMzhcdWM4MWNcdWI5N2MgXHVkNDgwIFx1YjU0Y1x1YjI5NCBcdWJjZjRcdWQxYjUgXHVhYzAxIFx1YzJkZFx1Yzc0NCBcdWM4MTVcdWFkZGNcdWQ2NTQgXHVkNTVjIFx1YjRhNCwgXHViNDUwIFx1YzgxNVx1YWRkY1x1ZDY1NCBcdWMyZGRcdWM3NzQgXHVhYzE5XHVjNzQwXHVjOWMwIFx1ZDMxMFx1YmNjNFx1ZDU1OFx1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NDQgXHVjMGFjXHVjNmE5XHVkNTVjXHViMmU0LiBcdWFjMDFcdWFjMDFcdWM3NTggXHViMTdjXHViOWFjXHVjMmRkXHVjNzQwIDEwXHVhYzFjIFx1Yzc3NFx1ZDU1OFx1Yzc1OCBcdWJjYzBcdWMyMTgsIDEwMFx1YWMxYyBcdWM3NzRcdWQ1NThcdWM3NTggXHVjNWYwXHVjMGIwXHVjNzkwXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHJcblx0XHVhYzAxXHVhYzAxXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWI0NTAgXHViMTdjXHViOWFjXHVjMmRkXHVjNzc0IFx1YWMxOVx1YjJlNFx1YmE3NCw8XC9wPlxyXG48cD5cclxuXHREYXRhIHNldCBOOiBFcXVpdmFsZW50PFwvcD5cclxuPHA+XHJcblx0XHViMmU0XHViOTc0XHViMmU0XHViYTc0PFwvcD5cclxuPHA+XHJcblx0RGF0YSBzZXQgTjogRGlmZmVyZW50PFwvcD5cclxuPHA+XHJcblx0XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gTlx1Yzc0MCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0IFx1YmM4OFx1ZDYzOFx1Yzc3NFx1YWNlMCwgMVx1YmM4OFx1YmQ4MFx1ZDEzMCBcdWMyZGNcdWM3OTFcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMjc2OSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ikl0XHUyMDE5cyBMb2dpY2FsIiwiZGVzY3JpcHRpb24iOiI8cD5BdCB0aGUgVW5pdmVyc2l0eSBvZiBLZW50dWNreSwgdGhleSBidWlsZCBhIGxvdCBvZiBoaWdoLXBlcmZvcm1hbmNlIGNvbXB1dGVyIGhhcmR3YXJlIGFuZCBzb2Z0d2FyZSwgb2Z0ZW4gdXNpbmcgb25lIHN1cGVyY29tcHV0ZXIgdG8gZGVzaWduIHRoZSBuZXh0LiBPbmUgb2YgdGhlIG1vc3QgZnVuZGFtZW50YWwgY29tcHV0ZXIgZGVzaWduIHByb2JsZW1zIGlzIGxvZ2ljIG9wdGltaXphdGlvbjogbWFraW5nIHN1cmUgdGhhdCB0aGUgb3B0aW1pemVkIGxvZ2ljIHN0aWxsIGNvbXB1dGVzIHRoZSBzYW1lIGZ1bmN0aW9uIGFzIHRoZSBvcmlnaW5hbCBkZXNpZ24uPFwvcD5cclxuXHJcbjxwPkZvciB0aGlzIHByb2JsZW0sIHlvdXIgcHJvZ3JhbSB3aWxsIGJlIGdpdmVuIHR3byBsb2dpYyBleHByZXNzaW9ucyB0byBjb21wYXJlIGZvciBsb2dpY2FsIGVxdWl2YWxlbmNlLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0IGNvbnNpc3RzIG9mIGEgcG9zaXRpdmUgaW50ZWdlciBuLCB3aGljaCBpcyB0aGUgbnVtYmVyIG9mIGRhdGFzZXRzIChsaW5lcykgdGhhdCBmb2xsb3cuIEVhY2ggZGF0YXNldCBjb25zaXN0cyBvZiBhIHNpbmdsZSBsaW5lIGNvbnRhaW5pbmcgdGhlIHR3byBpbnB1dCBleHByZXNzaW9ucyB0byBiZSB0ZXN0ZWQuIFRoZSBpbnB1dCBleHByZXNzaW9ucyBjb25zaXN0IG9mIGFueSBvZiAyNiB2YXJpYWJsZXMgbmFtZWQgYS16LCB0aGUgYmluYXJ5IG9wZXJhdG9ycyB8LCAmYW1wOywgXiwgKE9SLCBBTkQgYW5kIFhPUiByZXNwZWN0aXZlbHkpLCB0aGUgdW5hcnkgfiAoTk9UKSwgYW5kIHBhcmVudGhlc2lzLiBUaGUgZXhwcmVzc2lvbnMgc2hvdWxkIGJlIGV2YWx1YXRlZCBpZ25vcmluZyBhbGwgb3RoZXIgY2hhcmFjdGVycyBhbmQgd2l0aCBvcGVyYXRvciBwcmVjZWRlbmNlIGFzIGluIHRoZSBDIGxhbmd1YWdlIChwYXJlbnRoZXNpcywgfiwgJmFtcDssIF4sIHwpLiBUaGUgdHdvIGV4cHJlc3Npb25zIHdpbGwgYmUgaW5wdXQgaW4gc2VxdWVuY2UgYW5kIGl0IGlzIHVwIHRvIHlvdXIgcHJvZ3JhbSB0byBkZXRlcm1pbmUgd2hlcmUgb25lIGV4cHJlc3Npb24gZW5kcyBhbmQgdGhlIG5leHQgYmVnaW5zLjxcL3A+XHJcblxyXG48cD5Nb3N0IGxvZ2ljIG1hbmlwdWxhdGlvbiBwcm9ncmFtcyB3b3VsZCBjb252ZXJ0IGVhY2ggZXhwcmVzc2lvbiBpbnRvIGEgbm9ybWFsIGZvcm0gYW5kIGNoZWNrIGlmIHRoZSB0d28gbm9ybWFsaXplZCBleHByZXNzaW9ucyBhcmUgaWRlbnRpY2FsLiBGb3J0dW5hdGVseSBmb3IgeW91LCBlYWNoIGV4cHJlc3Npb24gd2lsbCBjb25zaXN0IG9mIG5vIG1vcmUgdGhhbiAxMDAgb3BlcmF0aW9ucyB1c2luZyBubyBtb3JlIHRoYW4gMTAgZGlmZmVyZW50IHZhcmlhYmxlcy4gRm9yIHRoYXQgbWFueSBjYXNlcywgeW91IGNhbiB0ZXN0IGZvciBlcXVpdmFsZW5jZSBieSBzaW1wbHkgZXZhbHVhdGluZyB0aGUgdHdvIGlucHV0IGV4cHJlc3Npb25zIGZvciBhbGwgcG9zc2libGUgaW5wdXRzIGFuZCBjb21wYXJpbmcgdGhlIHJlc3VsdHMuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggZGF0YSBzZXQsIHByaW50OjxcL3A+XHJcblxyXG48cD5EYXRhIHNldCBOOiBFcXVpdmFsZW50PFwvcD5cclxuXHJcbjxwPmlmIHRoZSBleHByZXNzaW9ucyBwcm9kdWNlIHRoZSBzYW1lIHJlc3VsdCwgb3I6PFwvcD5cclxuXHJcbjxwPkRhdGEgc2V0IE46IERpZmZlcmVudDxcL3A+XHJcblxyXG48cD5pZiB0aGV5IHByb2R1Y2UgZGlmZmVyZW50IHJlc3VsdHMuIE9mIGNvdXJzZSBOIHNob3VsZCBiZSByZXBsYWNlZCBieSB0aGUgZGF0YSBzZXQgbnVtYmVyLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

ICPC > Regionals > North America > Greater New York Region > 2003 Greater New York Programming Contest E번

문제를 번역한 사람: baekjoon

문제

문제

출처

ICPC

2769번 - 논리식 비교 다국어

문제

입력

출력

제한

예제 입력 1

예제 출력 1

힌트

출처

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

문제

문제

출처

ICPC

2769번 - 논리식 비교 다국어

문제

입력

출력

제한

예제 입력 1 복사

예제 출력 1 복사

힌트

출처

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

예제 입력 1

예제 출력 1