시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 44 34 26 74.286%

문제

3차 논리는 논리값이 "true", "false", "unknown"을 가지는 논리 체계이다. 이 체계에서는 "false"는 0의 값을 가지고, "unknown"은 1, "true"는 2의 값을 갖는다.

"-"을 단항 연산자, "*"와 "+"는 이항 연산자라고 하자. 이 연산자는 각각 NOT, AND, OR을 의미한다. 3차 논리에서 3개 연산자는 다음과 같이 정의되어 있다.

P, Q, R을 3차 논리값을 갖는 변수라고 하자. 이때, 식이 주어졌을 때, 식의 값을 2로 만드는 (P,Q,R)쌍의 개수를 구하는 프로그램을 작성하시오. 식은 다음 중 하나의 형태를 갖는다. (X와 Y는 식을 의미한다)

  • 상수: 0, 1, 2
  • 변수: P, Q, R
  • NOT: -X
  • AND: (X*Y)
  • OR: (X+Y)

AND와 OR은 항상 괄호로 둘러싸여 있다.

예를 들어, (P*Q)가 주어졌을 때, 식의 값을 2로 만드는 (P,Q,R)쌍은 (2,2,0), (2,2,1), (2,2,2) 3가지이다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 식을 나타낸다. 식은 0, 1, 2, P, Q, R, -, *, +, (, )로만 이루어져 있다.

식의 BNF형 문법은 다음과 같다.

<formula> ::= 0 | 1 | 2 | P | Q | R |
              -<formula> | (<formula>*<formula>) | (<formula>+<formula>)

        

입력은 80글자를 넘지 않는다. 마지막 줄에는 '.'이 주어진다.

출력

각 테스트 케이스에 대해서, 입력으로 주어진 식의 값을 2로 만드는 (P,Q,R) 쌍의 개수를 출력한다.

예제 입력 1

(P*Q)
(--R+(P*Q))
(P*-P)
2
1
(-1+(((---P+Q)*(--Q+---R))*(-R+-P)))
.

예제 출력 1

3
11
0
27
0
7
W3sicHJvYmxlbV9pZCI6IjQ5NzAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI1MTRcdWM5YzBcdWQxMzggXHVkNjhjXHViODVjIFx1YWMxY1x1Yjg2MCIsImRlc2NyaXB0aW9uIjoiPHA+M1x1Y2MyOCBcdWIxN2NcdWI5YWNcdWIyOTQgXHViMTdjXHViOWFjXHVhYzEyXHVjNzc0ICZxdW90O3RydWUmcXVvdDssICZxdW90O2ZhbHNlJnF1b3Q7LCAmcXVvdDt1bmtub3duJnF1b3Q7XHVjNzQ0IFx1YWMwMFx1YzljMFx1YjI5NCBcdWIxN2NcdWI5YWMgXHVjY2I0XHVhY2M0XHVjNzc0XHViMmU0LiBcdWM3NzQgXHVjY2I0XHVhY2M0XHVjNWQwXHVjMTFjXHViMjk0ICZxdW90O2ZhbHNlJnF1b3Q7XHViMjk0IDBcdWM3NTggXHVhYzEyXHVjNzQ0IFx1YWMwMFx1YzljMFx1YWNlMCwgJnF1b3Q7dW5rbm93biZxdW90O1x1Yzc0MCAxLCAmcXVvdDt0cnVlJnF1b3Q7XHViMjk0IDJcdWM3NTggXHVhYzEyXHVjNzQ0IFx1YWMxNlx1YjI5NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+JnF1b3Q7LSZxdW90O1x1Yzc0NCBcdWIyZThcdWQ1NmQgXHVjNWYwXHVjMGIwXHVjNzkwLCAmcXVvdDsqJnF1b3Q7XHVjNjQwICZxdW90OysmcXVvdDtcdWIyOTQgXHVjNzc0XHVkNTZkIFx1YzVmMFx1YzBiMFx1Yzc5MFx1Yjc3Y1x1YWNlMCBcdWQ1NThcdWM3OTAuIFx1Yzc3NCBcdWM1ZjBcdWMwYjBcdWM3OTBcdWIyOTQgXHVhYzAxXHVhYzAxIE5PVCwgQU5ELCBPUlx1Yzc0NCBcdWM3NThcdWJiZjhcdWQ1NWNcdWIyZTQuIDNcdWNjMjggXHViMTdjXHViOWFjXHVjNWQwXHVjMTFjIDNcdWFjMWMgXHVjNWYwXHVjMGIwXHVjNzkwXHViMjk0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NzQgXHVjODE1XHVjNzU4XHViNDE4XHVjNWI0IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC90di5wbmdcIiBzdHlsZT1cImhlaWdodDoxODdweDsgd2lkdGg6NDQ2cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+UCwgUSwgUlx1Yzc0NCAzXHVjYzI4IFx1YjE3Y1x1YjlhY1x1YWMxMlx1Yzc0NCBcdWFjMTZcdWIyOTQgXHViY2MwXHVjMjE4XHViNzdjXHVhY2UwIFx1ZDU1OFx1Yzc5MC4gXHVjNzc0XHViNTRjLCBcdWMyZGRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjMmRkXHVjNzU4IFx1YWMxMlx1Yzc0NCAyXHViODVjIFx1YjljY1x1YjRkY1x1YjI5NCAoUCxRLFIpXHVjMzBkXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4gXHVjMmRkXHVjNzQwIFx1YjJlNFx1Yzc0YyBcdWM5MTEgXHVkNTU4XHViMDk4XHVjNzU4IFx1ZDYxNVx1ZDBkY1x1Yjk3YyBcdWFjMTZcdWIyOTRcdWIyZTQuIChYXHVjNjQwIFlcdWIyOTQgXHVjMmRkXHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNCk8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWMwYzFcdWMyMTg6IDAsIDEsIDI8XC9saT5cclxuXHQ8bGk+XHViY2MwXHVjMjE4OiBQLCBRLCBSPFwvbGk+XHJcblx0PGxpPk5PVDogLVg8XC9saT5cclxuXHQ8bGk+QU5EOiAoWCpZKTxcL2xpPlxyXG5cdDxsaT5PUjogKFgrWSk8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5BTkRcdWM2NDAgT1JcdWM3NDAgXHVkNTZkXHVjMGMxIFx1YWQwNFx1ZDYzOFx1Yjg1YyBcdWI0NThcdWI3ZWNcdWMyZjhcdWM1ZWMgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCAoUCpRKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWMyZGRcdWM3NTggXHVhYzEyXHVjNzQ0IDJcdWI4NWMgXHViOWNjXHViNGRjXHViMjk0IChQLFEsUilcdWMzMGRcdWM3NDAgKDIsMiwwKSwgKDIsMiwxKSwgKDIsMiwyKSAzXHVhYzAwXHVjOWMwXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWQ1NWMgXHVjOTA0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWFjZTAsIFx1YzJkZFx1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuIFx1YzJkZFx1Yzc0MCAwLCAxLCAyLCBQLCBRLCBSLCAtLCAqLCArLCAoLCApXHViODVjXHViOWNjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzJkZFx1Yzc1OCBCTkZcdWQ2MTUgXHViYjM4XHViYzk1XHVjNzQwIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWIyZTQuPFwvcD5cclxuXHJcbjxwcmU+XHJcbiZsdDtmb3JtdWxhJmd0OyA6Oj0gMCB8IDEgfCAyIHwgUCB8IFEgfCBSIHxcclxuICAgICAgICAgICAgICAtJmx0O2Zvcm11bGEmZ3Q7IHwgKCZsdDtmb3JtdWxhJmd0OyombHQ7Zm9ybXVsYSZndDspIHwgKCZsdDtmb3JtdWxhJmd0OysmbHQ7Zm9ybXVsYSZndDspPFwvcHJlPlxyXG5cclxuPHA+Jm5ic3A7ICZuYnNwOyAmbmJzcDsgJm5ic3A7Jm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCA4MFx1YWUwMFx1Yzc5MFx1Yjk3YyBcdWIxMThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LiBcdWI5YzhcdWM5YzBcdWI5YzkgXHVjOTA0XHVjNWQwXHViMjk0ICYjMzk7LiYjMzk7XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzQgXHVjMmRkXHVjNzU4IFx1YWMxMlx1Yzc0NCAyXHViODVjIFx1YjljY1x1YjRkY1x1YjI5NCAoUCxRLFIpIFx1YzMwZFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjQ5NzAiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJIb3cgY2FuIEkgc2F0aXNmeSB0aGVlPyBMZXQgbWUgY291bnQgdGhlIHdheXMuLi4iLCJkZXNjcmlwdGlvbiI6IjxwPlRocmVlLXZhbHVlZCBsb2dpYyBpcyBhIGxvZ2ljIHN5c3RlbSB0aGF0IGhhcywgaW4gYWRkaXRpb24gdG8gJnF1b3Q7dHJ1ZSZxdW90OyBhbmQgJnF1b3Q7ZmFsc2UmcXVvdDssICZxdW90O3Vua25vd24mcXVvdDsgYXMgYSB2YWxpZCB2YWx1ZS4gSW4gdGhlIGZvbGxvd2luZywgbG9naWNhbCB2YWx1ZXMgJnF1b3Q7ZmFsc2UmcXVvdDssICZxdW90O3Vua25vd24mcXVvdDsgYW5kICZxdW90O3RydWUmcXVvdDsgYXJlIHJlcHJlc2VudGVkIGJ5IDAsIDEgYW5kIDIgcmVzcGVjdGl2ZWx5LjxcL3A+XHJcblxyXG48cD5MZXQgJnF1b3Q7LSZxdW90OyBiZSBhIHVuYXJ5IG9wZXJhdG9yIChpLmUuIGEgc3ltYm9sIHJlcHJlc2VudGluZyBvbmUgYXJndW1lbnQgZnVuY3Rpb24pIGFuZCBsZXQgYm90aCAmcXVvdDsqJnF1b3Q7IGFuZCAmcXVvdDsrJnF1b3Q7IGJlIGJpbmFyeSBvcGVyYXRvcnMgKGkuZS4gc3ltYm9scyByZXByZXNlbnRpbmcgdHdvIGFyZ3VtZW50IGZ1bmN0aW9ucykuIFRoZXNlIG9wZXJhdG9ycyByZXByZXNlbnQgbmVnYXRpb24gKE5PVCksIGNvbmp1bmN0aW9uIChBTkQpIGFuZCBkaXNqdW5jdGlvbiAoT1IpIHJlc3BlY3RpdmVseS4gVGhlc2Ugb3BlcmF0b3JzIGluIHRocmVlLXZhbHVlZCBsb2dpYyBjYW4gYmUgZGVmaW5lZCBpbiBUYWJsZSBDLTEuPFwvcD5cclxuXHJcbjxwPlRhYmxlIEMtMTogVHJ1dGggdGFibGVzIG9mIHRocmVlLXZhbHVlZCBsb2dpYyBvcGVyYXRvcnMmbmJzcDs8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC90di5wbmdcIiBzdHlsZT1cImhlaWdodDoxODdweDsgd2lkdGg6NDQ2cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+TGV0IFAsIFEgYW5kIFIgYmUgdmFyaWFibGVzIHJhbmdpbmcgb3ZlciB0aHJlZS12YWx1ZWQgbG9naWMgdmFsdWVzLiBGb3IgYSBnaXZlbiBmb3JtdWxhLCB5b3UgYXJlIGFza2VkIHRvIGFuc3dlciB0aGUgbnVtYmVyIG9mIHRyaXBsZXMgKFAsUSxSKSB0aGF0IHNhdGlzZnkgdGhlIGZvcm11bGEsIHRoYXQgaXMsIHRob3NlIHdoaWNoIG1ha2UgdGhlIHZhbHVlIG9mIHRoZSBnaXZlbiBmb3JtdWxhIDIuIEEgZm9ybXVsYSBpcyBvbmUgb2YgdGhlIGZvbGxvd2luZyBmb3JtIChYIGFuZCBZIHJlcHJlc2VudCBmb3JtdWxhcykuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+Q29uc3RhbnRzOiAwLCAxIG9yIDI8XC9saT5cclxuXHQ8bGk+VmFyaWFibGVzOiBQLCBRIG9yIFI8XC9saT5cclxuXHQ8bGk+TmVnYXRpb25zOiAtWDxcL2xpPlxyXG5cdDxsaT5Db25qdW5jdGlvbnM6IChYKlkpPFwvbGk+XHJcblx0PGxpPkRpc2p1bmN0aW9uczogKFgrWSk8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5Ob3RlIHRoYXQgY29uanVuY3Rpb25zIGFuZCBkaXNqdW5jdGlvbnMgb2YgdHdvIGZvcm11bGFzIGFyZSBhbHdheXMgcGFyZW50aGVzaXplZC48XC9wPlxyXG5cclxuPHA+Rm9yIGV4YW1wbGUsIHdoZW4gZm9ybXVsYSAoUCpRKSBpcyBnaXZlbiBhcyBhbiBpbnB1dCwgdGhlIHZhbHVlIG9mIHRoaXMgZm9ybXVsYSBpcyAyIHdoZW4gYW5kIG9ubHkgd2hlbiAoUCxRLFIpIGlzICgyLDIsMCksICgyLDIsMSkgb3IgKDIsMiwyKS4gVGhlcmVmb3JlLCB5b3Ugc2hvdWxkIG91dHB1dCAzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGNvbnNpc3RzIG9mIG9uZSBvciBtb3JlIGxpbmVzLiBFYWNoIGxpbmUgY29udGFpbnMgYSBmb3JtdWxhLiBBIGZvcm11bGEgaXMgYSBzdHJpbmcgd2hpY2ggY29uc2lzdHMgb2YgMCwgMSwgMiwgUCwgUSwgUiwgLSwgKiwgKywgKCwgKS4gT3RoZXIgY2hhcmFjdGVycyBzdWNoIGFzIHNwYWNlcyBhcmUgbm90IGNvbnRhaW5lZC4gVGhlIGdyYW1tYXIgb2YgZm9ybXVsYXMgaXMgZ2l2ZW4gYnkgdGhlIGZvbGxvd2luZyBCTkYuPFwvcD5cclxuXHJcbjxwcmU+XHJcbiZsdDtmb3JtdWxhJmd0OyA6Oj0gMCB8IDEgfCAyIHwgUCB8IFEgfCBSIHxcclxuICAgICAgICAgICAgICAtJmx0O2Zvcm11bGEmZ3Q7IHwgKCZsdDtmb3JtdWxhJmd0OyombHQ7Zm9ybXVsYSZndDspIHwgKCZsdDtmb3JtdWxhJmd0OysmbHQ7Zm9ybXVsYSZndDspPFwvcHJlPlxyXG5cclxuPHA+QWxsIHRoZSBmb3JtdWxhcyBvYmV5IHRoaXMgc3ludGF4IGFuZCB0aHVzIHlvdSBkbyBub3QgaGF2ZSB0byBjYXJlIGFib3V0IGdyYW1tYXRpY2FsIGVycm9ycy4gSW5wdXQgbGluZXMgbmV2ZXIgZXhjZWVkIDgwIGNoYXJhY3RlcnMuPFwvcD5cclxuXHJcbjxwPkZpbmFsbHksIGEgbGluZSB3aGljaCBjb250YWlucyBvbmx5IGEgJnF1b3Q7LiZxdW90OyAocGVyaW9kKSBjb21lcywgaW5kaWNhdGluZyB0aGUgZW5kIG9mIHRoZSBpbnB1dDxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPllvdSBzaG91bGQgYW5zd2VyIHRoZSBudW1iZXIgKGluIGRlY2ltYWwpIG9mIHRyaXBsZXMgKFAsUSxSKSB0aGF0IG1ha2UgdGhlIHZhbHVlIG9mIHRoZSBnaXZlbiBmb3JtdWxhIDIuIE9uZSBsaW5lIGNvbnRhaW5pbmcgdGhlIG51bWJlciBzaG91bGQgYmUgb3V0cHV0IGZvciBlYWNoIG9mIHRoZSBmb3JtdWxhcywgYW5kIG5vIG90aGVyIGNoYXJhY3RlcnMgc2hvdWxkIGJlIG91dHB1dC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

ICPC > Regionals > Asia Pacific > Japan > Japan Domestic Contest > 2008 Japan Domestic Contest C번