CodeEff/ECCO huggingface dataset:
# Original solution
import sys

sys.setrecursionlimit(10**7)

inf = float('inf')

def solve():
    n = int(sys.stdin.readline())

    r = [0] * n
    c = [0] * n

    for i in range(n):
        ri, ci = list(map(int, sys.stdin.readline().split()))
        r[i] = ri
        c[i] = ci

    memo = [[-1]*(n + 1) for i in range(n + 1)]

    ans = mcm(memo, n, r, c, 0, n)

    # print(memo)

    print(ans)

def mcm(memo, n, r, c, left, right):
    if memo[left][right] != -1:
        return memo[left][right]
    elif right - left == 1:
        memo[left][right] = 0
        return 0
    else:
        res = inf

        for i in range(left + 1, right):
            res = min(res, mcm(memo, n, r, c, left, i) + mcm(memo, n, r, c, i, right) + r[left]*r[i]*c[right-1])

        memo[left][right] = res
        return res

def compute_lcs(x, y):
    n = len(x)
    m = len(y)

    x = '#' + x
    y = '#' + y

    dp = [[0]*(m + 1) for i in range(n + 1)]

    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if x[i] == y[j]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    return dp[n][m]

if __name__ == '__main__':
    solve()

# Optimized solution
import sys

sys.setrecursionlimit(10**7)

inf = float('inf')

def solve():
    n = int(sys.stdin.readline())

    r = [0] * n
    c = [0] * n

    for i in range(n):
        ri, ci = list(map(int, sys.stdin.readline().split()))
        r[i] = ri
        c[i] = ci

    dp = [[0]*(n + 1) for i in range(n + 1)]

    for ls in range(2, n + 1):
        for i in range(n - ls + 1):
            dp[i][i + ls] = inf
            for j in range(i + 1, i + ls):
                dp[i][i + ls] = min(dp[i][i + ls], dp[i][j] + dp[j][i + ls] + r[i]*r[j]*c[i + ls - 1])

    ans = dp[0][n]

    print(ans)

if __name__ == '__main__':
    solve()
# Original solution
class Puzzle:
    def __init__(self,panel,space,cnt):
        self.panel=panel
        self.space=space
        self.cnt=cnt

d=(1,-1,4,-4)
model=list(map(str,list(range(8))))
def check(s):
    if s==model:
        return True
    return False

def bfs(s):
    m=set()
    que=[s]
    m.add(tuple(s.panel))
    while que!=[]:
        now=que[0]
        del que[0]
        if check(now.panel):
            return now.cnt
        idx1=now.space
        for i in range(4):
            idx2=idx1+d[i]
            if idx2<0 or idx2>7:
                continue
            if (idx1==3 and d[i]==1) or (idx1==4 and d[i]==-1):
                continue
            next_panel=now.panel[:]
            next_panel[idx2],next_panel[idx1]=now.panel[idx1],now.panel[idx2]
            next=Puzzle(next_panel,idx2,now.cnt+1)
            if tuple(next.panel) not in m:
                m.add(tuple(next.panel))
                que.append(next)
    return -1

while True:
    try:
        panel=input().split()
    except EOFError:
        break
    space=panel.index("0")
    s=Puzzle(panel,space,0)
    ans=bfs(s)
    print(ans)

# Optimized solution
from collections import defaultdict
d=(1,-1,4,-4)

def solve():
    que=["01234567"]
    while que!=[]:
        v=que[0]
        del que[0]
        pos=v.index("0")
        for i in range(4):
            idx2=pos+d[i]
            if idx2<0 or idx2>7:
                continue
            if (pos==3 and d[i]==1) or (pos==4 and d[i]==-1):
                continue
            u=list(v)
            u[pos],u[pos+d[i]]=u[pos+d[i]],u[pos]
            u="".join(u)
            if res[u]==0:
                que.append(u)
                res[u]=res[v]+1
res=defaultdict(int)
res["01234567"]=1
solve()
while True:
    try:
        s=input().split()
    except EOFError:
        break
    s="".join(s)
    print(res[s]-1)
# Original solution
def to_xyi(str, target):
  index = 0
  for s in list(str):
    if target == int(s):
      x = index%4
      if index < 4:
        y = 0
      else:
        y = 1
      return (x, y, index)
    index += 1

def zero_swap(str, mx, my):
  zx, zy, zi = to_xyi(str, 0)

  for index in range(len(list(str))):
    sx, sy, si = to_xyi(str, index)
    if (zx + mx) == sx and (zy + my) == sy:
      nstr = []
      for s in list(str):
        if s == str[zi]:
          nstr.append(str[si])
        elif s == str[si]:
          nstr.append(str[zi])
        else:
          nstr.append(s)
      return ''.join(nstr)

rules = (
  (lambda x, y : x <= 2, lambda str : zero_swap(str,  1,  0)),
  (lambda x, y : y == 0, lambda str : zero_swap(str,  0,  1)),
  (lambda x, y : x >= 1, lambda str : zero_swap(str, -1,  0)),
  (lambda x, y : y == 1, lambda str : zero_swap(str,  0, -1)),
)

goal = '01234567'

move_num = {goal: 0}
queue = [goal]

while True:
  if len(queue) == 0: break
  search_map = queue.pop(0)

  for can_move, move in rules:
    x, y, i = to_xyi(search_map, 0)
    if not can_move(x, y): continue
    next_map = move(search_map)
    if next_map in move_num: continue
    move_num[next_map] = move_num[search_map] + 1
    queue.append(next_map)

import sys
for s in sys.stdin:
  s = s.replace(' ', '').rstrip()
  print(move_num[s])

# Optimized solution
MOVE = [[1, 4], [0, 2, 5], [1, 3, 6], [2, 7], [0, 5], [1, 4, 6], [2, 5, 7], [3, 6]]
answers = {"01234567": 0}

def swap(field, a, b):
  tmp = list(field)
  tmp[a], tmp[b] = tmp[b], tmp[a]
  return "".join(tmp)

def breadth_first_search(answers):
  q = [[0, "01234567"]]

  while len(q) != 0:
    g, field = q.pop(0)
    a = field.find("0")

    for b in MOVE[a]:
      tmp = swap(field, a, b)

      if not tmp in answers:
        answers[tmp] = g+1
        q.append([g+1, tmp])

  return answers

answers = breadth_first_search(answers)

while True:
  try:
    print(answers[input().replace(" ", "")])
  except:
    break
# Original solution
# AOJ 0121 Seven Puzzle 
# Python 2017.6.23 bal4u

def swap(state, x, y):
	s = list(copy.deepcopy(state))
	s[x], s[y] = s[y], s[x]
	return tuple(s)
	
from collections import deque
import copy
MAGIC = 37
move = ((1,4), (0,2,5), (1,3,6), (2,7), (0,5), (1,4,6), (2,5,7), (3,6))

Q = deque()
Q.append(((0,1,2,3,4,5,6,7), 0))
hash = {}
hash[(0,1,2,3,4,5,6,7)] = 0
while Q:
	state, x = Q.popleft()
	step = hash[state]+1
	if step > MAGIC: continue
	for y in move[x]:
		nstate = swap(state, x, y)
		if nstate not in hash: nstep = 100
		else: nstep = hash[nstate]
		if step < nstep:
			Q.append((nstate, y))
			hash[nstate] = step

while 1:
	try: state = tuple(map(int, input().split()))
	except: break
	print((hash[state]))


# Optimized solution
# AOJ 0121 Seven Puzzle 
# Python 2017.6.23 bal4u

def swap(state, x, y):
	s = list(state)
	s[x], s[y] = s[y], s[x]
	return tuple(s)
	
from collections import deque
MAGIC = 37
move = ((1,4), (0,2,5), (1,3,6), (2,7), (0,5), (1,4,6), (2,5,7), (3,6))

Q = deque()
Q.append(((0,1,2,3,4,5,6,7), 0))
hash = {}
hash[(0,1,2,3,4,5,6,7)] = 0
while Q:
	state, x = Q.popleft()
	step = hash[state]+1
	if step > MAGIC: continue
	for y in move[x]:
		nstate = swap(state, x, y)
		if nstate not in hash: nstep = 100
		else: nstep = hash[nstate]
		if step < nstep:
			Q.append((nstate, y))
			hash[nstate] = step

while 1:
	try: state = tuple(map(int, input().split()))
	except: break
	print((hash[state]))
# Original solution
#!/usr/bin/env python3
import sys

def solve(N: int, S: str):
    answer = 0
    for i in range(0,1000):
        i = str(i).zfill(3)
        index = 0
        for ss in S:
            if ss == i[index]:
                index += 1
                if index >= 3:
                    answer += 1
                    break

    print(answer)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = next(tokens)  # type: int
    solve(N, S)

if __name__ == '__main__':
    main()


# Optimized solution
#!/usr/bin/env python3
import sys

def solve(N: int, S: str):
    answer = 0
    for i in range(0,1000):
        i = str(i).zfill(3)
        x = S.find(i[0])
        if x == -1:
            continue

        y = S.find(i[1],x+1)
        if y == -1:
            continue

        z = S.find(i[2],y+1)
        if z == -1:
            continue
        
        answer +=1
    print(answer)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    solve(N, S)

if __name__ == '__main__':
    main()
# Original solution
from pprint import pprint
import sys

n = int(sys.stdin.readline().strip())
s = sys.stdin.readline().strip()

count = 0
for i in range(1000):
    pin = str(i).zfill(3)
    start = 0
    flags = [False] * 3
    for i, pin_i in enumerate(pin):
        flag = False
        for j, s_j in enumerate(s):
            if j < start:
                continue
            if s_j == pin_i:
                flag = True
                start = j + 1
                break
        flags[i] = flag
    if flags[0] and flags[1] and flags[2]:
        # print(pin)
        count += 1

print(count)

# Optimized solution
import sys

N = int(sys.stdin.readline())
S = sys.stdin.readline()

ans = 0
for i in range(1000):
    password = str(i).zfill(3)
    p_i = 0
    s_i = 0
    while s_i < len(S) and p_i < 3:
        # print(p_i, s_i)
        if S[s_i] == password[p_i]:
            p_i += 1
        s_i += 1
    if p_i == 3:
        ans += 1
print(ans)
# Original solution
import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


# 初期入力　　２０２０－０７２７　21：50
from collections import Counter
import sys
input = sys.stdin.readline  #文字列では使わない
N = int(eval(input()))
*S, =input().strip()
"""
c =Counter(S)
ans =combinations_count(N, 3) -len(c)
"""
count =0
x100=0
x10=0
x1=0
for i in range(10):
    for j in range(10):
        for k in range(10):
            if str(i) in S:
                x100 =S.index(str(i)) +1
                if str(j) in S[x100:]:
                    x10 =S[x100:].index(str(j)) +1
                    if str(k) in S[x100 +x10:]:
                        x1 =S[x100+x10:].index(str(k)) +1
                        count +=1
                        #print("aa",i,j,k,"bb",x100,x100+x10,x100+x10+x1)

print(count)

# Optimized solution
# forしながらif、ifでないときはforしないので、計算量減
# 初期入力　　２０２０－０７２７　21：50
from collections import Counter
import sys
input = sys.stdin.readline  #文字列では使わない
N = int(eval(input()))
*S, =input().strip()
"""
c =Counter(S)
ans =combinations_count(N, 3) -len(c)
"""
count =0
x100=0
x10=0
x1=0
for i in range(10):
    if str(i) in S:
        x100 =S.index(str(i)) +1
        for j in range(10):
            if str(j) in S[x100:]:
                x10 =S[x100:].index(str(j)) +1
                for k in range(10):
                    if str(k) in S[x100 +x10:]:
                        x1 =S[x100+x10:].index(str(k)) +1
                        count +=1
                        #print("aa",i,j,k,"bb",x100,x100+x10,x100+x10+x1)

print(count)
# Original solution
def strKey(key):
    if key == 0:
        return '000'
    if 1<= key <= 9:
        return '00' + str(key)
    if 10<= key <=99:
        return '0' + str(key) 
    return str(key)

N = int(eval(input()))
s  = input().strip()

cnt = 0
for key in range(1000):
    key = strKey(key)    #; print(key)
    isFlag = False
    for i0 in range(N-2):
        if isFlag == True:
            break
        if s[i0] == key[0]:
            for i1 in range(i0+1, N-1):
                if isFlag == True:
                    break
                if s[i1] == key[1]:
                    for i2 in range(i1+1, N):
                        if s[i2] == key[2]:
                            cnt += 1     #; print(i0, i1, i2, key)
                            isFlag = True
                            break
                        
print(cnt)            

# Optimized solution
N = int(eval(input()))
s  = input().strip()

cnt = 0
for key in range(1000):
    key = '{:0>3}'.format(str(key))    #; print(key)
    i0 = s.find(key[0])
    if 0 <= i0 < N-2:
        i1 = s.find(key[1], i0+1)
        if 0 < i1 < N-1:
            i2 = s.find(key[2], i1+1)
            if i2 != -1:
                cnt += 1
            else:
                continue
        else:
            continue        
    else:
        continue
                                   
print(cnt)
# Original solution
#!/usr/bin/env python3
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)

N = int(readline())
S = readline()
count = 0
for i in range(0,1000):
    c = (i//100,(i//10)%10,i%10)
    f = 0
    for j in range(0,N):
        if int(S[j]) == int(c[f]):
            f += 1
        if f == 3:
            break
    if f == 3:
        count += 1
            
print(count)

# Optimized solution
#!/usr/bin/env python3
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)

N = int(readline())
S = readline()
count = 0
for i in range(10):
    a = S.find(str(i))
    if a == -1: 
        continue
    for j in range(10):
        b = S.find(str(j),a+1)
        if b == -1: 
            continue
        for k in range(10):
            c = S.find(str(k),b+1)
            if c != -1: count +=1
print(count)
# Original solution
# coding: utf-8


def solve(*args: str) -> str:
    n = int(args[0])
    s = args[1]
    ret = 0
    for i in range(1000):
        iii = '{:03d}'.format(i)
        j = 0
        for k in range(n):
            if s[k] == iii[j]:
                j += 1
                if j == 3:
                    ret += 1
                    break

    return str(ret)


if __name__ == "__main__":
    print((solve(*(open(0).read().splitlines()))))


# Optimized solution
# coding: utf-8


def solve(*args: str) -> str:
    n = int(args[0])
    s = args[1]
    ret = 0

    index = [[] for _ in range(10)]
    for i in range(n):
        index[int(s[i])].append(i)

    for i in range(1000):
        iii = '{:03d}'.format(i)
        cur = -1
        found = False

        for e, j in enumerate(iii):
            found = False

            for k in index[int(j)]:
                if cur < k:
                    found = True
                    cur = k
                    break

            if not found:
                break

        if found:
            ret += 1

    return str(ret)


if __name__ == "__main__":
    print((solve(*(open(0).read().splitlines()))))
# Original solution
import sys

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip() # ignore trailing spaces 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))

def sumitrust2019_d(a,b,c,s):
    a,b,c = list(map(str,[a,b,c]))
    for idx_a in range(len(s)-2):
        if s[idx_a] == a:
            for idx_b in range(idx_a+1,len(s)-1):
                if s[idx_b] == b:
                    for idx_c in range(idx_b+1,len(s)):
                        if s[idx_c] == c:
                                return True
    else:
        return False

def main():
    n = ni()
    s = ns()
    ans = 0
    for a in range(10):
        for b in range(10):
            for c in range(10):
                if sumitrust2019_d(a,b,c,s):
                    ans += 1
    print(ans)
    return

if __name__ == '__main__':
    main()

# Optimized solution
import sys

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip() # ignore trailing spaces 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))

def sumitrust2019_d(a,b,c,s):
    abc = list(map(str,[a,b,c]))
    now = 0
    for i in range(len(s)):
        if s[i] == abc[now]:
            now += 1
            if now == 3:
            	return True
    return False

def main():
    n = ni()
    s = ns()
    ans = 0
    for a in range(10):
        for b in range(10):
            for c in range(10):
                if sumitrust2019_d(a,b,c,s):
                    ans += 1
    print(ans)
    return

if __name__ == '__main__':
    main()
# Original solution
import sys
from itertools import product
from string import digits

def main():
    n, s = sys.stdin.read().split()
    n = int(n)

    cand = list(''.join(p) for p in product(digits, repeat=3))

    res = set()
    for c in cand:
        i = s.find(c[0])
        if i == -1:
            continue
        j = s.find(c[1], i+1)
        if j == -1:
            continue
        k = s.find(c[2], j+1)
        if k == -1:
            continue
        
        res.add(c)
        
    ans = len(res)
    print(ans)

if __name__ == '__main__':
    main()

# Optimized solution
import sys
from string import digits

def main():
    n, s = sys.stdin.read().split()

    res = []
    for i in digits:
        x = s.find(i)
        if x == -1:
            continue
        for j in digits:
            y = s.find(j, x+1)
            if y == -1:
                continue
            for k in digits:
                z = s.find(k, y+1)
                if z == -1:
                    continue
                res.append((i, j, k))

    print((len(res)))

if __name__ == '__main__':
    main()
# Original solution
import sys
from string import digits

def main():
    n, s = sys.stdin.read().split()
    n = int(n)

    place = dict((i, set()) for i in digits)
    for i in range(n):
        place[s[i]].add(i)

    l = [None] * n
    l[0] = set()
    for i in range(1, n):
        l[i] = l[i-1] | set([s[i-1]])
    
    r = [None] * n
    r[n-1] = set()
    for i in range(n-2, -1, -1):
        r[i] = r[i+1] | set([s[i+1]])

    res = set()
    for j in digits:
        for c in place[j]:
            for i in digits:
                if i in l[c]:
                    for k in digits:
                        if k in r[c]:
                            res.add((i, j, k))
    
    print((len(res)))


if __name__ == '__main__':
    main()

# Optimized solution
import sys
from string import digits

def main():
    n, s = sys.stdin.read().split()
    n = int(n)

    place = dict((i, set()) for i in digits)
    for i in range(n):
        place[s[i]].add(i)

    l = [None] * n
    l[0] = set()
    for i in range(1, n):
        l[i] = l[i-1] | set([s[i-1]])
    
    r = [None] * n
    r[n-1] = set()
    for i in range(n-2, -1, -1):
        r[i] = r[i+1] | set([s[i+1]])

    res = set()
    for j in digits:
        for i in digits:
            for k in digits:
                for c in place[j]:
                    if not i in l[c]:
                        continue
                    if not k in r[c]:
                        continue
                    res.add((i, j, k))
                    break
    print((len(res)))


if __name__ == '__main__':
    main()
# Original solution
import sys
from string import digits

def main():
    n, s = sys.stdin.read().split()
    n = int(n)

    place = dict((i, set()) for i in digits)
    for i in range(n):
        place[s[i]].add(i)

    l = [None] * n
    l[0] = set()
    for i in range(1, n):
        l[i] = l[i-1] | set([s[i-1]])
    
    r = [None] * n
    r[n-1] = set()
    for i in range(n-2, -1, -1):
        r[i] = r[i+1] | set([s[i+1]])

    res = set()
    for j in digits:
        for i in digits:
            for k in digits:
                for c in place[j]:
                    if not i in l[c]:
                        continue
                    if not k in r[c]:
                        continue
                    res.add((i, j, k))
                    break
    print((len(res)))


if __name__ == '__main__':
    main()

# Optimized solution
import sys
from string import digits

def main():
    n, s = sys.stdin.read().split()
    n = int(n)

    place = dict((i, list()) for i in digits)
    for i in range(n):
        place[s[i]].append(i)

    l = [None] * n
    l[0] = set()
    for i in range(1, n):
        l[i] = l[i-1] | set([s[i-1]])
    
    r = [None] * n
    r[n-1] = set()
    for i in range(n-2, -1, -1):
        r[i] = r[i+1] | set([s[i+1]])

    res = set()
    for j in digits:
        p = place[j]
        if not p:
            continue
        for i in digits:
            for k in digits:
                for c in p:
                    if not k in r[c]:
                        break
                    if not i in l[c]:
                        continue
                    res.add((i, j, k))
                    break
    print((len(res)))

if __name__ == '__main__':
    main()
# Original solution
import sys
from string import digits

def main():
    n, s = sys.stdin.read().split()
    n = int(n)

    place = dict((i, list()) for i in digits)
    for i in range(n):
        place[s[i]].append(i)

    l = [None] * n
    l[0] = set()
    for i in range(1, n):
        l[i] = l[i-1] | set([s[i-1]])
    
    r = [None] * n
    r[n-1] = set()
    for i in range(n-2, -1, -1):
        r[i] = r[i+1] | set([s[i+1]])

    res = set()
    for j in digits:
        p = place[j]
        if not p:
            continue
        for i in digits:
            for k in digits:
                for c in p:
                    if not k in r[c]:
                        break
                    if not i in l[c]:
                        continue
                    res.add((i, j, k))
                    break
    print((len(res)))

if __name__ == '__main__':
    main()

# Optimized solution
import sys
from string import digits

def main():
    n, s = sys.stdin.read().split()

    cnt = 0
    for i in digits:
        x = s.find(i)
        if x == -1:
            continue
        for j in digits:
            y = s.find(j, x + 1)
            if y == -1:
                continue
            for k in digits:
                z = s.find(k, y + 1)
                if z == -1:
                    continue
                cnt += 1

    print(cnt)

if __name__ == '__main__':
    main()
# Original solution
import bisect
import collections

def read():
    N = int(input().strip())
    S = str(input().strip())
    return N, S

def dig(S, T, N):
    for i in range(N):
            if S[i] == T[0]:
                for j in range(i+1, N):
                    if S[j] == T[1]:
                        for k in range(j+1, N):
                            if S[k] == T[2]:
                                return True
    return False


def solve(N, S):
    d = [collections.deque() for i in range(10)]
    count = 0
    for p in range(1000):
        T = '{:03d}'.format(p)
        count += 1 if dig(S, T, N) else 0
        
    return count
    
if __name__ == '__main__':
    inputs = read()
    output = solve(*inputs)
    print(("%d" % output))


# Optimized solution
import bisect
import collections

def read():
    N = int(input().strip())
    S = str(input().strip())
    return N, S

def dig(S, T, N):
    k0, k1, k2 = -1, -1, -1
    for i in range(N):
        if S[i] == T[0]:
            k0 = i
            break
    if k0 == -1:
        return False
    for i in range(k0+1, N):
        if S[i] == T[1]:
            k1 = i
            break
    if k1 == -1:
        return False
    for i in range(k1+1, N):
        if S[i] == T[2]:
            k2 = i
            break
    if k2 == -1:
        return False
    return True


def solve(N, S):
    d = [collections.deque() for i in range(10)]
    count = 0
    for p in range(1000):
        T = '{:03d}'.format(p)
        count += 1 if dig(S, T, N) else 0
    return count
    
if __name__ == '__main__':
    inputs = read()
    output = solve(*inputs)
    print(("%d" % output))
# Original solution
import sys
import itertools
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N = int(eval(input()))
S = input().rstrip()

s = set()
l = list(itertools.combinations(S, 3))

for x in l:
    s.add(x[0]+x[1]+x[2])

print((len(s)))


# Optimized solution
import sys
import itertools
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N = int(eval(input()))
S = input().rstrip()

s = set()


for i in range(0, N-2):
    for j in range(i+1, N-1):
        for k in range(j+1, N):
            s.add(S[i]+S[j]+S[k])

print((len(s)))