하나.제목

[PDF Link] A mobile is a type of kinetic sculpture constructed to take advantage of the principle of equilibrium. It consists of a number of rods, from which weighted objects or further rods hang. The objects hanging from the rods balance each other, so that the rods remain more or less horizontal. Each rod hangs from only one string, which gives it freedom to rotate about the string.
We consider mobiles where each rod is attached to its string exactly in the middle, as in the figure underneath. You are given such a configuration, but the weights on the ends are chosen incorrectly, so that the mobile is not in equilibrium. Since that's not aesthetically pleasing, you decide to change some of the weights.
What is the minimum number of weights that you must change in order to bring the mobile to equilibrium? You may substitute any weight by any (possibly non-integer) weight. For the mobile shown in the figure, equilibrium can be reached by changing the middle weight from 7 to 3, so only 1 weight needs to changed.

Input

On the first line one positive number: the number of testcases, at most 100. After that per testcase:

One line with the structure of the mobile, which is a  recursively defined expression of the form: 

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

  with a positive integer smaller than  109 indicating a weight and  [,]  indicating a rod with the two expressions at the ends of the rod.  The total number of rods in the chain from a weight to the top of  the mobile will be at most 16.

Output

Per testcase:

One line with the minimum number of weights that have to be changed.

Sample Input

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

Sample Output

103

2.분석과 실현

본고는 매우 흥미롭다. 우선'균형'이라는 관계를 통해 한 잎이 다른 모든 잎의 크기를 결정할 수 있다는 것을 분석하고 생각해야 한다. 즉, 한 노드가 전체 두 갈래 나무의 크기를 결정하기 때문에 우리는 이 성질을 이용하여 몇 개의 노드를 수정해야 하는지 판단한다. 왜냐하면 무게가 다른 노드가 계산한 전체 두 갈래 나무의 총 무게도 반드시 다르기 때문이다.그래서 우리는 모든 노드를 검색한 후에 각 노드가 발생하는 총 무게를 구한다. 가장 많은 총 무게가 나타나는 것은 가장 많은 잎 노드가 수정할 필요가 없다는 것을 의미한다.

셋.총결산

본고는 이러한 데이터 구조를 이용하여 임의의 유형의 데이터의 출현 횟수를 통계할 수 있기를 희망한다. 우리는 stl 안의 맵을 이용하여 반복적으로 사용하고 비울 수 있는 사용 방법은 다음과 같다. 그리고 주의해야 할 점은 문자의 s와 e를 정하는 것이다. 이 문자는 하나의 숫자이고 숫자로 정리하는 방법이다.

#include <iostream>
#include <cstring>
#include <cmath>
#include <map>
#include <algorithm>
#include <cstdio>
using namespace std;
map<long long,int>base;
int sum;
string str;
void dfs(int s,int e,int depth)
{
	if(str[s]=='[')
	{
		///cout<<s<<" "<<e<<endl;
		int p;
		p=0;
		for(int i=s+1;i<=e;i++)
		{
			//cout<<s<<" "<<e<<endl;
			if(str[i]=='[') p++;
			if(str[i]==']') p--;
			if(!p&&str[i]==',')
			{
				dfs(s+1,i-1,depth+1);
				dfs(i+1,e-1,depth+1);
			}
		}
	}
	else 
	{
		long long  w;
		w=0;
		for(int i=s;i<=e;i++)
		{
			w=w*10+str[i]-'0';
		}
		//cout<<w<<endl;
		sum++;
		base[w<<depth]++;
		//printflag();
	}
}
int main()
{
	//freopen("input.txt","r",stdin);
	int T;
	cin>>T;
	for(int t=1;t<=T;t++)
	{

		cin>>str;
		int len;
		base.clear();
		sum=0;
		len=str.length();
		dfs(0,len-1,0);
		int maxn=0;
		for(map<long long,int>::iterator it=base.begin();it!=base.end();++it)
		{
			maxn=max(maxn,it->second);
		}
		printf("%d
",sum-maxn);
	}
}