4882번 - 정규형 다국어

시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB238878140.909%

문제

모든 불리언 식은 Disjunctive Normal Form(DNF)나 Conjunctive Normal Form(CNF)로 나타낼 수 있다. DNF는 하나 또는 그 이상의 CNF식을 OR로 연결한 식이고, CNF는 DNF식을 AND로 연결한 식이다.

AND/OR 트리는 DNF나 CNF 불리언 식을 트리와 같은 형태로 표현한 것이다. DNF나 CNF는 서로를 부분식으로 포함하기 때문에, 서브 트리의 레벨만 알면 그 서브 트리가 AND트리인지 OR트리인지를 알 수 있다.

오른쪽 그림은 (A∨(B∧C))∧(D∨E)를 트리로 나타낸 것이다. 레벨 1(가장 위)과 3은 AND트리이다.

AND/OR 트리가 주어졌을 때, 식을 계산하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 32,000글자를 넘지 않는다.

(E1 E2 ... En)

항상 n > 0을 만족하고, Ei가 T인 경우에는 true, F인 경우에는 false이다. 부분식도 이와 같은 형식으로 주어진다.

가장 낮은 레벨에 있는 트리는 AND 트리이다. 입력의 마지막 줄에는 ()가 주어진다.

출력

각 테스트 케이스에 대해서, 다음을 출력한다.

k. E

k는 테스트 케이스의 번호이고, E는 입력으로 주어진 식의 값 true 또는 false이다.

예제 입력 1 

((F(TF))(TF))
(TFT)
((TFT)T)
()

예제 출력 1 

1. false
2. false
3. true
W3sicHJvYmxlbV9pZCI6IjQ4ODIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM4MTVcdWFkZGNcdWQ2MTUiLCJkZXNjcmlwdGlvbiI6IjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvYW5kb3J0cmVlLnBuZ1wiIHN0eWxlPVwiZmxvYXQ6cmlnaHQ7IGhlaWdodDoxNzJweDsgd2lkdGg6MTY0cHhcIiBcLz5cdWJhYThcdWI0ZTAgXHViZDg4XHViOWFjXHVjNWI4IFx1YzJkZFx1Yzc0MCBEaXNqdW5jdGl2ZSBOb3JtYWwgRm9ybShETkYpXHViMDk4IENvbmp1bmN0aXZlIE5vcm1hbCBGb3JtKENORilcdWI4NWMgXHViMDk4XHVkMGMwXHViMGJjIFx1YzIxOCBcdWM3ODhcdWIyZTQuIERORlx1YjI5NCBcdWQ1NThcdWIwOTggXHViNjEwXHViMjk0IFx1YWRmOCBcdWM3NzRcdWMwYzFcdWM3NTggQ05GXHVjMmRkXHVjNzQ0IE9SXHViODVjIFx1YzVmMFx1YWNiMFx1ZDU1YyBcdWMyZGRcdWM3NzRcdWFjZTAsIENORlx1YjI5NCBETkZcdWMyZGRcdWM3NDQgQU5EXHViODVjIFx1YzVmMFx1YWNiMFx1ZDU1YyBcdWMyZGRcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPkFORFwvT1IgXHVkMmI4XHViOWFjXHViMjk0IERORlx1YjA5OCBDTkYgXHViZDg4XHViOWFjXHVjNWI4IFx1YzJkZFx1Yzc0NCBcdWQyYjhcdWI5YWNcdWM2NDAgXHVhYzE5XHVjNzQwIFx1ZDYxNVx1ZDBkY1x1Yjg1YyBcdWQ0NWNcdWQ2MDRcdWQ1NWMgXHVhYzgzXHVjNzc0XHViMmU0LiBETkZcdWIwOTggQ05GXHViMjk0IFx1YzExY1x1Yjg1Y1x1Yjk3YyBcdWJkODBcdWJkODRcdWMyZGRcdWM3M2NcdWI4NWMgXHVkM2VjXHVkNTY4XHVkNTU4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgXHVjMTFjXHViZTBjIFx1ZDJiOFx1YjlhY1x1Yzc1OCBcdWI4MDhcdWJjYThcdWI5Y2MgXHVjNTRjXHViYTc0IFx1YWRmOCBcdWMxMWNcdWJlMGMmbmJzcDtcdWQyYjhcdWI5YWNcdWFjMDAgQU5EXHVkMmI4XHViOWFjXHVjNzc4XHVjOWMwIE9SXHVkMmI4XHViOWFjXHVjNzc4XHVjOWMwXHViOTdjIFx1YzU0YyBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2MjRcdWI5NzhcdWNhYmQgXHVhZGY4XHViOWJjXHVjNzQwIChBJm9yOyhCJmFuZDtDKSkmYW5kOyhEJm9yO0UpXHViOTdjIFx1ZDJiOFx1YjlhY1x1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYjggXHVhYzgzXHVjNzc0XHViMmU0LiBcdWI4MDhcdWJjYTggMShcdWFjMDBcdWM3YTUgXHVjNzA0KVx1YWNmYyAzXHVjNzQwIEFORFx1ZDJiOFx1YjlhY1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+QU5EXC9PUiBcdWQyYjhcdWI5YWNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjMmRkXHVjNzQ0IFx1YWNjNFx1YzBiMFx1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWQ1NWMgXHVjOTA0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWFjZTAsIDMyLDAwMFx1YWUwMFx1Yzc5MFx1Yjk3YyBcdWIxMThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+XHJcblxyXG48cHJlPlxyXG4oRTxzdWI+MTxcL3N1Yj4gRTxzdWI+MjxcL3N1Yj4gLi4uIEU8c3ViPm48XC9zdWI+KTxcL3ByZT5cclxuXHJcbjxwPlx1ZDU2ZFx1YzBjMSBuICZndDsgMFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWFjZTAsIEU8c3ViPmk8XC9zdWI+XHVhYzAwIFRcdWM3NzggXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IHRydWUsIEZcdWM3NzggXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IGZhbHNlXHVjNzc0XHViMmU0LiBcdWJkODBcdWJkODRcdWMyZGRcdWIzYzQgXHVjNzc0XHVjNjQwIFx1YWMxOVx1Yzc0MCBcdWQ2MTVcdWMyZGRcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDBcdWM3YTUgXHViMGFlXHVjNzQwIFx1YjgwOFx1YmNhOFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVkMmI4XHViOWFjXHViMjk0IEFORCBcdWQyYjhcdWI5YWNcdWM3NzRcdWIyZTQuIFx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWI5YzhcdWM5YzBcdWI5YzkgXHVjOTA0XHVjNWQwXHViMjk0ICgpXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsIFx1YjJlNFx1Yzc0Y1x1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwcmU+XHJcbmsuIEU8XC9wcmU+XHJcblxyXG48cD5rXHViMjk0IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHViYzg4XHVkNjM4XHVjNzc0XHVhY2UwLCBFXHViMjk0IFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzQgXHVjMmRkXHVjNzU4IFx1YWMxMiB0cnVlIFx1YjYxMFx1YjI5NCBmYWxzZVx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiI0ODgyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTm9ybWFsaXplZCBGb3JtIiwiZGVzY3JpcHRpb24iOiI8cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2FuZG9ydHJlZS5wbmdcIiBzdHlsZT1cImZsb2F0OnJpZ2h0OyBoZWlnaHQ6MTcycHg7IHdpZHRoOjE2NHB4XCIgXC8+QXMgeW91IG1vc3QgcHJvYmFibHkga25vdywgYW55IGJvb2xlYW4gZXhwcmVzc2lvbiBjYW4gYmUgZXhwcmVzc2VkIGluIGVpdGhlciBhIGRpc2p1bmN0aXZlIG5vcm1hbCBmb3JtIG9yIGEgY29uanVuY3RpdmUgbm9ybWFsIGZvcm0uIEluIGEgZGlzanVuY3RpdmUgbm9ybWFsIGZvcm0sIGEgYm9vbGVhbiBleHByZXNzaW9uIGlzIHdyaXR0ZW4gYXMgYSBkaXNqdW5jdCAobG9naWNhbCBvcikgb2Ygb25lLW9yIG1vcmUgc3ViLWV4cHJlc3Npb25zIHdoZXJlIGVhY2ggb2YgdGhlc2Ugc3ViLWV4cHJlc3Npb25zIGlzIHdyaXR0ZW4gaW4gYSBjb25qdW5jdGl2ZSBub3JtYWwgZm9ybS4gU2ltaWxhcmx5LCBhbiBleHByZXNzaW9uIHdyaXR0ZW4gaW4gYSBjb25qdW5jdGl2ZSBub3JtYWwgZm9ybSBpcyBhIGNvbmp1bmN0IChsb2dpY2FsIGFuZCkgb2Ygc3ViLWV4cHJlc3Npb25zIGVhY2ggd3JpdHRlbiBpbiBhIGRpc2p1bmN0aXZlIG5vcm1hbCBmb3JtLjxcL3A+XHJcblxyXG48cD5BbiBBTkRcL09SIHRyZWUgaXMgYSB0cmVlLWxpa2UgZ3JhcGhpY2FsLXJlcHJlc2VudGF0aW9uIG9mIGJvb2xlYW4gZXhwcmVzc2lvbnMgd3JpdHRlbiBhcyBlaXRoZXIgY29uanVuY3RpdmUtIG9yIGRpc2p1bmN0aXZlLW5vcm1hbCBmb3JtLiBTaW5jZSB0aGUgc3ViLWV4cHJlc3Npb25zIG9mIGEgbm9ybWFsaXplZCBmb3JtIGFsdGVybmF0ZSBpbiBiZWluZyBlaXRoZXIgZGlzanVuY3RpdmUgb3IgY29uanVuY3RpdmUgZm9ybXMsIHlvdSZyc3F1bztkIGV4cGVjdCB0aGUgc3ViLXRyZWVzIG9uIGFuIEFORFwvT1IgdHJlZSB0byBhbHRlcm5hdGUgaW4gYmVpbmcgQU5ELSBvciBPUi0gdHJlZXMgZGVwZW5kaW5nIG9uIHRoZSBzdWItdHJlZSZyc3F1bztzIGRlcHRoLWxldmVsLiBUaGUgZXhhbXBsZSBvbiB0aGUgcmlnaHQgaWxsdXN0cmF0ZXMgdGhpcyBvYnNlcnZhdGlvbiBmb3IgdGhlIGJvb2xlYW4gZXhwcmVzc2lvbiZuYnNwOyhBJm9yOyhCJmFuZDtDKSkmYW5kOyhEJm9yO0UpIHdoZXJlIHRoZSB0cmVlcyBpbiB0aGUgMXN0ICh0b3AtbW9zdCkgYW5kIDNyZCBsZXZlbHMgYXJlIEFORC10cmVlcy48XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQgZXZhbHVhdGVzIGEgZ2l2ZW4gYW5kXC9vciB0cmVlLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+WW91ciBwcm9ncmFtIHdpbGwgYmUgdGVzdGVkIG9uIG9uZSBvciBtb3JlIHRlc3QgY2FzZXMuIEVhY2ggdGVzdCBjYXNlIGlzIHNwZWNpXHVmYjAxZWQgb24gZXhhY3RseSBvbmUgbGluZSAod2hpY2ggaXMgbm8gbG9uZ2VyIHRoYW4gMzIsMDAwIGNoYXJhY3RlcnMpIG9mIHRoZSBmb3JtOjxcL3A+XHJcblxyXG48cHJlPlxyXG4oRTxzdWI+MTxcL3N1Yj4gRTxzdWI+MjxcL3N1Yj4gLi4uIEU8c3ViPm48XC9zdWI+KTxcL3ByZT5cclxuXHJcbjxwPndoZXJlIG4gJmd0OyAwIGFuZCBFPHN1Yj5pPFwvc3ViPiBpcyBlaXRoZXIgVCBmb3IgdHJ1ZSwgRiBmb3IgZmFsc2UsIG9yIGEgc3ViLWV4cHJlc3Npb24gdXNpbmcgdGhlIHNhbWUgZm9ybWF0LjxcL3A+XHJcblxyXG48cD5UaGUgdHJlZXMgYXQgdGhlIGRlZXBlc3QgbGV2ZWwgYXJlIEFORC10cmVlcy4gVGhlIGxhc3QgdGVzdCBjYXNlIGlzIGZvbGxvd2VkIGJ5IGEgZHVtbXkgbGluZSBtYWRlIG9mICgpLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgcHJpbnQgdGhlIGZvbGxvd2luZyBsaW5lOjxcL3A+XHJcblxyXG48cHJlPmsuXHUwMDAyIEU8XC9wcmU+XHJcblxyXG48cD5XaGVyZSBrIGlzIHRoZSB0ZXN0IGNhc2UgbnVtYmVyIChzdGFydGluZyBhdCBvbmUsKSBhbmQgRSBpcyBlaXRoZXIgdHJ1ZSBvciBmYWxzZSBkZXBlbmRpbmcgb24gdGhlIHZhbHVlIG9mIHRoZSBleHByZXNzaW9uIGluIHRoYXQgdGVzdCBjYXNlLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

ICPC > Regionals > Africa and Arab > Arab Collegiate Programming Contest > 2010 Arab Collegiate Programming Contest C번

  • 문제를 번역한 사람: baekjoon
  • 어색한 표현을 찾은 사람: yukariko

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO

  • 사업자 등록 번호: 541-88-00682
  • 대표자명: 최백준
  • 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
  • 전화번호: 02-521-0487 (이메일로 연락 주세요)
  • 이메일: contacts@startlink.io
  • 통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)