Problem:


Problem B: Stylish

Stylish is a programming language whose syntax comprises names, that are sequences of Latin alphabet letters, three types of grouping symbols, periods ('.'), and newlines. Grouping symbols, namely round brackets ('(' and ')'), curly brackets ('{' and '}'), and square brackets ('[' and ']'), must match and be nested properly. Unlike most other programming languages, Stylish uses periods instead of whitespaces for the purpose of term separation. The following is an example of a Stylish program.

1 ( Welcome .to
2 ......... Stylish )
3 { Stylish .is
4 .....[.( a. programming . language .fun .to. learn )
5 .......]
6 ..... Maybe .[
7 ....... It. will .be.an. official . ICPC . language
8 .......]
9 .....}

As you see in the example, a Stylish program is indented by periods. The amount of indentation of a line is the number of leading periods of it.

Your mission is to visit Stylish masters, learn their indentation styles, and become the youngest Stylish master. An indentation style for well-indented Stylish programs is defined by a triple of integers, (R, C, S), satisfying 1 ≤ R, C, S ≤ 20. R, C and S are amounts of indentation introduced by an open round bracket, an open curly bracket, and an open square bracket, respectively.

In a well-indented program, the amount of indentation of a line is given by R(ro &minus; rc) + C(co &minus; cc) + S(so &minus; sc), where ro, co, and so are the numbers of occurrences of open round, curly, and square brackets in all preceding lines, respectively, and rc, cc, and sc are those of close brackets. The first line has no indentation in any well-indented program.

The above example is formatted in the indentation style (R, C, S) = (9, 5, 2). The only grouping symbol occurring in the first line of the above program is an open round bracket. Therefore the amount of indentation for the second line is 9 &middot; (1 &minus; 0) + 5 &middot; (0 &minus; 0) + 2 &middot;(0 &minus; 0) = 9. The first four lines contain two open round brackets, one open curly bracket, one open square bracket, two close round brackets, but no close curly nor square bracket. Therefore the amount of indentation for the fifth line is 9 &middot; (2 &minus; 2) + 5 &middot; (1 &minus; 0) + 2 &middot; (1 &minus; 0) = 7.

Stylish masters write only well-indented Stylish programs. Every master has his/her own indentation style.

Write a program that imitates indentation styles of Stylish masters.

Input

The input consists of multiple datasets. The first line of a dataset contains two integers p (1 ≤ p ≤ 10) and q (1 ≤ q ≤ 10). The next p lines form a well-indented program P written by a
Stylish master and the following q lines form another program Q. You may assume that every line of both programs has at least one character and at most 80 characters. Also, you may assume that no line of Q starts with a period.

The last dataset is followed by a line containing two zeros.

Output

Apply the indentation style of P to Q and output the appropriate amount of indentation for each line of Q. The amounts must be output in a line in the order of corresponding lines of Q and they must be separated by a single space. The last one should not be followed by trailing spaces. If the appropriate amount of indentation of a line of Q cannot be determined uniquely through analysis of P, then output -1 for that line.

Sample Input

5 4
(Follow.my.style
.........starting.from.round.brackets)
{then.curly.brackets
.....[.and.finally
.......square.brackets.]}
(Thank.you
{for.showing.me
[all
the.secrets]})
4 2
(This.time.I.will.show.you
.........(how.to.use.round.brackets)
.........[but.not.about.square.brackets]
.........{nor.curly.brackets})
(I.learned
how.to.use.round.brackets)
4 2
(This.time.I.will.show.you
.........(how.to.use.round.brackets)
.........[but.not.about.square.brackets]
.........{nor.curly.brackets})
[I.have.not.learned
how.to.use.square.brackets]
2 2
(Be.smart.and.let.fear.of
..(closed.brackets).go)
(A.pair.of.round.brackets.enclosing
[A.line.enclosed.in.square.brackets])
1 2
Telling.you.nothing.but.you.can.make.it
[One.liner.(is).(never.indented)]
[One.liner.(is).(never.indented)]
2 4
([{Learn.from.my.KungFu
...}])
((
{{
[[
]]}}))
1 2
Do.not.waste.your.time.trying.to.read.from.emptiness
(
)
2 3
({Quite.interesting.art.of.ambiguity
....})
{
(
)}
2 4
({[
............................................................]})
(
{
[
]})
0 0

Output for the Sample Input

0 9 14 16
0 9
0 -1
0 2
0 0
0 2 4 6
0 -1
0 -1 4
0 20 40 60



Sample input:
5 4
(Follow.my.style
.........starting.from.round.brackets)
{then.curly.brackets
.....[.and.finally
.......square.brackets.]}
(Thank.you
{for.showing.me
[all
the.secrets]})
4 2
(This.time.I.will.show.you
.........(how.to.use.round.brackets)
.........[but.not.about.square.brackets]
.........{nor.curly.brackets})
(I.learned
how.to.use.round.brackets)
4 2
(This.time.I.will.show.you
.........(how.to.use.round.brackets)
.........[but.not.about.square.brackets]
.........{nor.curly.brackets})
[I.have.not.learned
how.to.use.square.brackets]
2 2
(Be.smart.and.let.fear.of
..(closed.brackets).go)
(A.pair.of.round.brackets.enclosing
[A.line.enclosed.in.square.brackets])
1 2
Telling.you.nothing.but.you.can.make.it
[One.liner.(is).(never.indented)]
[One.liner.(is).(never.indented)]
2 4
([{Learn.from.my.KungFu
...}])
((
{{
[[
]]}}))
1 2
Do.not.waste.your.time.trying.to.read.from.emptiness
(
)
2 3
({Quite.interesting.art.of.ambiguity
....})
{
(
)}
2 4
({[
............................................................]})
(
{
[
]})
0 0


Sample output:
0 9 14 16
0 9
0 -1
0 2
0 0
0 2 4 6
0 -1
0 -1 4
0 20 40 60

Submission status: Wrong Answer

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 = 10**9+7
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 = []

    while True:
        p,q = LI()
        if p == 0:
            break

        a = [S() for _ in range(p)]
        b = [S() for _ in range(q)]
        aa = [[0,0,0,0]]
        mc = 0
        for c in a:
            d = collections.Counter(c)
            t = aa[-1][:]
            t[0] += d['(']
            t[0] -= d[')']
            t[1] += d['{']
            t[1] -= d['}']
            t[2] += d['[']
            t[2] -= d[']']
            t[3] = 0
            for ct in c:
                if ct != '.':
                    break
                t[3] += 1
                if mc < t[3]:
                    mc = t[3]
            aa.append(t)
        k = []
        for c1,c2,c3 in itertools.product(range(1,min(mc+1,21)), repeat=3):
            f = True
            for ci in range(p):
                c = aa[ci]
                if c[0] * c1 + c[1] * c2 + c[2] * c3 != aa[ci+1][3]:
                    f = False
                    break
            if f:
                k.append((c1,c2,c3))
        bb = [[0,0,0]]
        for c in b:
            d = collections.Counter(c)
            t = bb[-1][:]
            t[0] += d['(']
            t[0] -= d[')']
            t[1] += d['{']
            t[1] -= d['}']
            t[2] += d['[']
            t[2] -= d[']']
            bb.append(t)

        r = [0]
        for c in bb[1:-1]:
            s = set()
            for c1,c2,c3 in k:
                s.add(c[0]*c1+c[1]*c2+c[2]*c3)
            if len(s) == 1:
                r.append(list(s)[0])
            else:
                r.append(-1)

        rr.append(' '.join(map(str,r)))


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


print(main())

Submission status: Accepted

Solution code:
from itertools import product
ci = "({["
co = ")}]"
while 1:
    p, q = map(int, input().split())
    if p == q == 0:
        break
    S = [input() for i in range(p)]
    T = [input() for i in range(q)]
    L = [set() for i in range(q)]

    for lens in product(range(1, 21), repeat=3):
        cnts = [0]*3
        ok = 1
        for s in S:
            idx = 0
            while s[idx] == '.':
                idx += 1
            if sum(c*l for c, l in zip(cnts, lens)) != idx:
                ok = 0
                break
            for c in s:
                if c in ci:
                    cnts[ci.index(c)] += 1
                elif c in co:
                    cnts[co.index(c)] -= 1
        if not ok:
            continue
        cnts = [0]*3
        for i, t in enumerate(T):
            idx = 0
            while t[idx] == '.':
                idx += 1
            L[i].add(sum(c*l for c, l in zip(cnts, lens)))
            for c in t:
                if c in ci:
                    cnts[ci.index(c)] += 1
                elif c in co:
                    cnts[co.index(c)] -= 1
    ans = [0]*q
    for i in range(q):
        if 1 < len(L[i]):
            ans[i] = -1
        else:
            v, = L[i]
            ans[i] = v
    print(*ans)

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 = 10**9+7
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 = []

    while True:
        p,q = LI()
        if p == 0:
            break

        a = [S() for _ in range(p)]
        b = [S() for _ in range(q)]
        aa = [[0,0,0,0]]
        mc = 0
        for c in a:
            d = collections.Counter(c)
            t = aa[-1][:]
            t[0] += d['(']
            t[0] -= d[')']
            t[1] += d['{']
            t[1] -= d['}']
            t[2] += d['[']
            t[2] -= d[']']
            t[3] = 0
            for ct in c:
                if ct != '.':
                    break
                t[3] += 1
                if mc < t[3]:
                    mc = t[3]
            aa.append(t)
        k = []
        for c1,c2,c3 in itertools.product(range(1,min(mc+1,21)), repeat=3):
            f = True
            for ci in range(p):
                c = aa[ci]
                if c[0] * c1 + c[1] * c2 + c[2] * c3 != aa[ci+1][3]:
                    f = False
                    break
            if f:
                k.append((c1,c2,c3))
        bb = [[0,0,0]]
        for c in b:
            d = collections.Counter(c)
            t = bb[-1][:]
            t[0] += d['(']
            t[0] -= d[')']
            t[1] += d['{']
            t[1] -= d['}']
            t[2] += d['[']
            t[2] -= d[']']
            bb.append(t)

        r = [0]
        for c in bb[1:-1]:
            s = set()
            for c1,c2,c3 in k:
                s.add(c[0]*c1+c[1]*c2+c[2]*c3)
            if len(s) == 1:
                r.append(list(s)[0])
            elif sum(c) == 0:
                r.append(0)
            else:
                r.append(-1)

        rr.append(' '.join(map(str,r)))


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


print(main())

Submission status: Accepted

Solution code:
import re
while 1:
    R=[]
    C=[]
    S=[]
    p,q=map(int,input().split())
    if p==q==0:break
    #P=[input()for _ in range(p)]
    G=[]
    R_c=[0]
    C_c=[0]
    S_c=[0]
    for _ in range(p):
        s=input()
        cnt=s.count
        G.append(re.match('[.]*',s).span()[1])
        R_c.append(R_c[-1]+cnt('(')-cnt(')'))
        C_c.append(C_c[-1]+cnt('{')-cnt('}'))
        S_c.append(S_c[-1]+cnt('[')-cnt(']'))
    for x in range(1,21):
        for y in range(1,21):
            for z in range(1,21):
                for g,i,j,k, in zip(G,R_c,C_c,S_c):
                    if i*x+j*y+k*z!=g:
                        break
                else:
                    R.append(x)
                    C.append(y)
                    S.append(z)
    #print(R,C,S)
    R_c=[0]
    C_c=[0]
    S_c=[0]
    for _ in range(q):
        s=input()
        cnt=s.count
        R_c.append(R_c[-1]+cnt('(')-cnt(')'))
        C_c.append(C_c[-1]+cnt('{')-cnt('}'))
        S_c.append(S_c[-1]+cnt('[')-cnt(']'))
    R_c=R_c[:-1]
    C_c=C_c[:-1]
    S_c=S_c[:-1]

    a=[set()for _ in range(q)]
    for x,y,z in zip(R,C,S):
        for idx,(i,j,k)in enumerate(zip(R_c,C_c,S_c)):
            a[idx].add(i*x+j*y+k*z)
    print(*[list(t)[0]if len(t)==1else-1for t in a])