Problem:


Score: 400 points

Problem Statement

AtCoder Inc. has decided to lock the door of its office with a 3-digit PIN code.

The company has an N-digit lucky number, S. Takahashi, the president, will erase N-3 digits from S and concatenate the remaining 3 digits without changing the order to set the PIN code.

How many different PIN codes can he set this way?

Both the lucky number and the PIN code may begin with a 0.

Constraints

4 \leq N \leq 30000

S is a string of length N consisting of digits.

Input

Input is given from Standard Input in the following format:

N
S

Output

Print the number of different PIN codes Takahashi can set.

Sample Input 1

4
0224

Sample Output 1

3

Takahashi has the following options:

Erase the first digit of S and set 224.

Erase the second digit of S and set 024.

Erase the third digit of S and set 024.

Erase the fourth digit of S and set 022.

Thus, he can set three different PIN codes: 022, 024, and 224.

Sample Input 2

6
123123

Sample Output 2

17

Sample Input 3

19
3141592653589793238

Sample Output 3

329



Sample input:
4
0224


Sample output:
3

Submission status: Accepted

Solution code:
# coding: utf-8

import sys
import math
import collections
import itertools
from inspect import currentframe
INF = 10 ** 10
MOD = 10 ** 9 + 7
def input() : return sys.stdin.readline().strip()
def gcd(x, y) : return y if x % y == 0 else gcd(y, x % y)
def lcm(x, y) : return (x * y) // gcd(x, y)
def I() : return int(input())
def MI() : return map(int, input().split())
def LI() : return [int(x) for x in input().split()]
def RI(N) : return [int(input()) for _ in range(N)]
def LRI(N) : return [[int(x) for x in input().split()] for _ in range(N)]
def chkprint(*args) : names = {id(v):k for k,v in currentframe().f_back.f_locals.items()}; print(', '.join(names.get(id(arg),'???')+' = '+repr(arg) for arg in args))

N = I()
S = input()

cnt = 0
for a in range(10):
    aa = S.find(str(a))
    if aa == -1:
        continue

    for b in range(10):
        bb = S.find(str(b), aa + 1)
        if bb == -1:
            continue

        for c in range(10):
            cc = S.find(str(c), bb + 1)
            # print(a,b,c,end=", ")
            if cc != -1:
                cnt += 1
                # print(a,b,c,end=", ")

print(cnt)

Submission status: Accepted

Solution code:
from itertools import product
from bisect import bisect_left
from collections import defaultdict
N = int(input())
S = list(input())
S = [int(c) for c in S]
dic = defaultdict(list)
seq = [i for i in range(10)]
com = product(seq,repeat=3)
ans = 0
for i in range(N):
  dic[S[i]] += [i]

for x,y,z in com:
  if x==y and y==z:
    if len(dic[x])>2:
      ans += 1
      continue
  elif x==y:
    if len(dic[x])>1 and len(dic[z])>0:
      j = bisect_left(dic[x],dic[z][-1])
      if j>1:
        ans += 1
  elif y==z:
    if len(dic[x])>0 and len(dic[y])>1:
      j = bisect_left(dic[x],dic[y][-2])
      if 0<j:
        ans += 1
  elif x==z:
    if len(dic[x])>1 and len(dic[y])>0:
      h = bisect_left(dic[y], dic[x][-1])
      if h==0:
        continue
      j = bisect_left(dic[x], dic[y][h-1])
      if j>0:
        ans += 1
  else:
    if len(dic[x])>0 and len(dic[y])>0 and len(dic[z])>0:
      h = bisect_left(dic[y], dic[z][-1])
      if h==0:
        continue
      j = bisect_left(dic[x], dic[y][h-1])
      if j>0:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
keta = int(input())
s = input()

total = 0
for i in range(1000):
    str_i = str(i)
    if i < 100:
        str_i = "0" + str_i
    if i < 10:
        str_i = "0" + str_i
    tmp0 = s.find(str_i[0])
    if tmp0 >= 0:
        tmp1 = s[tmp0+1:].find(str_i[1])
        if tmp1 >= 0:
            tmp2 = s[tmp0+1+tmp1+1:].find(str_i[2])
            if tmp2 >= 0:
                total += 1

print(total)

Submission status: Accepted

Solution code:
import bisect
N=int(input())
S=input()

d=dict()
c=0
for i in range(10):
    d[i] = []
for i,s in enumerate(S):
    d[int(s)].append(i)
for i in range(1000):
    s=str(i).zfill(3)
    x=int(s[0])
    y=int(s[1])
    z=int(s[2])
    if len(d[x]) == 0:
        pass
    else:
        try:
            p1 = d[x][0]      
            p2 = d[y][bisect.bisect_right(d[y],p1)]
            p3 = d[z][bisect.bisect_right(d[z],p2)]

            if p3 < N:
                #print(x,y,z,p1,p2,p3)
                c += 1
            else:
                pass
        except:
            pass
print(c)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
N = int(input())
S = input()

dp1 = [False for i in range(10)]
dp2 = [False for i in range(100)]
dp3 = [False for i in range(1000)]

for i, ss in enumerate(S):
    s = int(ss)
    if i>1:
        for i3 in range(0, 100):
            if dp2[i3]:
                dp3[i3*10+s] = True
    if i>0:
        for i2 in range(0, 10):
            if dp1[i2]:
                dp2[i2*10+s] = True
    dp1[s] = True

# for i, d in enumerate(dp3):
#     if d:
#         print(i)

# print(sum(dp1)+sum(dp2)+sum(dp3))
print(sum(dp3))

Submission status: Accepted

Solution code:
N=int(input())
S=list(map(int,list(input())))
#print(S)

A=[[] for i in range(10)]

for i in range(N):
  A[S[i]].append(i)
#print(A)

cnt=0
for a in range(10):
  if len(A[a])==0:
    continue
  for c in range(10):
    if len(A[c])==0:
      continue
    cnt+=len(set(S[A[a][0]+1:A[c][-1]]))
print(cnt)

Submission status: Accepted

Solution code:
n = int(input())
s = input()
# memo_ls[i][j] : i番目まででj+1桁のパスワードを作る通り
pos_dict = dict()
for i, _s in enumerate(s):
    if pos_dict.get(_s) is None:
        pos_dict[_s] = []
    pos_dict[_s].append(i)
memo_ls = [[0 for j in range(3)] for i in range(n+1)]
memo_ls[1][0] = 1
ct = dict()
for i in range(1,n+1):
    _s = s[i-1]
    if _s not in ct:
        memo_ls[i][0] = memo_ls[i-1][0] + 1
        ct[_s] = []
    else:
        memo_ls[i][0] = memo_ls[i - 1][0]
    last_s_i = ct[_s]
    if len(last_s_i) > 0:
        memo_ls[i][1] = memo_ls[i-1][1] + memo_ls[i-1][0] - memo_ls[last_s_i[-1]-1][0]
    else:
        memo_ls[i][1] = memo_ls[i - 1][1] + memo_ls[i - 1][0]
    if(len(last_s_i)) > 0:
        memo_ls[i][2] = memo_ls[i - 1][2] + memo_ls[i - 1][1] - memo_ls[last_s_i[-1]-1][1]
    else:
        memo_ls[i][2] = memo_ls[i - 1][2] + memo_ls[i - 1][1]
    ct[_s].append(i)
print(memo_ls[-1][-1])

Submission status: Accepted

Solution code:
import collections
import bisect
N = int(input())
S = list(input())

dp = [[0]*10 for i in range(N)]


table = collections.defaultdict(list)


for i in range(N):
    table[int(S[i])].append(i)

ans = 0
for x in range(10):
    if x not in table:
        continue
    i = table[x][0]
    for y in range(10):
        if y not in table:
            continue
        idy = bisect.bisect_left(table[y], i + 1)
        if idy < len(table[y]):
            idy = table[y][idy]
            for z in range(10):
                if z not in table:
                    continue
                idz = bisect.bisect_left(table[z], idy+1)
                if idz < len(table[z]):
                    ans += 1
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
import copy
S=list(input())
F=[]
E=[]
L=[0 for i in range(10)]
for i in range(N):
    L[int(S[i])]=1
    F.append(copy.deepcopy(L))
#print(F)
RS=S[::-1]
L=[0 for i in range(10)]
for i in range(N):
    L[int(RS[i])]=1
    E.append(copy.deepcopy(L))
E=E[::-1]
D={}
for i in range(1,N-1):
    for f in range(10):
        if F[i-1][f]==1:
            for e in range(10):
                if E[i+1][e]==1:
                    if (f,S[i],e) not in D:
                        D[(f,S[i],e)]=1
print(len(D))
    
#print(E)

Submission status: Accepted

Solution code:
N = int(input())
S = input()

from bisect import *
from collections import defaultdict

res = defaultdict(list)

for i in range(len(S)):
    s = S[i]
    res[int(s)].append(i)

for i in range(10):
    res[i].append(10000000)
ans = set()
for i in range(10):
    for j in range(10):
        for k in range(10):
            if len(res[i]) > 1 and len(res[j]) > 1 and len(res[k]) > 1:
                tmp = str(i) + str(j) + str(k)
                # print(i, j, k)
                f = res[i][0]
                s_i = bisect_left(res[j], f + 1)
                if s_i != len(res[j]) - 1:
                    s = res[j][s_i]
                else:
                    continue
                t_i = bisect_left(res[k], s + 1)
                if t_i != len(res[k]) - 1:
                    t = res[k][t_i]
                else:
                    continue
                if f < s < 10000000 and s < t < 10000000:
                    ans.add(tmp)
print(len(ans))

Submission status: Accepted

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

stdin = sys.stdin
 
ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

# 上限は1000
N = ri()
S = list(rs())
answer = set()
se1 = set()
for i in range(len(S)-2):
    x = S[i]
    if x in se1:
        continue
    se1.add(x)
    se2 = set()
    for j in range(i+1, len(S)-1):
        y = S[j]
        if y in se2:
            continue
        se2.add(y)
        se = set(S[j+1:])
        for z in se:
            answer.add((x, y, z))

print(len(answer))

Submission status: Accepted

Solution code:
from bisect import bisect_right

n = int(input())
s = input()

ans = 0

pos = [
    [] for _ in range(10)
]


def find_gt(a, x):
    'Find leftmost value greater than x'
    i = bisect_right(a, x)
    if i != len(a):
        return a[i]
    return None


for j in range(n):
    pos[int(s[j])].append(j)

for i in range(1000):
    t = '000' + str(i)
    t = t[-3:]
    a, b, c = map(int, tuple(t))

    p = -1
    p = find_gt(pos[a], p)
    if p is None:
        continue
    q = find_gt(pos[b], p)
    if q is None:
        continue
    r = find_gt(pos[c], q)
    if r is None:
        continue

    ans += 1

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
s = input()
one = [False for _ in range(10)]
two = [False for _ in range(100)]
three = [False for _ in range(1000)]
for i in range(n):
	x = int(s[i])
	for j in range(100):
		if three[j*10+x]:
			continue
		if two[j]:
			three[j*10+x] = True
	for j in range(10):
		if two[j*10+x]:
			continue
		if one[j]:
			two[j*10+x] = True
	one[x] = True
print(sum(three))

Submission status: Accepted

Solution code:
n = int(input())
s = input()
count = 0
for i in range(0, 1000):
    pin = '{0:03d}'.format(i)
    pos1 = s.find(pin[0])
    pos2 = s.find(pin[1], pos1 + 1)
    pos3 = s.find(pin[2], pos2 + 1)
    if pos1 != -1 and pos2 != -1 and pos3 != -1:
        count += 1
print(count)

Submission status: Accepted

Solution code:
from collections import defaultdict

N = int(input())
S = input()

dp = defaultdict(int)
d1 = {S[0], S[1], S[2]}
d2 = {S[0:2], S[1:3], S[0] + S[2]}
pin = {S[0:3]}
for i in range(3, N):
    s = S[i]
    for d in d2:
        pin.add(d + s)
    for d in d1:
        d2.add(d + s)
    d1.add(s)
print(len(pin))

Submission status: Accepted

Solution code:
n = int(input())
s = input()
res = [[None for j in range(10)] for i in range(n)]
res[-1][int(s[-1])] = n - 1
for i in range(n - 2, -1, -1):
    for j in range(10):
        res[i][j] = res[i + 1][j]
    res[i][int(s[i])] = i
ans = 0
for i in range(10):
    x = res[0][i]
    if x is None or x > n - 3:
        continue
    for j in range(10):
        y = res[x + 1][j]
        if y is None or y > n - 2:
            continue
        for k in range(10):
            z = res[y + 1][k]
            if z is not None:
                ans += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools
n=int(input())
S=input()
L=list(itertools.product(range(10),repeat=3))
N=[''.join(str(c) for c in l) for l in L]
x=0
for n in N:
  if n[0] in S:
    a=S.index(n[0])+1
    if n[1] in S[a:]:
      b=S[a:].index(n[1])+a+1
      if n[2] in S[b:]:
        x+=1
print(x)

Submission status: Accepted

Solution code:
n=int(input())
S=input()
ans=0
sublist=[]
for i in range(100):
    used=0
    j="0"*(2-len(str(i)))+str(i)
    flag1=False
    flag2=False
    for i in range(n):
        if not flag1 and S[i]==j[0]:
            flag1=True
            continue
        if flag1 and not flag2:
            if S[i]==j[1]:
                flag2=True
                used=i+1
    if flag2:
        sublist.append((j,used))
anslist=[]
for some in sublist:
    a1=some[0]
    index=some[1]
    lis=[0 for i in range(10)]
    for j in range(index,n):
        anslist.append(a1+S[j])
anslist=set(anslist)
print(len(anslist))

Submission status: Accepted

Solution code:
import math

array_size = int(input())
#array = list(map(int,list(input())))
array = str(input())
#num = math.factorial(array_size)/math.factorial(3)
count = 0
for i in range(1000):
    tf = 1
    i = list(map(int,list(str(i))))
    if len(i) < 3:
        i.insert(0,0)
        if len(i) < 3:
            i.insert(0,0)
    index = -1
    for j in i:
        j = str(j)
        index = array.find(j,index+1)
        if index == -1:
            tf = 0
            break
    if tf == 1:
        count+=1
        #print(i)
print(count)

Submission status: Accepted

Solution code:
n = int(input())
s = input()
ans = 0

def my_index(l, x, default=-1):
    if x in l:
        return l.index(x)
    else:
        return default
      
for i in range(1000):
  ss = str(i)
  if len(ss) == 1:
    ss = "00" + ss
  elif len(ss) == 2:
    ss = "0" + ss
  k = my_index(s, ss[0])
  if k < 0:
    continue
  else:
    kk = my_index(s[k+1:], ss[1])
    if kk < 0:
      continue
    else:
      kkk = my_index(s[k+1:][kk+1:], ss[2])
      if kkk < 0:
        continue
      else:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
S=input()

ans=0
for i in range(10):
  i=str(i)
  ind=S.find(i)
  if ind<0:
    continue
  S2=S[ind+1:]
  for j in range(10):
    j=str(j)
    j_ind=S2.find(j)
    if j_ind<0:
      continue
    S3=S2[j_ind+1:]
    ans+=len(set(S3))
    
print(ans)

Submission status: Accepted

Solution code:

class SegmentTree:

    def __init__(self, n, fn=lambda x, y: min(x, y), unity=(1 << 31) - 1):
        self.n = 1
        while self.n < n:
            self.n *= 2

        self.arr = [unity] * (2 * self.n - 1)
        self.fn = fn
        self.unity = unity

    def update(self, i, x):
        k = self.n + i - 1
        self.arr[k] = x

        while k > 0:
            k = (k - 1) // 2
            self.arr[k] = self.fn(self.arr[2 * k + 1], self.arr[2 * k + 2])

    def query(self, l, r):
        return self._inner_query(l, r, 0, 0, self.n)

    def _inner_query(self, l, r, k, il, ir):
        if ir <= l or r <= il:
            return self.unity

        elif l <= il and ir <= r:
            return self.arr[k]

        vl = self._inner_query(l, r, k * 2 + 1, il, (il + ir) // 2)
        vr = self._inner_query(l, r, k * 2 + 2, (il + ir) // 2, ir)
        return self.fn(vl, vr)

    def __str__(self):
        return self.arr[0: 2 * self.n].__str__()

N = int(input())
S = list(input())

sts = [SegmentTree(N + 1, fn=lambda x, y: max(x, y), unity=0) for _ in range(10)]

minmax = [(N + 1, 0) for _ in range(10)]

for i in range(N):
    c = int(S[i])
    sts[c].update(i, 1)
    minmax[c] = (min(minmax[c][0], i), max(minmax[c][1], i))

cnt = 0
for l in range(10):
    for r in range(10):
        for c in range(10):
            if sts[c].query(minmax[l][0] + 1, minmax[r][1]) > 0:
                cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
import bisect
n = int(input())
s = input()
s_list = [[] for _ in range(10)]
for i in range(n):
    s_list[int(s[i])].append(i)
for i in range(10):
    s_list[i].sort()

can_use = [[0 for _ in range(10)] for _ in range(10)]

ans = 0
for i in range(1000):
    thisS = str(i)
    while len(thisS) < 3:
        # print(thisS)
        thisS = "0" + thisS

    if len(s_list[int(thisS[0])]) == 0:
        continue
    now_point = s_list[int(thisS[0])][0]
    # print(thisS, now_point)
    tmp = 0
    for j in range(2):
        tmp = 0
        now = int(thisS[j])
        next = int(thisS[j + 1])
        for k in range(len(s_list[next])):
            if s_list[next][k] > now_point:
                now_point = s_list[next][k]
                tmp = 1
                break
        if tmp == 0:
            break
    ans += tmp

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = list(map(int,input()))
c = [False]*10
con = [False]*100
pas = [False]*1000

for k in S:
    for i in range(100):
        if con[i]:
            pas[i*10+k] = True
    if c[0]:
        con[k] = True
    if c[1]:
        con[10+k] = True
    if c[2]:
        con[20+k] = True
    if c[3]:
        con[30+k] = True
    if c[4]:
        con[40+k] = True
    if c[5]:
        con[50+k] = True
    if c[6]:
        con[60+k] = True
    if c[7]:
        con[70+k] = True
    if c[8]:
        con[80+k] = True
    if c[9]:
        con[90+k] = True
    c[k] = True
ans = 0
for p in pas:
    if p:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, S):
    idx = defaultdict(list)
    for i, s in enumerate(S):
        idx[int(s)].append(i)

    ans = 0
    for i in range(0, 10):
        if not idx[i]:
            continue
        l = idx[i][0]
        for j in range(0, 10):
            if not idx[j]:
                continue
            ll = bisect.bisect_right(idx[j], l)
            if ll == len(idx[j]):
                continue
            ll = idx[j][ll]
            for k in range(0, 10):
                if not idx[k]:
                    continue
                lll = bisect.bisect_right(idx[k], ll)
                if lll != len(idx[k]):
                    ans += 1

    return ans


def main():
    N = read_int()
    S = read_str()
    print(slv(N, S))

    # N = 300000
    # S = '0123456789' * (N //10)
    # print(slv(N, S))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def umeru(x):#x Z
    s = str(x)
    return  '0'*(3-len(s))+s

def search(s,S):
    ok = 0
    for i in range(len(S)):
        point = s[ok]
        if S[i]==point:
            ok +=1
        if ok==3:
            return True
    return False
n = input()
S = input()
count = 0
for i in range(1000):
    s = umeru(i)
    if search(s,S):
        count +=1
print(count)

Submission status: Accepted

Solution code:
N = int(input()) # 数字を変数に格納
S = input() # 文字列を変数に格納

List_1 = [0] * 10
List_2 = [[0] * 10 for i in range(10)]
List_3 = [[[0] * 10 for i in range(10)] for j in range(10)]

sum = 0
first = 0
second = 0
third = 0

for i in range(0,N-2):
    first = int(S[i])
    if List_1[first] == 0:
        List_1[first] = 1
        for j in range(i+1,N-1):
            second = int(S[j])
            if List_2[first][second] == 0:
                List_2[first][second] = 1
                for k in range(j+1,N):
                    third = int(S[k])
                    if List_3[first][second][third] == 0:
                        List_3[first][second][third] = 1
                        
for i in range(10):
    for j in range(10):
        for k in range(10):
            sum += List_3[i][j][k]

print(sum)

Submission status: Accepted

Solution code:
N = int(input())
S = [int(i) for i in input()]

ans = 0
R = [0]*N
L = [0]*N
memoR = [S[N-1]]
memoL = [S[0]]
L[0] = 1
R[N-1] = 1
count = [0]*10

for i in range(1,N):
  L[i] = L[i-1]
  if S[i] not in memoL:
    L[i] +=1
    memoL.append(S[i])
for i in range(N-2,-1,-1):
  R[i] = R[i+1]
  if S[i] not in memoR:
    R[i] += 1
    memoR.append(S[i])
    
for i in range(1,N-1):
  if L[i-1] > count[S[i]]:
    ans += (L[i-1]-count[S[i]])*R[i+1]
    count[S[i]] = L[i-1]
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
t=list(str(input()))
s=[]
for i in range(n):
    s.append(int(t[i]))
g=[[0 for i in range(10)] for j in range(10)]
r=[0 for j in range(n+1)]
l=[0 for j in range(n+1)]
for i in range(n):
    if r[i]&(2**s[i])==0:
        r[i+1]=r[i]+2**s[i]
    else:
        r[i+1]=r[i]
    if l[n-i]&(2**s[n-i-1])==0:
        l[n-i-1]=l[n-i]+2**s[n-i-1]
    else:
        l[n-i-1]=l[n-i]
ans=[[[0 for i in range(10)] for j in range(10)] for k in range(10)]
for i in range(n):
    for j in range(10):
        for k in range(10):
            if r[i]&(2**j) and l[i+1]&(2**k):
                ans[j][s[i]][k]+=1
kai=0
for i in range(10):
    for j in range(10):
        for k in range(10):
            if ans[i][j][k]>0:
                kai+=1
print(kai)

Submission status: Accepted

Solution code:
N = int(input())
s = input()
l = {}
a = [{} for i in range(N)]
a[-1] = {s[-1]: N-1}

for i in range(N-2, -1 , -1):
  a[i] = a[i+1].copy()
  a[i].update({s[i]: i})

r = 0
for k1, v1 in a[0].items():
  if v1 >= N - 2: continue
  for k2, v2 in a[v1+1].items():
    if v2 >= N - 1 : continue
    r += len(a[v2+1].keys())

print(r)

Submission status: Accepted

Solution code:
_ = input()
s = input()

count = 0
for i in range(0, 1000):
    ans = '{:03d}'.format(i)
    idx = s.find(ans[0])
    if idx == -1:
        continue
    else:
        s1 = s[idx+1:]
        idx = s1.find(ans[1])
        if idx == -1:
            continue
        else:
            s2 = s1[idx+1:]
            idx = s2.find(ans[2])
            if idx != -1:
                count += 1
print(count)

Submission status: Accepted

Solution code:
N = int(input())
S = input()

count = 0
count_dict = {}
for s in S:
    for k, v in count_dict.items():
        for k2, v2 in v.items():
            if s not in v2:
                v2.append(s)
                count += 1
        if s not in v.keys():
            v[s] = []
    if s not in count_dict.keys():
        count_dict[s] = {}

# print(count_dict)
print(count)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
ss = set(S)
ans = 0
for i in range(1000):
    cur_index = 0
    for p in "{:03d}".format(i):
        if p not in ss:
            break
        try:
            idx = S[cur_index:].index(p)
        except:
            break
        else:
            cur_index += idx + 1
    else:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = input()

count = 0

for i in range(10):
    c = S.find(str(i))
    if c > -1:
        for j in range(10):
            d = S[c + 1:].find(str(j))
            if d > -1:
                for k in range(10):
                    e = S[c + 1 + d + 1:].find(str(k))
                    if e > -1:
                        count += 1
print(count)

Submission status: Accepted

Solution code:
def solve():
    N = int(input())
    S = list(input())
    ans = 0

    i_tmp = []
    j_tmp = []
    for i in range(N-2):
        if S[i] in i_tmp:
            continue
        else:
            i_tmp.append(S[i])
            j_tmp.clear()
        for j in range(i+1, N-1):
            if S[j] in j_tmp:
                continue
            else:
                j_tmp.append(S[j])
                ans += len(set(S[j+1:]))
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
n = int(input())
s = input()

c = 0
for i in range(1000):
  a = str(i).zfill(3)  
  n0 = s.find(a[0])
  if n0==-1:
    continue
  n1 = s.find(a[1], n0+1)
  if n1==-1:
    continue
  n2 = s.find(a[2], n1+1)
  if n2!=-1:
    c += 1
print(c)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
s0,s1,s2 = int(S[0]),int(S[1]),int(S[2])
C = [0 for i in range(10)]
D = [0 for i in range(100)]
E = [0 for i in range(1000)]
C[s0] += 1
C[s1] += 1
C[s2] += 1
D[s0*10+s1] += 1
D[s0*10+s2] += 1
D[s1*10+s2] += 1
E[s0*100+s1*10+s2] += 1
for i in range(3,N):
    s = int(S[i])
    for i in range(100):
        E[10*i+s] =  E[10*i+s]+D[i]
    for i in range(10):
        D[10*i+s] = D[10*i+s]+C[i]
    C[s] += 1
ans = 0
for i in range(1000):
    if E[i] > 0:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    N=int(input())
    S=list(map(int,list(input())))
    z=[None]*10
    for i in range(10):
        for j in range(N-2):
            if S[j]==i:
                 z[i]=j
                 break
    y=[[None]*10 for _ in range(10)]
    for x in range(10):
        if z[x] is not None:
            for i in range(10):
                for j in range(z[x]+1,N-1):
                    if S[j]==i:
                        y[x][i]=j
                        break
    ans=0
    for h in range(10):
        for x in range(10):
            if y[h][x] is not None:
                for i in range(10):
                    for j in range(y[h][x]+1,N):
                        if S[j]==i:
                            ans+=1
                            break
    print(ans)
                

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
def solve():
    N = int(input())
    S = input()
    L1 = [0 for _ in range(10)]
    L2 = [0 for _ in range(100)]
    L3 = [0 for _ in range(1000)]
    for s in S:
        s = int(s)
        L3[s::10] = L2[:]
        L2[s::10] = L1[:]
        L1[s] = 1
    return str(sum(L3))

if __name__ == '__main__':
    print(solve())

Submission status: Accepted

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

N = int(input())
S = input().rstrip()
# X, Y = map(int,input().split())
# Z, W = map(int,input().split())
# vA = list(map(int, input().split()))

dpA = [1,] + [0,]*10
dpB = [0,] * 100
dpC = [0,] * 1000

# dp = [[[1,]+[0,]*10 for _i in range(11)]
#       for _j in range(11)]

for s in S:
    d = int(s)
    for i in range(10):
        for j in range(10):
            if dpB[i*10 + j]:
                dpC[i*100 + j*10 + d] = 1
    for i in range(10):
        if dpA[i+1]:
            dpB[i*10 + d] = 1
    dpA[d+1] = 1
    # print(dpA)##
# print(":(")

# res = 0
# for i in range(10):
#     for j in range(10):
#         res += sum(a>0 for a in dp[i][j][1:])

res = sum(dpC)
print(res)

Submission status: Accepted

Solution code:
from collections import defaultdict

N = int(input())
S = input()
d = defaultdict(list)
for i in range(N):
    d[int(S[i])].append(i)

ans = 0
for i in range(11):
    for j in range(11):
        if d[i] and d[j]:
            left = d[i][0]
            right = d[j][-1]
            if(left+1 < right):
                for k in range(11):
                    for elem in d[k]:
                        if left < elem < right:
                            ans += 1
                            break


print(ans)

Submission status: Accepted

Solution code:
n = int(input())
s = input()

keys = []

for i in range(10):
    i_str = str(i)
    if i_str not in s:
        continue
    else:
        t = s[s.index(i_str)+1:]
        for j in range(10):
            j_str = str(j)
            if j_str not in t:
                continue
            else:
                u = t[t.index(j_str)+1:]
                for k in range(10):
                    k_str = str(k)
                    if k_str in u:
                        keys.append(i_str + j_str + k_str)

print(len(keys))

Submission status: Accepted

Solution code:
n=int(input())
if n<3:
    print(0)
    exit()
if n==3:
    print(1)
    exit()
s=input()
s=[int(i)+1 for i in s]
l=[int(i) for i in s]
l1=[0]*(n+16) 
l2=[0]*(n+13)
l3=[0]*(n+12)
l2[n-1]=1 
l3[s[n-1]-1]=1 
k=3 
for i in range(n-2,-1,-1): 
    l2[i]=l2[i+1]
    if l3[s[i]-1]==0:
        l2[i]+=1 
        l3[s[i]-1]=1 
for j in range(1,k):
    l3=[0]*(n+18)
    l1[n-1]=0 
    for i in range(n-2,-1,-1) : 
        l1[i]=l1[i+1]
        l1[i]=l1[i]+l2[i+1]
        l1[i]=l1[i]-l3[s[i]-1]
        l3[s[i]-1]=l2[i+1]
    l2=l1[:]
print(l1[0])

Submission status: Accepted

Solution code:
import sys
n = int(input())
s = input()
l = []
for i in range(len(s)):
    l.append(s[i])

cnt = 0
for i in range(10):
    if str(i) in l:
        p = l.index(str(i))
        
        for j in range(10):
            if str(j) in l[p+1:]:
                q = l[p+1:].index(str(j))

                for k in range(10):
                    if str(k) in l[p+q+2:]:
                        cnt += 1


print(cnt)

Submission status: Accepted

Solution code:
n = int(input())
s = input()
l = [[],[],[],[],[],[],[],[],[],[]]

for i in range(n):
    l[int(s[i])].append(i)

def hantei(i):
    p = -1
    q = -1

    a = i // 100
    b = i // 10 - a * 10
    c = i - a * 100 - b * 10

    if len(l[a]) == 0:
        return 0
    else:
        p = l[a][0]

    if len(l[b]) == 0:
        return 0
    else:
        for j in range(len(l[b])):
            if l[b][j] > p:
                q = l[b][j]
                break
        if q == -1:
            return 0

    if len(l[c]) == 0:
        return 0
    else:
        for j in range(len(l[c])):
            if l[c][j] > q:
                return 1
    return 0

ans = 0

for i in range(1000):
    ans += hantei(i)

print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
n = int(input())
s = input()
ans = 0

for i in range(1000):
    tmp = str('{:03}'.format(i))
    s0 = s.find(tmp[0])
    if s0 == -1:
        continue
    else:
        s1 = s.find(tmp[1], s0 + 1)
        if s1 == -1:
            continue
        else:
            s2 = s.find(tmp[2], s1 + 1)
            if s2 == -1:
                continue
            else:
                ans += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools


len_lucky = int(input())
lucky = input()

numbers = ("0", "1", "2", "3", "4", "5", "6", "7", "8", "9")

count = 0
for i, j, k in itertools.product(numbers, repeat=3):
    try:
        i_index = lucky.index(i, 0)
        j_index = lucky.index(j, i_index+1)
        k_index = lucky.index(k, j_index+1)
        if min(i_index, j_index, k_index) != -1:
            count += 1
    except ValueError:
        continue

print(count)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

N = int(input())
S = [int(x) for x in list(input().strip())]

nxtind = [[-1]*(N+1) for i in range(10)]

for i in range(N-1,-1,-1):
	si = S[i]
	for j in range(10):
		if j==si:
			nxtind[j][i] = i
		else:
			nxtind[j][i] = nxtind[j][i+1]

ans = 0
for i in range(10):
	ff = nxtind[i][0]
	if ff==-1: continue
	for j in range(10):
		ss = nxtind[j][ff+1]
		if ss==-1: continue
		for k in range(10):
			tt = nxtind[k][ss+1]
			if tt==-1:
				continue
			else:
				ans += 1

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
S = str(input())
r = 0
for i in range(1000):
    t = "{0:03d}".format(i)
    j = 0
    for c in S:
        if t[j] == c:
            j += 1
        if j == 3:
            r += 1
            break
print(r)