Problem:


Hierarchical Democracy

The presidential election in Republic of Democratia is carried out through multiple stages as follows.

There are exactly two presidential candidates.

At the first stage, eligible voters go to the polls of his/her electoral district.
The winner of the district is the candidate who takes a majority of the votes.
Voters cast their ballots only at this first stage.

A district of the k-th stage (k > 1) consists of multiple districts of the (k &minus; 1)-th stage. In contrast, a district of the (k &minus; 1)-th stage is a sub-district of one and only one district of the k-th stage. The winner of a district of the k-th stage is the candidate who wins in a majority of its sub-districts of the (k &minus; 1)-th stage.

The final stage has just one nation-wide district. The winner of the final stage is chosen as the president.

You can assume the following about the presidential election of this country.

Every eligible voter casts a vote.

The number of the eligible voters of each electoral district of the first stage is odd.

The number of the sub-districts of the (k &minus; 1)-th stage that constitute a district of the k-th stage (k > 1) is also odd.

This means that each district of every stage has its winner (there is no tie). 

Your mission is to write a program that finds a way to win the presidential election with the minimum number of votes.
Suppose, for instance, that the district of the final stage has three sub-districts of the first stage and that the numbers of the eligible voters of the sub-districts are 123, 4567, and 89, respectively.
The minimum number of votes required to be the winner is 107, that is, 62 from the first district and 45 from the third.
In this case, even if the other candidate were given all the 4567 votes in the second district, s/he would inevitably be the loser. 
Although you might consider this election system unfair, you should accept it as a reality.

Input

The entire input looks like:

the number of datasets (=n) 

1st dataset                 

2nd dataset                 

&hellip;                                

n-th dataset                

The number of datasets, n, is no more than 100.

The number of the eligible voters of each district and the part-whole relations among districts are denoted as follows.

  
An electoral district of the first stage is denoted as [c], where c is the number of the eligible voters of the district.

  
A district of the k-th stage (k > 1) is denoted as [d1d2&hellip;dm], where d1, d2, &hellip;, dm denote its sub-districts of the (k &minus; 1)-th stage in this notation.

For instance, an electoral district of the first stage that has 123 eligible voters is denoted as [123].
A district of the second stage consisting of three sub-districts of the first stage that have 123, 4567, and 89 eligible voters, respectively, is denoted as [[123][4567][89]].

Each dataset is a line that contains the character string denoting the district of the final stage in the aforementioned notation.
You can assume the following.

  
The character string in each dataset does not include any characters except digits ('0', '1', &hellip;, '9') and square brackets ('[', ']'), and its length is between 11 and 10000, inclusive.

  
The number of the eligible voters of each electoral district of the first stage is between 3 and 9999, inclusive.

The number of stages is a nation-wide constant.
So, for instance, [[[9][9][9]][9][9]] never appears in the input.
[[[[9]]]] may not appear either since each district of the second or later stage must have multiple sub-districts of the previous stage.

Output

For each dataset, print the minimum number of votes required to be the winner of the presidential election in a line.
No output line may include any characters except the digits with which the number is written.

Sample Input

6
[[123][4567][89]]
[[5][3][7][3][9]]
[[[99][59][63][85][51]][[1539][7995][467]][[51][57][79][99][3][91][59]]]
[[[37][95][31][77][15]][[43][5][5][5][85]][[71][3][51][89][29]][[57][95][5][69][31]][[99][59][65][73][31]]]
[[[[9][7][3]][[3][5][7]][[7][9][5]]][[[9][9][3]][[5][9][9]][[7][7][3]]][[[5][9][7]][[3][9][3]][[9][5][5]]]]
[[8231][3721][203][3271][8843]]

Output for the Sample Input

107
7
175
95
21
3599



Sample input:
6
[[123][4567][89]]
[[5][3][7][3][9]]
[[[99][59][63][85][51]][[1539][7995][467]][[51][57][79][99][3][91][59]]]
[[[37][95][31][77][15]][[43][5][5][5][85]][[71][3][51][89][29]][[57][95][5][69][31]][[99][59][65][73][31]]]
[[[[9][7][3]][[3][5][7]][[7][9][5]]][[[9][9][3]][[5][9][9]][[7][7][3]]][[[5][9][7]][[3][9][3]][[9][5][5]]]]
[[8231][3721][203][3271][8843]]


Sample output:
107
7
175
95
21
3599

Submission status: Wrong Answer

Solution code:
def calc_majority(l):
    l.sort()
    result = 0
    for i in range(len(l) // 2 + 1):
        result += l[i]
    return result

#過半数になるような値を求めてそれを返す
def calc_fisrt_majority(l):
    people_num = list(map(int, l))
    people_num.sort()
    n = 0
    for i in range(len(people_num) // 2 + 1):
        n += int(people_num[i]) // 2 + 1
    return n

#括弧と括弧の間の数値を返す
def get_num(l, lp, rp):
    #print(lp, end="")
    #print(" ", end="")
    #print(rp)
    s = ''
    for i in range(lp+1, rp):
        s += l[i]
    return s

#左かっこに対応する右かっこのインデックスを返す
def getRp(char_list, n):
    count = 1
    i = 0
    while count:
        c = char_list[i]
        i += 1
        if c == '[':
            count += 1
        elif c == ']':
            count -= 1
        else:
            continue

    return i+n

#かっこの位置全てのリストを返す
def brackets(s):
    lp = []
    rp = []
    n = 0
    bucket_nest = 0
    l = list(s)

    for i in l:
        if i == '[':
            bucket_nest += 1
        if i != '[':
            break

    for i in l:
        n += 1
        if i == '[':
            lp.append(n-1)
            rp.append(getRp(l[n:], n-1))
    for i in range(1, len(lp)):
        return lp, rp, bucket_nest

def main():
    N = int(input())
    lp = []
    rp = []
    tmp_result = []
    result = 0
    people_num = []
    nest = 0
    n = 0
    while N != 0:
        s = input()
        l = list(s)
        N -= 1
        lp, rp, nest = brackets(s)
        n = 0
        for i in lp:
            if(l[i+1] != '['): #次が[でないなら必ず数字が来る
                people_num.append(get_num(l, lp[n], rp[n]))
                if(l[rp[n]+1] == ']'): #ネストの終わり
                    tmp_result.append(calc_fisrt_majority(people_num))
                    people_num.clear()
            n += 1

        print(tmp_result)
        if nest == 2:
            result = tmp_result[0]

        while nest != 2:
            result = calc_majority(tmp_result)
            nest -= 1
        print(result)

if __name__ == '__main__':
    main()

#[[[37][95][31][77][15]][[43][5][5][5][85]][[71][3][51][89][29]]
#[[57][95][5][69][31]][[99][59][65][73][31]]]
#[[43][9][43][48][79]]=9+43+43=95

Submission status: Accepted

Solution code:
def rec(s):
    ans = int(1e8)
    c_list = []
    st = []
    n = len(s)
    l = 0
    r = len(s)-1
    if s[0]!='[':
        return 1+int(s)//2
    for i in range(n):
        _s = s[i]
        if _s=='[':
            if len(st)==0:
                l = i+1
            st.append(_s)
        elif _s==']':
            st = st[:-1]
            if len(st)==0:
                r = i
                c_list.append(rec(s[l:r]))
    c_list.sort()
    return sum( c_list[:1+len(c_list)//2] )

N = int(input())
for _ in range(N):
    s = input()
    print(rec(s))

Submission status: Accepted

Solution code:
def dfs(s):
 if type(s)==int:return s/2+1
 v=sorted(map(dfs, s));return sum(v[:len(v)/2+1])
for _ in[0]*input():print dfs(eval(raw_input().replace("][","],[")))

Submission status: Accepted

Solution code:
def parser(l, r):
    if all(S[i].isdigit() for i in range(l, r + 1)):
        return int(S[l:r + 1]) // 2 + 1
    ret = []
    cnt = 0
    start = 0
    for i in range(l, r + 1):
        if S[i] == '[':
            cnt += 1
            if cnt == 1:
                start = i
        elif S[i] == ']':
            if cnt == 1:
                ret.append(parser(start + 1, i - 1))
            cnt -= 1
    ret.sort()
    return sum(ret[:len(ret) // 2 + 1])


N = int(input())
for _ in range(N):
    S = input()
    print(parser(0, len(S) - 1))

Submission status: Accepted

Solution code:
n = input()
for _ in xrange(n):
    s = raw_input()
    cur = 1
    def parse():
        global cur
        result = []
        num = None
        while 1:
            c = s[cur]; cur += 1
            if c is '[':
                result.append(parse())
            elif c is ']':
                break
            else:
                num = num or 0
                num = 10*num + int(c)
        if num is not None:
            return num/2+1
        l = len(result)
        result.sort()
        return sum(result[:l/2+1])

    print parse()

Submission status: Accepted

Solution code:
#!/usr/bin/env python
N = input()

def func(lst):
    if len(lst) == 1:
        return lst[0] // 2 + 1
    res_lst = []
    for l in lst:
        res_lst.append(func(l))
    res_lst.sort()
    ret = 0
    for i in range(len(res_lst) // 2 + 1):
        ret += res_lst[i]
    return ret

for loop in range(N):
    S = raw_input()
    hoge = S.split(']')
    S = '],'.join(hoge)
    exec('piyo = ' + S[:-1])
    print func(piyo)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353
dd = [(0,-1),(1,0),(0,1),(-1,0)]
ddn = [(0,-1),(1,-1),(1,0),(1,1),(0,1),(-1,-1),(-1,0),(-1,1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []
    n = I()
    ni = 0

    def f(a):
        if len(a) == 1:
            return a[0] // 2 + 1
        cs = sorted([f(c) for c in a])
        return sum(cs[:len(cs)//2+1])

    while ni < n:
        ni += 1
        s = S()
        a = eval(s.replace('][', '],['))
        rr.append(f(a))

    return '\n'.join(map(str,rr))


print(main())

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from sys import setrecursionlimit
setrecursionlimit(100000)

def cal(L):
    if type(L[0][0]) == list:
        L = [[cal(l)*2] for l in L]
    return sum(sorted([-(-l[0]//2) for l in L])[:-(-len(L)//2)])

for _ in range(int(input())):
    print(cal(eval(input().replace("][", "],["))))

Submission status: Accepted

Solution code:
N = int(input())
def rec ():
	global now,l
	if s[now].isdigit():
		res = 0
		while (now < l and s[now].isdigit()):
			res = ((10 * res) + int(s[now]))
			now += 1
		return (res+1)//2
	else:
		g = []
		while(now < l and s[now] == '['):
			now += 1
			g.append(rec())
			now += 1
		g.sort()
		return sum(g[:(len(g)+1)//2])

for i in range(N):
	s = input()
	l = len(s)
	now = 0
	print(rec())

Submission status: Accepted

Solution code:
def cost(s):
  lens = len(s)
  if lens == 1:
    return int(s[0]) // 2 + 1
  costs = [cost(x) for x in s]
  costs.sort()
  return sum(costs[:lens // 2 + 1])

n = int(input())
for _ in range(n):
  s = input()
  s = s.replace("][", "],[")
  s = eval(s)
  print(cost(s))

Submission status: Accepted

Solution code:
def solve(a):
	if type(a[0]) is int:
		a = [a[i]/2+1 for i in range(len(a))]
		return sum(sorted(a)[:len(a)/2+1])
	else:
		return sum(sorted(solve(a[i]) for i in range(len(a)))[:len(a)/2+1])
for i in range(input()):
	A = eval(raw_input().replace("][","],["))
	print solve(A)

Submission status: Accepted

Solution code:
def solve(a):
	if type(a[0]) is int:
		return sum(sorted(a)[:len(a)/2+1])/2 + len(a)
	else:
		return sum(sorted(solve(i) for i in a)[:len(a)/2+1])
for i in range(input()):
	A = eval(raw_input().replace("][","],["))
	print solve(A)

Submission status: Accepted

Solution code:
N=int(input())
for i in range(N):
    s__=input()
    s_=""
    s=[]
    #step1
    for i in range(len(s__)):
        if s__[i].isdigit():
            s_+=s__[i]
        else:
            s_+=" "+s__[i]+" "
    s_=s_.split(" ")
    for i in range(len(s_)):
        if s_[i]!='':
            s.append(s_[i])

    #step2
    M=[[] for i in range(10)]
    M_=[0]*10
    D=[]
    count=0
    for i in range(len(s)):
        if s[i]=='[':
            count +=1
        elif s[i]==']':
            M[count].append(M_[count])
            M_[count]=0
            M_[count-1]+=1
            count-=1
        else:
            D.append(int(s[i]))
    for i in range(1,len(M)):
        if len(M[i])==0:
            M=M[1:i]
            break
    for i in range(len(M[-1])):
        M[-1][i]=1
    for i in range(len(M)):
        M[i]=[0]+M[i]
    for i in range(len(M)):
        for j in range(1,len(M[i])):
            M[i][j]=M[i][j]+M[i][j-1]

    #step3
    ans=[]
    for i in range(len(M)):
        ans.append([0]*(len(M[i])-1))
    for j in range(len(ans[-1])):
        ans[-1][j]=(D[j]//2)+1
    for i in range(len(M)-2,-1,-1):
        for j in range(len(ans[i])):
            partial_sorted=sorted(ans[i+1][M[i][j]:M[i][j+1]])
            ans[i][j]=sum(partial_sorted[:((len(partial_sorted)//2)+1)])

    print(ans[0][0])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def f(x):
    res = []
    flag = False
    tank = []
    for i in range(len(x)):
        if x[i] == 0 and x[i+1] > 0:
            flag = True
        elif x[i] == 0:
            res.append(0)
        elif x[i] > 0:
            tank.append(x[i])
        elif x[i] == -1 and flag:
            tank.sort()
            res.append(sum(tank[:len(tank)//2+1]))
            flag = False
            tank = []
        else:
            res.append(-1)
    return res


testnum = int(input())
for testcase in range(testnum):
    ss = list(input())
    s = []
    tmp,p = 0,0
    for i in range(len(ss)-2,-1,-1):
        if ss[i] == "]":
            s.append(-1)
        elif ss[i] == "[":
            s.append(0)
        else:
            tmp += int(ss[i])*pow(10,p)
            p += 1
            if ss[i-1] == "[":
                s.append(tmp//2+1)
                tmp,p = 0,0
    s = s[::-1]
    while len(s) > 1:
        s = f(s)
    print(s[0])

Submission status: Accepted

Solution code:
def f(S):
    k,l = 0,0
    num = ""
    A = []
    for i in range(len(S)):
        s = S[i]
        if s=="[":
            k+=1
            if k==3 and l==0:
                l = i-1
        elif s=="]":
            k-=1
            if l==0 and k==1:
                num = int(num)
                num = num//2 if num%2==0 else num//2+1
                A.append(num)
                num = ""
            elif l!=0 and k==1:
                A.append(f(S[l:i+1]))
                num = ""
                l = 0
        else:
            num += s
    A.sort()
    return sum(A[:len(A)//2+1])
for i in [0]*int(input()):
    S = input()
    print(f(S))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

class Node():
    def __init__(self):
        self.is_leaf = False
        self.val = -1
        self.childs = []
        self.child_num = 0
        self.parent = None

    def win(self):
        if self.is_leaf:
            return self.val // 2 + 1
        tmp = []
        for c in self.childs:
            tmp.append(c.win())
        tmp = sorted(tmp)
        ret = 0
        for i in range(self.child_num//2 + 1):
            ret += tmp[i]
        return ret

def main():
    n = int(input())
    questions = [input().strip() for i in range(n)]

    for q in questions:
        root = Node()
        now = root
        i = 0
        while i < len(q):
            if q[i] == "[":
                tmp = Node()
                tmp.parent = now
                now.childs.append(tmp)
                now.child_num += 1
                now = tmp
                i += 1
            elif q[i] == "]":
                now = now.parent
                i += 1
            else:
                j = i
                while q[j+1] in "0123456789":
                    j += 1
                now.is_leaf = True
                now.val = int(q[i:j+1])
                i = j+1
        print(root.win())

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())


N = inp()
for nnnnnnn in range(N):
    S = input()
    stacks = [[] for _ in range(10000)]
    num = ''
    d = 0
    for s in S:
        if s == '[':
            d += 1
        elif s == ']':
            if num != '':
                num = int(num)
                stacks[d-1].append(num//2+1)
                num = ''
            else:
                stacks[d].sort()
                L = len(stacks[d])
                stacks[d-1].append(sum(stacks[d][:L//2+1]))
                stacks[d] = []
            d -= 1
        else:
            num = num + s
    print(stacks[0][0])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**5)

def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LI_(): return [-1*int(x) for x in input().split()]
def II(): return int(input())
def IF(): return float(input())
def LM(func,n): return [[func(x) for x in input().split()]for i in range(n)]
mod = 1000000007
inf = float('INF')


def solve(L):
   L = L[1:-1]
   if L[0] != '[':
       return int(L)//2+1
   ret = []
   s=0
   c = 0

   for i in range(len(L)):
       if L[i] == '[':
           c += 1
       elif L[i] == ']':
           c -= 1
       if c == 0:
           ret.append(solve(L[s:i + 1]))
           s = i + 1
   ret.sort()
   return sum(ret[0:len(ret)//2+1])


N = II()
for i in range(N):
    L = input()
    print(solve(L))

Submission status: Accepted

Solution code:
from itertools import combinations

class Source:
  def __init__(self, S):
    self.S = S
    self.pos = 0

def peek(S):
  return S.S[S.pos] if S.pos < len(S.S) else a

def next(S):
  S.pos += 1
      
def expr(S):
  next(S)
  if peek(S) != '[':
    return num(S) // 2 + 1
    
  A = []
  while peek(S) != ']':
    A.append(expr(S))
    next(S)
  
  A.sort()

  return sum(A[:len(A) // 2 + 1])
  
def num(S):
  res = 0
  while '0' <= peek(S) <= '9':
    res = 10 * res + int(peek(S))
    next(S)
    
  return res
             
n = int(input())
for i in range(n):
  print(expr(Source(input())))

Submission status: Accepted

Solution code:
import re

n = int(input())
for _ in range(n):
    dataset = input()
    stage = 1
    while (re.match('\[[0-9]+\]', dataset) is None):
        iterator = re.finditer('\[([0-9]+\]\[)+[0-9]+\]', dataset)
        minimum_votes = []
        for i, match in enumerate(iterator):
            areas = list(map(int, match.group()[1:-1].split('][')))
            minimum_areas = sorted(areas)[:len(areas)//2 + 1]
            if stage == 1:
                minimum_voters = [m // 2 + 1 for m in minimum_areas]
                minimum_vote = sum(minimum_voters)
            else:
                minimum_vote = sum(minimum_areas)
            minimum_votes.append(str(minimum_vote))
            dataset = dataset.replace(match.group(), str(-i-1), 1)
        for i, minimum_vote in enumerate(minimum_votes):
            dataset = dataset.replace(str(-i-1), minimum_vote, 1)
        stage += 1
    print(dataset[1:-1])

Submission status: Accepted

Solution code:
import re

n = int(input())
for _ in range(n):
    dataset = input()
    stage = 1
    while (re.match('\[[0-9]+\]', dataset) is None):
        iterator = re.finditer('\[([0-9]+\]\[)+[0-9]+\]', dataset)
        for match in iterator:
            areas = list(map(int, match.group()[1:-1].split('][')))
            minimum_areas = sorted(areas)[:len(areas)//2 + 1]
            if stage == 1:
                minimum_voters = [m // 2 + 1 for m in minimum_areas]
                minimum_vote = sum(minimum_voters)
            else:
                minimum_vote = sum(minimum_areas)
            dataset = dataset.replace(match.group(), '*' + str(minimum_vote) + '*', 1)
        dataset = dataset.replace('*', '')
        # print(dataset)

        stage += 1
    print(dataset[1:-1])

Submission status: Accepted

Solution code:
#2005_c
"""
n = int(input())
k = list("mcxi")
for i in range(n):
    d = {"m":0,"c":0,"x":0,"i":0}
    a,b  = input().split()
    a = list(a)
    b = list(b)
    a.insert(0,1)
    b.insert(0,1)
    for j in range(1,len(a)):
        if a[j] in k:
            if a[j-1] in k:
                d[a[j]] += 1
            else:
                d[a[j]] += int(a[j-1])
    for j in range(1,len(b))[::-1]:
        if b[j] in k:
            if b[j-1] in k:
                d[b[j]] += 1
            else:
                d[b[j]] += int(b[j-1])
            if d[b[j]] >= 10:
                l = b[j]
                while d[l] >= 10:
                    d[l] -= 10
                    l = k[k.index(l)-1]
                    d[l] += 1
    for j in k:
        if d[j]:
            if d[j] == 1:
                print(j,end = "")
            else:
                print(str(d[j])+j,end = "")
    print()
"""

#2017_c
"""
while 1:
    h, w = map(int, input().split())
    if h == w == 0:
        break
    s = [list(map(int, input().split())) for i in range(h)]

    ans = 0
    for u in range(h):
        for d in range(u+2,h):
            for l in range(w):
                for r in range(l+2,w):
                    m = float("inf")
                    for i in range(u,d+1):
                        m = min(m,s[i][l],s[i][r])
                    for i in range(l,r+1):
                        m = min(m,s[u][i],s[d][i])
                    f = 1
                    su = 0
                    for i in range(u+1,d):
                        for j in range(l+1,r):
                            su += (m-s[i][j])
                            if s[i][j] >= m:
                                f = 0
                                break
                        if not f:
                            break
                    if f:
                        ans = max(ans,su)
    print(ans)
"""

#2016_c
"""
while 1:
    m,n = map(int, input().split())
    if m == n == 0:
        break
    d = {}
    ma = 7368791
    for i in range(m,ma+1):
        d[i] = 1
    z = m
    for i in range(n):
        for j in range(z,ma+1):
            if d[j]:
                z = j
                break
        j = 1
        while z*j <= ma:
            d[z*j] = 0
            j += 1
    for j in range(z,ma+1):
        if d[j]:
            print(j)
            break
"""

#2018_c
"""
def factorize(n):
    if n < 4:
        return [1,n]
    i = 2
    l = [1]
    while i**2 <= n:
        if n%i == 0:
            l.append(i)
            if n//i != i:
                l.append(n//i)
        i += 1
    l.append(n)
    l.sort()
    return l
while 1:
    b = int(input())
    if b == 0:
        break
    f = factorize(2*b)
    for n in f[::-1]:
        a = 1-n+(2*b)//n
        if a >= 1 and a%2 == 0:
            print(a//2,n)
            break
"""

#2010_c
"""
import sys
dp = [100]*1000000
dp_2 = [100]*1000000
dp[0] = 0
dp_2[0] = 0
for i in range(1,181):
    s = i*(i+1)*(i+2)//6
    for j in range(s,1000000):
        if dp[j-s]+1 < dp[j]:
            dp[j] = dp[j-s]+1
    if s%2:
        for j in range(s,1000000):
            if dp_2[j-s]+1 < dp_2[j]:
                dp_2[j] = dp_2[j-s]+1
while 1:
    m = int(sys.stdin.readline())
    if m == 0:
        break
    print(dp[m],dp_2[m])
"""

#2015_c
"""
from collections import deque
while 1:
    n = int(input())
    if n == 0:
        break
    s = [input() for i in range(n)]
    d = [s[i].count(".") for i in range(n)]
    m = max(d)
    c = [s[i][-1] for i in range(n)]
    q = deque()
    for i in range(1,m+1)[::-1]:
        j = 0
        while j < n:
            for k in range(j,n):
                if d[k] == i:break
            else:
                break
            j = k
            op = c[j-1]
            while j < n and d[j] == i:
                q.append(j)
                j += 1
            j = k
            if op == "+":
                k = 0
                while q:
                    x = q.pop()
                    k += int(c[x])
                    c.pop(x)
                    d.pop(x)
                    n -= 1
            else:
                k = 1
                while q:
                    x = q.pop()
                    k *= int(c[x])
                    c.pop(x)
                    d.pop(x)
                    n -= 1
            c[j-1] = k
    print(c[0])
"""

#2013_c
from collections import defaultdict

def parse_expr(s,i):
    i += 1
    if s[i] == "[":
        q = []
        while s[i] != "]":
            e,i = parse_expr(s,i)
            q.append(e)
        return (calc(q),i+1)
    else:
        n,i = parse_num(s,i)
        return (calc([n]),i+1)

def parse_num(s,i):
    m = int(s[i])
    i += 1
    while f_num[s[i]]:
        m *= 10
        m += int(s[i])
        i += 1
    return (m,i)

def calc(q):
    if len(q) == 1:
        return (q[0]+1)//2
    q.sort()
    return sum(q[:len(q)//2+1])

f_num = defaultdict(lambda : 0)
for i in range(10):
    f_num[str(i)] = 1

n = int(input())
for i in range(n):
    s = input()
    print(parse_expr(s,0)[0])

Submission status: Accepted

Solution code:
n = int(input())
for i in range(n):
  t = input()
  nums = [[] for i in range(100)]
  num = ""
  nest = 0
  maxnest = 0
  for e in t:
    if e=="[":
      nest += 1
      maxnest = max(maxnest, nest)
    elif e!="[" and e!="]":
      num += e
    elif e=="]" and len(num):
      nums[nest].append(int(num)//2+1)
      num = ""
      nest -= 1
    else:
      nums[nest+1].sort()
      t = 0
      for i in range(len(nums[nest+1])//2+1):
        t += nums[nest+1][i]
      nums[nest+1] = []
      nums[nest].append(t)
      nest -= 1
  print(nums[1][0])

Submission status: Accepted

Solution code:
N=int(input())
for i in range(N):
    S=input()
    stack=[]
    num=[0]
    st=""
    N=len(S)
    for j in range(N):
        i=S[j]
        #print(num)
        #print(stack)
        #print('"'+i+'"',st)
        if i=="[":
            stack.append(0)
            num.append(0)
        elif i=="]":
            n=num.pop()
            num[-1]+=1
            if st!="":
                stack[-1]+=((int(st)+1)//2)
            else:
                tmp=[]
                for k in range(n):
                    tmp.append(stack[-1])
                    stack.pop()
                tmp.sort()
                stack[-1]+=sum(tmp[:(len(tmp)+1)//2])
            st=""
        else:
            st=st+str(i)
    #print(num)
    #print(stack)
    print(stack[0])

Submission status: Accepted

Solution code:
def rec(s, l, now=0):
    if s[now].isdigit():
        res = ''
        while now < l and s[now] != ']':
            res += s[now]
            now += 1
        return int(res) // 2 + 1, now + 1
    else:
        g = []
        while now < l and s[now] == '[':
            res, now = rec(s, l, now + 1)
            g.append(res)
        g.sort()
        return sum(g[:len(g) // 2 + 1]), now + 1


for _ in range(int(input())):
    s = input()
    l = len(s)
    print(rec(s, l)[0])

Submission status: Accepted

Solution code:
def AC():
    def solve(s):
        if s.count('[')==1:
            return int(s[1:-1])
        elif '][' in s and ']][[' not in s:
            tmp = sorted(map(int,s[2:-2].split('][')))
            ans=0
            for i in range(len(tmp)//2+1):
                ans+=tmp[i]//2+1
            return ans
        else:
            count=0
            for i in range(len(s)):
                if s[i]=='[':
                    count+=1
                else:
                    count-=1
                    break
            tmp=s[1:-1].split(']'*count+'['*count)
            d=[]
            for i in range(len(tmp)):
                if i==0:
                    tmp[i]=tmp[i]+']'*count
                elif i==len(tmp)-1:
                    tmp[i]='['*count+tmp[i]
                else:
                    tmp[i]='['*count+tmp[i]+']'*count
                d.append(solve(tmp[i]))
            tmp = sorted(d)
            ans=0
            for i in range(len(tmp)//2+1):
                ans+=tmp[i]
            return ans
    
    if __name__ == '__main__':
        n=int(input())
        for i in range(n):
            print(solve(input()))
AC()

Submission status: Runtime Error

Solution code:
def solve(a):
	if type(a[0]) is int:
		return sum(sorted(a)[:len(a)/2+1])/2 + len(a)
	else:
		return sum(sorted(solve(i) for i in a))[:len(a)/2+1])
for i in range(input()):
	A = eval(raw_input().replace("][","],["))
	print solve(A)