Problem:


Score : 600 points

Problem Statement

We have N strings of lowercase English letters: S_1, S_2, \cdots, S_N.

Takahashi wants to make a string that is a palindrome by choosing one or more of these strings - the same string can be chosen more than once - and concatenating them in some order of his choice.

The cost of using the string S_i once is C_i, and the cost of using it multiple times is C_i multiplied by that number of times.

Find the minimum total cost needed to choose strings so that Takahashi can make a palindrome.

If there is no choice of strings in which he can make a palindrome, print -1.

Constraints

1 \leq N \leq 50

1 \leq |S_i| \leq 20

S_i consists of lowercase English letters.

1 \leq C_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N
S_1 C_1
S_2 C_2
:
S_N C_N

Output

Print the minimum total cost needed to choose strings so that Takahashi can make a palindrome, or -1 if there is no such choice.

Sample Input 1

3
ba 3
abc 4
cbaa 5

Sample Output 1

7

We have ba, abc, and cbaa.

For example, we can use ba once and abc once for a cost of 7, then concatenate them in the order abc, ba to make a palindrome.
Also, we can use abc once and cbaa once for a cost of 9, then concatenate them in the order cbaa, abc to make a palindrome.

We cannot make a palindrome for a cost less than 7, so we should print 7.

Sample Input 2

2
abcab 5
cba 3

Sample Output 2

11

We can choose abcab once and cba twice, then concatenate them in the order abcab, cba, cba to make a palindrome for a cost of 11.

Sample Input 3

4
ab 5
cba 3
a 12
ab 10

Sample Output 3

8

We can choose a once, which is already a palindrome, but it is cheaper to concatenate ab and cba.

Sample Input 4

2
abc 1
ab 2

Sample Output 4

-1

We cannot make a palindrome, so we should print -1.



Sample input:
3
ba 3
abc 4
cbaa 5


Sample output:
7

Submission status: Runtime Error

Solution code:
from random import randrange
from heapq import heapify, heappush, heappop
from time import time
K = 150
rand = lambda: randrange(1 << K)
sTime = time()
N = int(input())
S, IS, C = [], [], []
for _ in range(N):
    s, c = input().split()
    S.append(s)
    IS.append(s[::-1])
    C.append(int(c))

D = {}
r = rand()
D[r] = (0, "", 0)
H = [r]
ans = 1 << K
while H:
    r = heappop(H)
    if time() - sTime > 1.7:
        print(1 // 0)
    d, s, c = D[r]
    if d == 0:
        for ss, cc in zip(S, C):
            m = min(len(s), len(ss))
            if s[:m] == ss[:m]:
                if abs(len(s) - len(ss)) <= 1 or len(ss) > len(s) and ss[m:] == ss[m:][::-1]:
                    ans = min(ans, c + cc)
                else:
                    if len(s) < len(ss):
                        r = rand() + (c + cc << K)
                        D[r] = (1, ss[m:], c + cc)
                        heappush(H, r)
                    else:
                        r = rand() + (c + cc << K)
                        D[r] = (0, s[m:], c + cc)
                        heappush(H, r)
    else:
        for ss, cc in zip(IS, C):
            m = min(len(s), len(ss))
            if s[:m] == ss[:m]:
                if abs(len(s) - len(ss)) <= 1 or len(ss) > len(s) and ss[m:] == ss[m:][::-1]:
                    ans = min(ans, c + cc)
                else:
                    if len(s) < len(ss):
                        r = rand() + (c + cc << K)
                        D[r] = (0, ss[m:], c + cc)
                        heappush(H, r)
                    else:
                        r = rand() + (c + cc << K)
                        D[r] = (1, s[m:], c + cc)
                        heappush(H, r)

print(ans if ans < 1 << K - 2 else -1)

Submission status: Runtime Error

Solution code:
n=input()
s=[]
c=[None]*n
for i in range(n):
  s_i,c_i=input().split()
  s.append(s_i)
  c[i]=int(c_i)
score=100000000000000
for i in range(n):
  for j in range(n):
    for k in range(n):
      for l in range(n):
        s0="".join(s[i],s[j])
        s1="".join(s[i],s[k])
        s2="".join(s[i],s[l])
        s3="".join(s[i],s[j],s[k])
        s4="".join(s[i],s[k],[l])
        s5="".join(s[i],s[j],s[k],s[l])
        if s0==s0[::-1]:
          score=min(score,c[i]+c[j])
        if s1==s1[::-1]:
          score=min(score,c[i]+c[k])
        if s2==s2[::-1]:
          score=min(score,c[i]+c[l])
        if s3==s3[::-1]:
          score=min(score,c[i]+c[j]+c[k])
        if s4==s4[::-1]:
          score=min(score,c[i]+c[k]+c[l])
        if s5==s5[::-1]:
          score=min(score,c[i]+c[j]+c[k]+c[l])
if score==100000000000000:
  print(-1)
else:
  print(score)

Submission status: Runtime Error

Solution code:
from random import randrange
from heapq import heapify, heappush, heappop
from time import time
K = 150
rand = lambda: randrange(1 << K)
sTime = time()
N = int(input())
S, IS, C = [], [], []
for _ in range(N):
    s, c = input().split()
    S.append(s)
    IS.append(s[::-1])
    C.append(int(c))

D = {}
r = rand()
D[r] = (0, "", 0)
H = [r]
ans = 1 << K
while H:
    r = heappop(H)
    if time() - sTime > 1.7:
        print(1 // 0)
    d, s, c = D[r]
    if d == 0:
        for ss, cc in zip(S, C):
            m = min(len(s), len(ss))
            if s[:m] == ss[:m]:
                if abs(len(s) - len(ss)) <= 1:
                    ans = min(ans, c + cc)
                else:
                    if len(s) < len(ss):
                        r = rand() + (c + cc << K)
                        D[r] = (1, ss[m:], c + cc)
                        heappush(H, r)
                    else:
                        r = rand() + (c + cc << K)
                        D[r] = (0, s[m:], c + cc)
                        heappush(H, r)
    else:
        for ss, cc in zip(IS, C):
            m = min(len(s), len(ss))
            if s[:m] == ss[:m]:
                if abs(len(s) - len(ss)) <= 1:
                    ans = min(ans, c + cc)
                else:
                    if len(s) < len(ss):
                        r = rand() + (c + cc << K)
                        D[r] = (0, ss[m:], c + cc)
                        heappush(H, r)
                    else:
                        r = rand() + (c + cc << K)
                        D[r] = (1, s[m:], c + cc)
                        heappush(H, r)

print(ans if ans < 1 << K - 2 else -1)

Submission status: Runtime Error

Solution code:
N=int(input())
X=[list(input().split()) for i in range(N)]
for i in range(N):
  X[i][1]=int(X[i][1])
INF=10**18
def f(S):
  if len(S)<2:
    return 0
  r=INF
  T=0
  for i in range(N):
    T=S+X[i][0]
    if T==T[::-1]:
      r=min(r,X[i][1])
  for i in range(N):
    if len(S)>=len(X[i][0]):
      if S[:len(X[i][0])]==X[i][0][::-1]:
        r=min(r,f(S[len(X[i][0]):])+X[i][1])
    elif len(S)*2>len(X[i][0]):
      if X[i][0][:len(S)]==S[::-1]:
        r=min(r,f(X[i][0][::-1][:len(S)])+X[i][1])
  return r

P=INF
for i in range(N):
  P=min(P,f(X[i][0])+X[i][1])
if P!=INF:
  print(P)
else:
  print(-1)

Submission status: Runtime Error

Solution code:
from random import randrange
from heapq import heapify, heappush, heappop
from time import time
K = 150
rand = lambda: randrange(1 << K)
sTime = time()
N = int(input())
S, IS, C = [], [], []
for _ in range(N):
    s, c = input().split()
    S.append(s)
    IS.append(s[::-1])
    C.append(int(c))

D = {}
r = rand()
D[r] = (0, "", 0)
H = [r]
ans = 1 << 60
while H:
    r = heappop(H)
    if time() - sTime > 1.7:
        print(1 // 0)
    d, s, c = D[r]
    if d == 0:
        for ss, cc in zip(S, C):
            m = min(len(s), len(ss))
            if s[:m] == ss[:m]:
                if abs(len(s) - len(ss)) <= 1:
                    ans = min(ans, c + cc)
                else:
                    if len(s) < len(ss):
                        r = rand() + (c + cc << K)
                        D[r] = (1, ss[m:], c + cc)
                        heappush(H, r)
                    else:
                        r = rand() + (c + cc << K)
                        D[r] = (0, s[m:], c + cc)
                        heappush(H, r)
    else:
        for ss, cc in zip(IS, C):
            m = min(len(s), len(ss))
            if s[:m] == ss[:m]:
                if abs(len(s) - len(ss)) <= 1:
                    ans = min(ans, c + cc)
                else:
                    if len(s) < len(ss):
                        r = rand() + (c + cc << K)
                        D[r] = (0, ss[m:], c + cc)
                        heappush(H, r)
                    else:
                        r = rand() + (c + cc << K)
                        D[r] = (1, s[m:], c + cc)
                        heappush(H, r)

print(ans if ans < 1 << 58 else -1)

Submission status: Runtime Error

Solution code:
N=int(input())
X=[list(input().split()) for i in range(N)]
for i in range(N):
  X[i][1]=int(X[i][1])
INF=10**18
def f(S):
  if len(S)<2:
    return 0
  r=INF
  T=0
  for i in range(N):
    T=S+X[i][0]
    if T==T[::-1]:
      r=min(r,X[i][1])
  for i in range(N):
    if len(S)>=len(X[i][0]):
      if S[:len(X[i][0])]==X[i][0][::-1]:
        r=min(r,f(S[len(X[i][0]):])+X[i][1])
    elif len(S)*2>len(X[i][0]):
      if X[i][0][:len(S)]==S[::-1]:
        r=min(r,f(X[i][0][:len(S)])+X[i][1])
  return r

P=INF
for i in range(N):
  P=min(P,f(X[i][0])+X[i][1])
if P!=INF:
  print(P)
else:
  print(-1)

Submission status: Runtime Error

Solution code:
N=int(input())
X=[list(input().split()) for i in range(N)]
for i in range(N):
  X[i][1]=int(X[i][1])
INF=10**18
def f(S,b):
  if len(S)<2:
    return 0
  r=INF
  T=0
  for i in range(N):
    T=S+X[i][0]
    if T==T[::-1]:
      r=min(r,X[i][1])
  for i in range(N):
    if len(S)>=len(X[i][0]):
      if S[:len(X[i][0])]==X[i][0][::-b]:
        r=min(r,f(S[len(X[i][0]):],b)+X[i][1])
    elif len(S)*2>len(X[i][0]):
      if X[i][0][:len(S)]==S[::b]:
        r=min(r,f(X[i][0][:len(S)],-b)+X[i][1])
  return r

P=INF
for i in range(N):
  P=min(P,f(X[i][0],1)+X[i][1])
if P!=INF:
  print(P)
else:
  print(-1)

Submission status: Runtime Error

Solution code:
from random import randrange
from heapq import heapify, heappush, heappop
from time import time
sTime = time()
N = int(input())
S, IS, C = [], [], []
for _ in range(N):
    s, c = input().split()
    S.append(s)
    IS.append(s[::-1])
    C.append(int(c))

D = {}
r = randrange(1 << 60)
D[r] = (0, "", 0)
H = [r]
ans = 1 << 60
while H:
    r = heappop(H)
    if time.time() - sTime > 1.7:
        break
    d, s, c = D[r]
    if d == 0:
        for ss, cc in zip(S, C):
            m = min(len(s), len(ss))
            if s[:m] == ss[:m]:
                if abs(len(s) - len(ss)) <= 1:
                    ans = min(ans, c + cc)
                else:
                    if len(s) < len(ss):
                        r = randrange(1 << 60) + (c + cc << 60)
                        D[r] = (1, ss[m:], c + cc)
                        heappush(H, r)
                    else:
                        r = randrange(1 << 60) + (c + cc << 60)
                        D[r] = (0, s[m:], c + cc)
                        heappush(H, r)
    else:
        for ss, cc in zip(IS, C):
            m = min(len(s), len(ss))
            if s[:m] == ss[:m]:
                if abs(len(s) - len(ss)) <= 1:
                    ans = min(ans, c + cc)
                else:
                    if len(s) < len(ss):
                        r = randrange(1 << 60) + (c + cc << 60)
                        D[r] = (0, ss[m:], c + cc)
                        heappush(H, r)
                    else:
                        r = randrange(1 << 60) + (c + cc << 60)
                        D[r] = (1, s[m:], c + cc)
                        heappush(H, r)

print(ans if ans < 1 << 58 else -1)