시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 51 20 10 24.390%

문제

모빌은 평형의 원리를 이용한 조각이다. 모빌은 여러 개의 막대와 물체로 이루어져 있다. 물체는 막대의 끝에만 매달려 있을 수 있고, 막대도 실을 이용해서 다른 막대의 끝에 연결할 수 있다. 

막대가 다른 막대에 연결되어 있는 경우에는 매달려있는 막대의 중앙과 연결되어 있다. 아래 그림은 모빌의 예이다. 숫자는 물체의 무게를 나타낸다.

균형을 맞추지 않은 모빌이 주어졌을 때, 최소 물체 몇 개의 무게를 바꾸면 모빌이 균형을 이루는지 구하는 프로그램을 작성하시오.

물체의 무게는 임의의 음이 아닌 실수로 바꿀 수 있다. 위의 그림에서 무게 7인 물체의 무게를 3으로 바꾸면, 모빌이 균형을 이룬다. 따라서, 물체 1개만 무게를 바꾸면 된다.

입력

첫째 줄에 테스트 케이스의 수가 주어진다. 테스트 케이스는 최대 100개이다.

각 테스트 케이스는 한 줄로 이루어져 있고, 아래와 같이 재귀적으로 표현한다.

<expr> ::= <weight> | "[" <expr> "," <expr> "]"

<weight>는 양의 정수로 109보다 작은 양의 정수이다. [<expr>,<expr>]는 막대를 나타내 표현으로 두 표현은 막대의 양 끝을 나타낸다. 가장 위에 있는 막대와 가장 아래에 있는 막대 사이에 막대 개수 (두 막대 포함) 는 최대 16개이다.

출력

각 테스트 케이스 마다, 균형을 이루기 위해 무게를 바꿔야하는 물체의 최소 개수를 출력한다.

예제 입력 1

3
[[3,7],6]
40
[[2,3],[4,5]]

예제 출력 1

1
0
3

힌트

W3sicHJvYmxlbV9pZCI6IjM2ODEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJhYThcdWJlNGMiLCJkZXNjcmlwdGlvbiI6IjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvbW9iaWxlLmpwZ1wiIHN0eWxlPVwiZmxvYXQ6cmlnaHQ7IGhlaWdodDoyNDBweDsgd2lkdGg6MjQycHhcIiBcLz5cdWJhYThcdWJlNGNcdWM3NDAgXHVkM2M5XHVkNjE1XHVjNzU4IFx1YzZkMFx1YjlhY1x1Yjk3YyBcdWM3NzRcdWM2YTlcdWQ1NWMgXHVjODcwXHVhYzAxXHVjNzc0XHViMmU0LiBcdWJhYThcdWJlNGNcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWI5YzlcdWIzMDBcdWM2NDAgXHViYjNjXHVjY2I0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YmIzY1x1Y2NiNFx1YjI5NCBcdWI5YzlcdWIzMDBcdWM3NTggXHViMDVkXHVjNWQwXHViOWNjIFx1YjllNFx1YjJlY1x1YjgyNCBcdWM3ODhcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YWNlMCwgXHViOWM5XHViMzAwXHViM2M0IFx1YzJlNFx1Yzc0NCBcdWM3NzRcdWM2YTlcdWQ1NzRcdWMxMWMgXHViMmU0XHViOTc4IFx1YjljOVx1YjMwMFx1Yzc1OCBcdWIwNWRcdWM1ZDAgXHVjNWYwXHVhY2IwXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1YjljOVx1YjMwMFx1YWMwMCBcdWIyZTRcdWI5NzggXHViOWM5XHViMzAwXHVjNWQwIFx1YzVmMFx1YWNiMFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyOTQgXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IFx1YjllNFx1YjJlY1x1YjgyNFx1Yzc4OFx1YjI5NCBcdWI5YzlcdWIzMDBcdWM3NTggXHVjOTExXHVjNTU5XHVhY2ZjIFx1YzVmMFx1YWNiMFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyZTQuIFx1YzU0NFx1Yjc5OCBcdWFkZjhcdWI5YmNcdWM3NDAgXHViYWE4XHViZTRjXHVjNzU4IFx1YzYwOFx1Yzc3NFx1YjJlNC4gXHVjMjJiXHVjNzkwXHViMjk0IFx1YmIzY1x1Y2NiNFx1Yzc1OCBcdWJiMzRcdWFjOGNcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFkZTBcdWQ2MTVcdWM3NDQgXHViOWRlXHVjZDk0XHVjOWMwIFx1YzU0YVx1Yzc0MCBcdWJhYThcdWJlNGNcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjZDVjXHVjMThjIFx1YmIzY1x1Y2NiNCBcdWJhODcgXHVhYzFjXHVjNzU4IFx1YmIzNFx1YWM4Y1x1Yjk3YyBcdWJjMTRcdWFmYjhcdWJhNzQgXHViYWE4XHViZTRjXHVjNzc0IFx1YWRlMFx1ZDYxNVx1Yzc0NCBcdWM3NzRcdWI4ZThcdWIyOTRcdWM5YzAgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvbW9iaWxlMigxKS5wbmdcIiBzdHlsZT1cImhlaWdodDoyMDZweDsgd2lkdGg6Mjg5cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHViYjNjXHVjY2I0XHVjNzU4IFx1YmIzNFx1YWM4Y1x1YjI5NCBcdWM3ODRcdWM3NThcdWM3NTggXHVjNzRjXHVjNzc0IFx1YzU0NFx1YjJjYyBcdWMyZTRcdWMyMThcdWI4NWMgXHViYzE0XHVhZmMwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YzcwNFx1Yzc1OCBcdWFkZjhcdWI5YmNcdWM1ZDBcdWMxMWMgXHViYjM0XHVhYzhjIDdcdWM3NzggXHViYjNjXHVjY2I0XHVjNzU4IFx1YmIzNFx1YWM4Y1x1Yjk3YyAzXHVjNzNjXHViODVjIFx1YmMxNFx1YWZiOFx1YmE3NCwgXHViYWE4XHViZTRjXHVjNzc0IFx1YWRlMFx1ZDYxNVx1Yzc0NCBcdWM3NzRcdWI4ZWNcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYywgXHViYjNjXHVjY2I0IDFcdWFjMWNcdWI5Y2MgXHViYjM0XHVhYzhjXHViOTdjIFx1YmMxNFx1YWZiOFx1YmE3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjMjE4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWNkNWNcdWIzMDAgMTAwXHVhYzFjXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWQ1NWMgXHVjOTA0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWFjZTAsIFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWM3NzQgXHVjN2FjXHVhZGMwXHVjODAxXHVjNzNjXHViODVjIFx1ZDQ1Y1x1ZDYwNFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHByZT5cclxuJmx0O2V4cHImZ3Q7IDo6PSAmbHQ7d2VpZ2h0Jmd0OyB8ICZxdW90O1smcXVvdDsgJmx0O2V4cHImZ3Q7ICZxdW90OywmcXVvdDsgJmx0O2V4cHImZ3Q7ICZxdW90O10mcXVvdDs8XC9wcmU+XHJcblxyXG48cD4mbHQ7d2VpZ2h0Jmd0O1x1YjI5NCBcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4XHViODVjIDEwPHN1cD45PFwvc3VwPlx1YmNmNFx1YjJlNCBcdWM3OTFcdWM3NDAgXHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOFx1Yzc3NFx1YjJlNC4gWyZsdDtleHByJmd0OywmbHQ7ZXhwciZndDtdXHViMjk0IFx1YjljOVx1YjMwMFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjQgXHVkNDVjXHVkNjA0XHVjNzNjXHViODVjIFx1YjQ1MCBcdWQ0NWNcdWQ2MDRcdWM3NDAgXHViOWM5XHViMzAwXHVjNzU4IFx1YzU5MSBcdWIwNWRcdWM3NDQgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LiBcdWFjMDBcdWM3YTUgXHVjNzA0XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWI5YzlcdWIzMDBcdWM2NDAgXHVhYzAwXHVjN2E1IFx1YzU0NFx1Yjc5OFx1YzVkMCBcdWM3ODhcdWIyOTQgXHViOWM5XHViMzAwIFx1YzBhY1x1Yzc3NFx1YzVkMCBcdWI5YzlcdWIzMDAgXHVhYzFjXHVjMjE4IChcdWI0NTAgXHViOWM5XHViMzAwIFx1ZDNlY1x1ZDU2OCkgXHViMjk0IFx1Y2Q1Y1x1YjMwMCAxNlx1YWMxY1x1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNCBcdWI5YzhcdWIyZTQsIFx1YWRlMFx1ZDYxNVx1Yzc0NCBcdWM3NzRcdWI4ZThcdWFlMzAgXHVjNzA0XHVkNTc0IFx1YmIzNFx1YWM4Y1x1Yjk3YyBcdWJjMTRcdWFmZDRcdWM1N2NcdWQ1NThcdWIyOTQgXHViYjNjXHVjY2I0XHVjNzU4IFx1Y2Q1Y1x1YzE4YyBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjM2ODEiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJFcXVpbGlicml1bSBNb2JpbGUiLCJkZXNjcmlwdGlvbiI6IjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvbW9iaWxlLmpwZ1wiIHN0eWxlPVwiZmxvYXQ6cmlnaHQ7IGhlaWdodDoyNDBweDsgd2lkdGg6MjQycHhcIiBcLz5BIG1vYmlsZSBpcyBhIHR5cGUgb2Yga2luZXRpYyBzY3VscHR1cmUgY29uc3RydWN0ZWQgdG8gdGFrZSBhZHZhbnRhZ2Ugb2YgdGhlIHByaW5jaXBsZSBvZiBlcXVpbGlicml1bS4gSXQgY29uc2lzdHMgb2YgYSBudW1iZXIgb2Ygcm9kcywgZnJvbSB3aGljaCB3ZWlnaHRlZCBvYmplY3RzIG9yIGZ1cnRoZXIgcm9kcyBoYW5nLiBUaGUgb2JqZWN0cyBoYW5naW5nIGZyb20gdGhlIHJvZHMgYmFsYW5jZSBlYWNoIG90aGVyLCBzbyB0aGF0IHRoZSByb2RzIHJlbWFpbiBtb3JlIG9yIGxlc3MgaG9yaXpvbnRhbC4gRWFjaCByb2QgaGFuZ3MgZnJvbSBvbmx5IG9uZSBzdHJpbmcsIHdoaWNoIGdpdmVzIGl0IGZyZWVkb20gdG8gcm90YXRlIGFib3V0IHRoZSBzdHJpbmcuPFwvcD5cclxuXHJcbjxwPldlIGNvbnNpZGVyIG1vYmlsZXMgd2hlcmUgZWFjaCByb2QgaXMgYXR0YWNoZWQgdG8gaXRzIHN0cmluZyBleGFjdGx5IGluIHRoZSBtaWRkbGUsIGFzIGluIHRoZSBcdWZiMDFndXJlIHVuZGVybmVhdGguIFlvdSBhcmUgZ2l2ZW4gc3VjaCBhIGNvblx1ZmIwMWd1cmF0aW9uLCBidXQgdGhlIHdlaWdodHMgb24gdGhlIGVuZHMgYXJlIGNob3NlbiBpbmNvcnJlY3RseSwgc28gdGhhdCB0aGUgbW9iaWxlIGlzIG5vdCBpbiBlcXVpbGlicml1bS4gU2luY2UgdGhhdCZyc3F1bztzIG5vdCBhZXN0aGV0aWNhbGx5IHBsZWFzaW5nLCB5b3UgZGVjaWRlIHRvIGNoYW5nZSBzb21lIG9mIHRoZSB3ZWlnaHRzLjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL21vYmlsZTIoMSkucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjA2cHg7IHdpZHRoOjI4OXB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPldoYXQgaXMgdGhlIG1pbmltdW0gbnVtYmVyIG9mIHdlaWdodHMgdGhhdCB5b3UgbXVzdCBjaGFuZ2UgaW4gb3JkZXIgdG8gYnJpbmcgdGhlIG1vYmlsZSB0byBlcXVpbGlicml1bT8gWW91IG1heSBzdWJzdGl0dXRlIGFueSB3ZWlnaHQgYnkgYW55IChwb3NzaWJseSBub24taW50ZWdlcikgd2VpZ2h0LiBGb3IgdGhlIG1vYmlsZSBzaG93biBpbiB0aGUgXHVmYjAxZ3VyZSwgZXF1aWxpYnJpdW0gY2FuIGJlIHJlYWNoZWQgYnkgY2hhbmdpbmcgdGhlIG1pZGRsZSB3ZWlnaHQgZnJvbSA3IHRvIDMsIHNvIG9ubHkgMSB3ZWlnaHQgbmVlZHMgdG8gY2hhbmdlZC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPk9uIHRoZSBcdWZiMDFyc3QgbGluZSBvbmUgcG9zaXRpdmUgbnVtYmVyOiB0aGUgbnVtYmVyIG9mIHRlc3RjYXNlcywgYXQgbW9zdCAxMDAuIEFmdGVyIHRoYXQgcGVyIHRlc3RjYXNlOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPk9uZSBsaW5lIHdpdGggdGhlIHN0cnVjdHVyZSBvZiB0aGUgbW9iaWxlLCB3aGljaCBpcyBhIHJlY3Vyc2l2ZWx5IGRlXHVmYjAxbmVkIGV4cHJlc3Npb24gb2YgdGhlIGZvcm06PFwvbGk+XHJcblx0PGxpPiZsdDtleHByJmd0OyA6Oj0gJmx0O3dlaWdodCZndDsgfCAmbGRxdW87WyZyZHF1bzsgJmx0O2V4cHImZ3Q7ICZsZHF1bzssJnJkcXVvOyAmbHQ7ZXhwciZndDsgJmxkcXVvO10mcmRxdW87Jm5ic3A7PFwvbGk+XHJcblx0PGxpPndpdGggaHdlaWdodGkgYSBwb3NpdGl2ZSBpbnRlZ2VyIHNtYWxsZXIgdGhhbiAxMDxzdXA+OTxcL3N1cD4gaW5kaWNhdGluZyBhIHdlaWdodCBhbmQgWyZsdDtleHByJmd0OywmbHQ7ZXhwciZndDtdIGluZGljYXRpbmcgYSByb2Qgd2l0aCB0aGUgdHdvIGV4cHJlc3Npb25zIGF0IHRoZSBlbmRzIG9mIHRoZSByb2QuIFRoZSB0b3RhbCBudW1iZXIgb2Ygcm9kcyBpbiB0aGUgY2hhaW4gZnJvbSBhIHdlaWdodCB0byB0aGUgdG9wIG9mIHRoZSBtb2JpbGUgd2lsbCBiZSBhdCBtb3N0IDE2LjxcL2xpPlxyXG48XC91bD5cclxuIiwib3V0cHV0IjoiPHA+UGVyIHRlc3RjYXNlOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPk9uZSBsaW5lIHdpdGggdGhlIG1pbmltdW0gbnVtYmVyIG9mIHdlaWdodHMgdGhhdCBoYXZlIHRvIGJlIGNoYW5nZWQuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

ACM-ICPC > Regionals > Europe > Northwestern European Regional Contest > NWERC 2008 A번

  • 문제를 번역한 사람: baekjoon
  • 잘못된 번역을 찾은 사람: kks227