시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 56 24 13 29.545%

문제

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

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

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

물체의 무게는 임의의 음이 아닌 실수로 바꿀 수 있다. 위의 그림에서 무게 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+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzY4MSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkVxdWlsaWJyaXVtIE1vYmlsZSIsImRlc2NyaXB0aW9uIjoiPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9tb2JpbGUuanBnXCIgc3R5bGU9XCJmbG9hdDpyaWdodDsgaGVpZ2h0OjI0MHB4OyB3aWR0aDoyNDJweFwiIFwvPkEgbW9iaWxlIGlzIGEgdHlwZSBvZiBraW5ldGljIHNjdWxwdHVyZSBjb25zdHJ1Y3RlZCB0byB0YWtlIGFkdmFudGFnZSBvZiB0aGUgcHJpbmNpcGxlIG9mIGVxdWlsaWJyaXVtLiBJdCBjb25zaXN0cyBvZiBhIG51bWJlciBvZiByb2RzLCBmcm9tIHdoaWNoIHdlaWdodGVkIG9iamVjdHMgb3IgZnVydGhlciByb2RzIGhhbmcuIFRoZSBvYmplY3RzIGhhbmdpbmcgZnJvbSB0aGUgcm9kcyBiYWxhbmNlIGVhY2ggb3RoZXIsIHNvIHRoYXQgdGhlIHJvZHMgcmVtYWluIG1vcmUgb3IgbGVzcyBob3Jpem9udGFsLiBFYWNoIHJvZCBoYW5ncyBmcm9tIG9ubHkgb25lIHN0cmluZywgd2hpY2ggZ2l2ZXMgaXQgZnJlZWRvbSB0byByb3RhdGUgYWJvdXQgdGhlIHN0cmluZy48XC9wPlxyXG5cclxuPHA+V2UgY29uc2lkZXIgbW9iaWxlcyB3aGVyZSBlYWNoIHJvZCBpcyBhdHRhY2hlZCB0byBpdHMgc3RyaW5nIGV4YWN0bHkgaW4gdGhlIG1pZGRsZSwgYXMgaW4gdGhlIFx1ZmIwMWd1cmUgdW5kZXJuZWF0aC4gWW91IGFyZSBnaXZlbiBzdWNoIGEgY29uXHVmYjAxZ3VyYXRpb24sIGJ1dCB0aGUgd2VpZ2h0cyBvbiB0aGUgZW5kcyBhcmUgY2hvc2VuIGluY29ycmVjdGx5LCBzbyB0aGF0IHRoZSBtb2JpbGUgaXMgbm90IGluIGVxdWlsaWJyaXVtLiBTaW5jZSB0aGF0JnJzcXVvO3Mgbm90IGFlc3RoZXRpY2FsbHkgcGxlYXNpbmcsIHlvdSBkZWNpZGUgdG8gY2hhbmdlIHNvbWUgb2YgdGhlIHdlaWdodHMuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvbW9iaWxlMigxKS5wbmdcIiBzdHlsZT1cImhlaWdodDoyMDZweDsgd2lkdGg6Mjg5cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+V2hhdCBpcyB0aGUgbWluaW11bSBudW1iZXIgb2Ygd2VpZ2h0cyB0aGF0IHlvdSBtdXN0IGNoYW5nZSBpbiBvcmRlciB0byBicmluZyB0aGUgbW9iaWxlIHRvIGVxdWlsaWJyaXVtPyBZb3UgbWF5IHN1YnN0aXR1dGUgYW55IHdlaWdodCBieSBhbnkgKHBvc3NpYmx5IG5vbi1pbnRlZ2VyKSB3ZWlnaHQuIEZvciB0aGUgbW9iaWxlIHNob3duIGluIHRoZSBcdWZiMDFndXJlLCBlcXVpbGlicml1bSBjYW4gYmUgcmVhY2hlZCBieSBjaGFuZ2luZyB0aGUgbWlkZGxlIHdlaWdodCBmcm9tIDcgdG8gMywgc28gb25seSAxIHdlaWdodCBuZWVkcyB0byBjaGFuZ2VkLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+T24gdGhlIFx1ZmIwMXJzdCBsaW5lIG9uZSBwb3NpdGl2ZSBudW1iZXI6IHRoZSBudW1iZXIgb2YgdGVzdGNhc2VzLCBhdCBtb3N0IDEwMC4gQWZ0ZXIgdGhhdCBwZXIgdGVzdGNhc2U6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+T25lIGxpbmUgd2l0aCB0aGUgc3RydWN0dXJlIG9mIHRoZSBtb2JpbGUsIHdoaWNoIGlzIGEgcmVjdXJzaXZlbHkgZGVcdWZiMDFuZWQgZXhwcmVzc2lvbiBvZiB0aGUgZm9ybTo8XC9saT5cclxuXHQ8bGk+Jmx0O2V4cHImZ3Q7IDo6PSAmbHQ7d2VpZ2h0Jmd0OyB8ICZsZHF1bztbJnJkcXVvOyAmbHQ7ZXhwciZndDsgJmxkcXVvOywmcmRxdW87ICZsdDtleHByJmd0OyAmbGRxdW87XSZyZHF1bzsmbmJzcDs8XC9saT5cclxuXHQ8bGk+d2l0aCBod2VpZ2h0aSBhIHBvc2l0aXZlIGludGVnZXIgc21hbGxlciB0aGFuIDEwPHN1cD45PFwvc3VwPiBpbmRpY2F0aW5nIGEgd2VpZ2h0IGFuZCBbJmx0O2V4cHImZ3Q7LCZsdDtleHByJmd0O10gaW5kaWNhdGluZyBhIHJvZCB3aXRoIHRoZSB0d28gZXhwcmVzc2lvbnMgYXQgdGhlIGVuZHMgb2YgdGhlIHJvZC4gVGhlIHRvdGFsIG51bWJlciBvZiByb2RzIGluIHRoZSBjaGFpbiBmcm9tIGEgd2VpZ2h0IHRvIHRoZSB0b3Agb2YgdGhlIG1vYmlsZSB3aWxsIGJlIGF0IG1vc3QgMTYuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJvdXRwdXQiOiI8cD5QZXIgdGVzdGNhc2U6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+T25lIGxpbmUgd2l0aCB0aGUgbWluaW11bSBudW1iZXIgb2Ygd2VpZ2h0cyB0aGF0IGhhdmUgdG8gYmUgY2hhbmdlZC48XC9saT5cclxuPFwvdWw+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

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

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