Problem:


Score : 400 points

Problem Statement

Given is a string S consisting of digits from 1 through 9.

Find the number of pairs of integers (i,j) (1 ≤ i ≤ j ≤ |S|) that satisfy the following condition:

Condition: In base ten, the i-th through j-th characters of S form an integer that is a multiple of 2019.

Constraints

1 ≤ |S| ≤ 200000

S is a string consisting of digits from 1 through 9.

Input

Input is given from Standard Input in the following format:

S

Output

Print the number of pairs of integers (i,j) (1 ≤ i ≤ j ≤ |S|) that satisfy the condition.

Sample Input 1

1817181712114

Sample Output 1

3

Three pairs - (1,5), (5,9), and (9,13) - satisfy the condition.

Sample Input 2

14282668646

Sample Output 2

2

Sample Input 3

2119

Sample Output 3

0

No pairs satisfy the condition.



Sample input:
1817181712114


Sample output:
3

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
S = str(input())

len_str = len(S)
dp_list = [[-1 for _ in range(len_str)] for _ in range(len_str)]

ans = 0
for i in range(len_str):
    for j in range(i + 4, len_str + 1):
        temp_ans = int(S[i:j]) if i == 0 or j == i + 4 else (dp_list[i][j - 2] * 10 + int(S[j - 1]))
        temp_ans %= 2019
        dp_list[i][j - 1] = temp_ans
        if temp_ans == 0:
            ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = input()
N = len( S )
l = [ str( 2019 * i )  for i in range( 1, 200000 ) if i % 10 != 0 ]
cnt = 0
for i in l:
    if len( i ) > N:
        break
    Sd = S
    if i in S:
        add = Sd.find( i )
        while add != - 1:
            cnt += 1
            Sd = Sd[ add + 1: ]
            add = Sd.find( i )
print( cnt )

Submission status: Time Limit Exceeded

Solution code:

s=input()
su=[0]
j=0
for i in s[::-1]:
    su.append((su[-1]+int(i)*10**j)%2019)
    j+=1

n=len(s)
cnt=0
for i in range(n-3):
    for j in range(i+4,n+1):
        if (su[j]-su[i])/(10**(j-i))%2019==0:
            cnt+=1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def main():
    from builtins import int,range,input,len
    s = input()
    s_l = len(s)
    l = []
    l_a = l.append
    for x in range(s_l):
        for y in range(x+4, s_l+1):
            if not int(s[x:x+y]) % 2019:
                l_a(0)
    print(len(l))

main()

Submission status: Time Limit Exceeded

Solution code:
S=input()
U=int(S)
T=len(S)

list=[]
count=0
for i in range(0,T-3):
  for j in range(i+4,T+1):
    list.append(S[i:j])
list_2 = [int(n) for n in list]
for z in range(len(list_2)):
  if list_2[z]%2019==0:
    count+=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
number = str(input())
print(len([i for i in range(0, len(number)-1) for j in range(4, len(number)+1) if number[i:j] != '' and int(number[i:j])%2019==0]))

Submission status: Time Limit Exceeded

Solution code:
S = str(input())

count = 0
for i in range(0, len(S)):
    for j in range(i+4, len(S)+1):
        if int(S[i:j]) % 2019 == 0:
            count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
S = input()
count = 0
num = len(S)
for i in range(num):
    try:
        for n in range(4,num+1):
            j = i + n
            number = int(S[i:j])
            if number % 2019 == 0:
                if j == len(S)+1:
                    break
                else:
                    count += 1
            else:
                pass
    except IndexError:
        break
print(count)

Submission status: Time Limit Exceeded

Solution code:
S = list(input())
ans = 0


for i in range(len(S)):
  s = S[i]
  for j in range(i + 1, len(S)):
    s  += S[j]
    if int(s) % 2019 == 0:
      ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
S= str(input())
T=S
ans = 0
for i in range(len(S)):
    S= T[i:]
    S = int(S)
    while True:
        if S % 2019 ==0:
            ans = ans+1
        S = S // 10
        if S < 12114:
            break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()
cnt = 0
for i in range(len(s)-4):
    for j in range(len(s)):
        if i >= j:
            continue
        d = int(s[i:j+1])
        if d%2019 == 0:          
            cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
s=input()
ans=0
s_l=0
for i in range(len(s)):
    for j in range(1,len(s)):
        if s_l==int(s[i:i+j+1]):
            continue
        if int(s[i:i+j+1])%2019==0:
            ans+=1
        s_l=int(s[i:i+j+1])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s=input()
n=len(s)
count=0
#for j in range(n-3):
j=0
while j<n-3:
	i=4
	while(i<n-j+1):
	#for i in range(4,n+1-j):
		nu = int(s[j:i+j])
		#print(nu) 
		if nu%2019==0:
			count+=1
			j+=3
			i+=3

		i+=1
	j+=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
N = int(input()) # 1行, 単数

S = str(N)
count = 0
for i in range(len(S) - 3):
  for j in range(int(i+3) , len(S)+1):
    A = int(S[i:j])
    if A % 2019 == 0:
      count+=1

print(count)

Submission status: Time Limit Exceeded

Solution code:
S=input()

out=0
D=len(S)-4
for ii in range(D+1):
    for i in range(ii+3,len(S)):
        T=S[ii:i+1]
        if int(T)%2019==0:
            out+=1
print(out)

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache

s = input()
s_len = len(s)
n = 2019
n_len = len(str(n))
result = 0
a = 202


@lru_cache(maxsize=128)
def reduce_number(s):
    left = int(s[:-1])
    right = a * int(s[-1])
    result = str(left + right)
    return result


@lru_cache(maxsize=128)
def is_multiple(s):
    _s = s
    while True:
        _s = reduce_number(_s)
        _s_int = int(_s)
        if _s_int == n:
            return True
        elif _s_int < n:
            return False


for i in range(s_len - n_len):
    for j in range(i + n_len, s_len + 1):
        m = s[i:j]
        if is_multiple(m):
            result += 1
            break
print(result)

Submission status: Time Limit Exceeded

Solution code:
S = input()
X = [int(i) for i in S]
amari = {i:0 for i in range(2019)}
Y = {i:0 for i in range(2019)}
n1 = {i:(i*10+1)%2019 for i in range(2019)}
n2 = {i:(i*10+2)%2019 for i in range(2019)}
n3 = {i:(i*10+3)%2019 for i in range(2019)}
n4 = {i:(i*10+4)%2019 for i in range(2019)}
n5 = {i:(i*10+5)%2019 for i in range(2019)}
n6 = {i:(i*10+6)%2019 for i in range(2019)}
n7 = {i:(i*10+7)%2019 for i in range(2019)}
n8 = {i:(i*10+8)%2019 for i in range(2019)}
n9 = {i:(i*10+9)%2019 for i in range(2019)}
ans = 0
for i in X:
    nextamari =dict(Y)
    if i == 1:
        for j in n1.keys():
            nextamari[n1[j]] += amari[j]
    elif i == 2:
        for j in n2.keys():
            nextamari[n2[j]] += amari[j]
    elif i == 3:
        for j in n3.keys():
            nextamari[n3[j]] += amari[j]
    elif i == 4:
        for j in n4.keys():
            nextamari[n4[j]] += amari[j]
    elif i == 5:
        for j in n5.keys():
            nextamari[n5[j]] += amari[j]
    elif i == 6:
        for j in n6.keys():
            nextamari[n6[j]] += amari[j]
    elif i == 7:
        for j in n7.keys():
            nextamari[n7[j]] += amari[j]
    elif i == 8:
        for j in n8.keys():
            nextamari[n8[j]] += amari[j]
    elif i == 9:
        for j in n9.keys():
            nextamari[n9[j]] += amari[j]
    if i in nextamari:
        nextamari[i] += 1
    else:
        nextamari[i] = 1
    if 0 in nextamari:
        ans += nextamari[0]
    amari = nextamari
#    for i in nextamari.keys():
#        if nextamari[i] != 0:
#            print(nextamari[i])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()
n = len(s)
ans = 0
ans = sum([sum([1 for j in range(n-i+1) if int(s[j:j+i])%2019 == 0]) for i in range(4, n)])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

input = sys.stdin.readline
s = input()
n = len(s)

b = [int(s[i:j]) for i in range(n - 3) for j in range(i + 3, n)]
c = np.array(b)

print(np.count_nonzero(c % 2019 == 0))

Submission status: Time Limit Exceeded

Solution code:
s = input()
length = len(s)
count_dict = {}

'''for i in range(length-4):
    for j in range(i+4,length+1):
        num = int(s[i:j])
        if num%2019 == 0:
            count += 1'''

num = int(s)%2019
count_dict[num] = 1

# num = int(s[-1])
# count_dict[num] = 1

for i in range(1,length):
    num = (num-int(s[-i])*(10**(i-1)%2019))%2019
    # num = num+int(s[-i])
    if num not in count_dict:
        count_dict[num] = 1
    else:
        count_dict[num] += 1


count = 0
for k,v in count_dict.items():
    count += v*(v-1)/2
    if k == 0:
        count += v

print(int(count))

Submission status: Time Limit Exceeded

Solution code:
s = input()

n = int(s)
j = len(s)
del s
ln = [n % 10**i for i in range(1, j+1)]
s_mod = set()
count = 0
for i in ln:
  amari = i % 2019
  if amari == 0:
    count += 1
  else:
    if amari in s_mod:
      count += 1
    s_mod.add(amari)

print(count)

Submission status: Time Limit Exceeded

Solution code:
s = input()
i = 0

ln = len(s)
cnt = 0
if ln >= 4:
    for i in range(0, ln-2, 1):
        for j in range(i+4, ln+1, 1):
            sstr = ''
            for k in range(i, j, 1):
                sstr = sstr + s[k]
            if int(sstr) % 2019 == 0:
                cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:

s = input()

count = 0

for h in range(0, len(s)):

    for i in range(h, len(s)):
        
        temp = ''

        # 各要素を足す
        for j in range(h, i + 1):
            temp = temp + s[j]

        temp = int(temp)

        if temp % 2019 == 0 :
            count = count + 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

def resolve():
  S_string = input()

  if len(S_string) < 4:
    print("0")
    return True

  d_start = 5
  d_end = len(S_string)

  # counter = Counter([int(S_string[i:i + d]) % 2019 for i in range(0, d_end - d_start - 1) for d in range(d_start, d_end + 1 - i)])
  # count = counter[0]
  count = 0
  for i in range(0, d_end - d_start + 1):
    for d in range(d_start, d_end + 1 - i ):
      # print(int(S_string[i: i + d]))
      if (int(S_string[i: i + d])%2019==0):
        count += 1

  print(count)

if __name__ == "__main__":
  resolve()

Submission status: Time Limit Exceeded

Solution code:
S = str(input())
N = len(S)
cnt = 0

for i in range(N):
    for j in range(i+1,N):
        if int(S[i:j+1]) % 2019 == 0:
            cnt += 1
            
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import itertools
N = input()
f_can = itertools.combinations(range(len(N)+1),2)
print(sum([int(N[int(f):int(b)])%2019==0
         for f,b in f_can]))

Submission status: Time Limit Exceeded

Solution code:
#


def main():
    s = input()
    length = len(s)
    count = 0
    # 愚直な方法ではTLE
    # for i in range(length - 3):
    #     for j in range(i + 4, length + 1):
    #         n = int(s[i:j])
    #         if n % 2019 == 0:
    #             count += 1
    for j in range(length, 4, -1):
        i = j - 4
        while i >= 0:
            n = int(s[i:j])
            if n % 2019 == 0:
                count += 1
                i -= 3
            else:
                i -= 1
    print(count)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 10 ** 9 + 7
N = 10 ** 6  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用
 
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)


import collections
S = input()
Smod = list()
for i in range(len(S)-1, -1, -1):
  S_i = int(S[i:])
  Smod.append(S_i%2019)
c = collections.Counter(Smod)

ans = 0
for amari, kosuu in c.items():
  if(amari == 0):
    ans += cmb(kosuu+1, 2, p)
  elif(kosuu >= 2):
    ans += cmb(kosuu, 2, p)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()
n = len(s)
ans = 0
try:
    for i in range(n):
        for j in range(i+3, n+1):
            if len(s[i:j]) >= 4 :
                if int(s[i:j])%2019 == 0 :
                    ans += 1
except:pass

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

S = list(input().strip())
length = len(S)
op = np.asarray(S)

def checkValue():
    count = 0
    for i in range(length):
        group = ""
        for j in range(i, length):
            group += op[j]
            if int(group) % 2019 == 0:
                count += 1
    print(count)
checkValue()

Submission status: Time Limit Exceeded

Solution code:
from math import log10
from functools import lru_cache

@lru_cache(maxsize=None)
def f(s):
    ans = 0
    while s > 2019:
        if s % 2019 == 0:
            ans += 1
        s //= 10
    return ans

s = int(input().strip())
n = int(log10(s)) + 1
ans = 0

while s > 2019:
    ans += f(s)
    n -= 1
    s %= (10**n)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = str(input())
count = 0
for i in range (len(S)-4):
    for n in range (4, len(S)+1-i):
        j = i + n
        num = int(S[i:j])
        if(num % 2019 == 0):
            count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
S = input()
l = len(S)
ans=0
for i in range(l-4):
    for j in range(i+4,l+1):
        m = int(S[i:j])
        if m%673 ==0:
            if m%3 ==0:
                ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main(): 
  s_str = input()

  num = 0
  for i in tuple(range(0, len(s_str)-4)):
    for j in tuple(range(i+3, len(s_str))):
      tmp_str = s_str[i:j+1]
      if int(tmp_str)%2019==0:
        num+=1
  print(num)

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
S=input()

print(len([(i,j)
    for j in range(len(S))
    for i in range(j+1)
    if sum([int(s) for s in S[i:j+1]])%3==0
        and int(S[i:j+1])%673==0
]))

Submission status: Time Limit Exceeded

Solution code:
import sys
from random import choice,randint
inp=sys.stdin.readline
out=sys.stdout.write
flsh=sys.stdout.flush
 
sys.setrecursionlimit(10**9)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]
 
def MI(): return map(int, inp().strip().split())
def LI(): return list(map(int, inp().strip().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines().strip()]
def LI_(): return [int(x)-1 for x in inp().strip().split()]
def LF(): return [float(x) for x in inp().strip().split()]
def LS(): return inp().strip().split()
def I(): return int(inp().strip())
def F(): return float(inp().strip())
def S(): return inp().strip()
def pf(s): return out(s+'\n')
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)

def main():
    s = S()
    n = len(s)

    numMultiples = 0
    seenRemainders = [dict() for i in range(n)]
    for i in range(n):
        remainder = 0
        prefixesFound = 0
        for j in range(i,n):
            remainder = (10 * remainder + (ord(s[j])-ord('0'))) % 2019
            if remainder in seenRemainders[j]:
                break
            seenRemainders[j][remainder]=1
            if remainder == 0:
                prefixesFound+=1
        numMultiples += (prefixesFound * (prefixesFound + 1))// 2
    print(numMultiples)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
S=input()
L=list(S)
length=len(L)    

total=0
List=[]
for i in range(0,length-3):
	y=L[i]
	for j in range(i+1,length):
		x=int(str(y)+L[j])
		y=x
		List.append(y)
          
def calc(n):
	return n%2019

data2=list(map(calc,List))
print(data2.count(0))

Submission status: Time Limit Exceeded

Solution code:
def main():
    from collections import Counter

    s = list(str(input()))
    num = ""
    li = []
    f = 0
    mi = 0
    li_append = li.append

    cm = {}
    for i in range(1,2*(10 ** 5)):
        cm[i] = i * (i - 1) // 2
    cm[0] = 0



    for i in range(1, len(s) + 1):
        num = s[-i] + num
        li_append(int(num) % 2019)
        if num[0] == "0":
            f += 1
        else:
            mi += cm[f+1]
            f = 0

    co = Counter(li)
    val = [i for i in co.values() if i > 1]
    ans_1 = 0

    for x in val:
        ans_1 += cm[x]
    ans2 = 0
    if 0 in co:
        ans2 = co[0]
    print(ans_1 + ans2 - mi)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
S = list(input())
rest = [0] * (len(S) + 1)
rest[0] = 0
for i in range(len(S)):
    rest[i+1] = (rest[i] + int(S[-(i+1)]) * 10 ** i) % 2019
    # print(i, rest[i+1], rest[i], int(S[-(i+2)]), int(S[-(i+2)]) * 10 ** (i+1))
# print(rest)
cnt = [0] * (2019 + 1)
for i in rest: cnt[i] += 1
ans = 0
for i in range(2020):
    ans += cnt[i] * (cnt[i] - 1) // 2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
  s = tuple(input())
  count = 0
  count = [1 for j in range(4, len(s)+1) for i in range(len(s)-j+1) if int(''.join(s[i:i + j])) % 2019 == 0]
  print(sum(count))

if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
s = input()

ans = 0
for i in range(len(s)):
    for j in range(len(s)):
        if i+3 <= j:
            if int(s[i:j+1]) % 2019 == 0:
                ans += 1
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
N = list(input())
# Ns = ''.join(N)
M = list(map(str, list(range(len(N)))))
S = list(itertools.combinations(M,2))
count = 0
for _, combi in enumerate(S):
    if int(combi[1]) - int(combi[0]) > 2:
        A = N[int(combi[0]):int(combi[1])+1]
        B = ''.join(A)
        # print(A,B)
        if int(B)%2019 == 0:
            count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
s = str(input())
l = len(s)

count = 0
temp1 = range(3, l + 1, 1)
for j in temp1:
    temp2 = range(0, l - j, 1)
    k = j + 1
    for i in temp2:
        if int(s[i:i+k]) % 2019 == 0:
            count = count + 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
S = input()
N = int(len(S))
A = 0

for i in range(N - 3):
    S1 = S[:N-i]
    for j in range(N - 3 - i):
        S2 = S1[N-i-j-4:]
        if int(S2) % 2019 == 0:
            A = A + 1

print(A)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
S = input()
listS = list(map(int,list(S)))
ans = 0
modlist = []
mod = int(S[len(S) - 1])
for i in reversed(range(len(S) - 1)):
    modlist.append(mod)
    mod = (mod + 10 ** (len(S) - i - 1) * int(S[i])) % 2019
modlist.append(mod)
c = Counter(modlist)
for i in c.values(): ans += i * (i - 1) // 2
print(c[0] + ans)

Submission status: Time Limit Exceeded

Solution code:
import re
N = ['12114', '14133', '16152', '18171', '24228', '26247', '28266', '34323', '36342', '38361', '42399', '44418', '46437', '48456', '52494', '54513', '56532', '58551', '62589', '66627', '68646', '72684', '76722', '78741', '82779', '84798', '86817', '88836', '92874', '94893', '96912', '98931', '119121', '123159', '125178', '127197', '129216', '131235', '133254', '135273', '137292', '139311', '143349', '145368', '147387', '151425', '153444', '155463', '157482', '163539', '165558', '167577', '169596', '171615', '173634', '175653', '177672', '179691', '183729', '185748', '187767', '189786', '193824', '195843', '197862', '199881', '211995', '226128', '228147', '232185', '236223', '238242', '244299', '246318', '248337', '252375', '254394', '256413', '258432', '264489', '268527', '272565', '274584', '278622', '284679', '286698', '288717', '292755', '294774', '296793', '298812', '312945', '314964', '316983', '331116', '333135', '335154', '337173', '339192', '341211', '345249', '347268', '349287', '353325', '355344', '357363', '359382', '365439', '367458', '369477', '371496', '373515', '375534', '377553', '379572', '381591', '385629', '387648', '389667', '391686', '395724', '397743', '399762', '411876', '413895', '415914', '417933', '419952', '421971', '438123', '442161', '446199', '448218', '452256', '454275', '456294', '458313', '462351', '466389', '472446', '474465', '476484', '482541', '486579', '488598', '492636', '494655', '496674', '498693', '512826', '514845', '516864', '518883', '522921', '526959', '528978', '543111', '547149', '549168', '551187', '555225', '557244', '559263', '561282', '567339', '569358', '571377', '573396', '575415', '577434', '579453', '581472', '583491', '587529', '589548', '591567', '593586', '597624', '599643', '611757', '613776', '615795', '617814', '619833', '621852', '623871', '629928', '631947', '633966', '635985', '652137', '654156', '656175', '658194', '662232', '664251', '668289', '672327', '674346', '676365', '678384', '682422', '684441', '688479', '692517', '694536', '696555', '698574', '714726', '716745', '718764', '724821', '728859', '732897', '734916', '736935', '738954', '742992', '757125', '759144', '761163', '763182', '769239', '771258', '773277', '775296', '777315', '779334', '781353', '783372', '785391', '789429', '791448', '793467', '795486', '799524', '811638', '813657', '815676', '817695', '819714', '821733', '823752', '825771', '831828', '833847', '835866', '837885', '841923', '843942', '845961', '849999', '862113', '864132', '866151', '874227', '876246', '878265', '884322', '886341', '892398', '894417', '896436', '898455', '912588', '916626', '918645', '922683', '926721', '932778', '934797', '936816', '938835', '942873', '944892', '946911', '952968', '954987', '971139', '973158', '975177', '977196', '979215', '981234', '983253', '985272', '987291', '991329', '993348', '995367', '997386', '1112469', '1114488', '1118526', '1122564', '1124583', '1128621', '1132659', '1134678', '1136697', '1138716', '1142754', '1144773', '1146792', '1148811', '1152849', '1154868', '1156887', '1162944', '1164963', '1166982', '1181115', '1183134', '1185153', '1187172', '1189191', '1193229', '1195248', '1197267', '1199286', '1213419', '1215438', '1217457', '1219476', '1221495', '1223514', '1225533', '1227552', '1229571', '1235628', '1237647', '1239666', '1241685', '1245723', '1247742', '1249761', '1253799', '1255818', '1257837', '1259856', '1261875', '1263894', '1265913', '1267932', '1269951', '1273989', '1288122', '1294179', '1296198', '1298217', '1314369', '1316388', '1322445', '1324464', '1326483', '1334559', '1336578', '1338597', '1342635', '1344654', '1346673', '1348692', '1354749', '1356768', '1358787', '1362825', '1364844', '1366863', '1368882', '1374939', '1376958', '1378977', '1395129', '1397148', '1399167', '1411281', '1415319', '1417338', '1419357', '1421376', '1423395', '1425414', '1427433', '1429452', '1431471', '1437528', '1439547', '1441566', '1443585', '1447623', '1449642', '1451661', '1455699', '1457718', '1459737', '1461756', '1463775', '1465794', '1467813', '1469832', '1471851', '1475889', '1479927', '1481946', '1483965', '1485984', '1512231', '1516269', '1518288', '1522326', '1524345', '1526364', '1528383', '1532421', '1536459', '1538478', '1542516', '1544535', '1546554', '1548573', '1552611', '1556649', '1558668', '1564725', '1566744', '1568763', '1576839', '1578858', '1582896', '1584915', '1586934', '1588953', '1592991', '1611162', '1613181', '1617219', '1619238', '1621257', '1623276', '1625295', '1627314', '1629333', '1631352', '1633371', '1639428', '1641447', '1643466', '1645485', '1649523', '1651542', '1653561', '1657599', '1659618', '1661637', '1663656', '1665675', '1667694', '1669713', '1671732', '1673751', '1677789', '1681827', '1683846', '1685865', '1687884', '1691922', '1693941', '1697979', '1699998', '1712112', '1714131', '1718169', '1724226', '1726245', '1728264', '1734321', '1738359', '1742397', '1744416', '1746435', '1748454', '1752492', '1754511', '1758549', '1762587', '1766625', '1768644', '1772682', '1778739', '1782777', '1784796', '1786815', '1788834', '1792872', '1794891', '1798929', '1819119', '1821138', '1823157', '1825176', '1827195', '1829214', '1831233', '1833252', '1835271', '1841328', '1843347', '1845366', '1847385', '1851423', '1853442', '1855461', '1859499', '1861518', '1863537', '1865556', '1867575', '1869594', '1871613', '1873632', '1875651', '1879689', '1883727', '1885746', '1887765', '1889784', '1893822', '1895841', '1899879', '1911993', '1926126', '1928145', '1932183', '1936221', '1942278', '1944297', '1946316', '1948335', '1952373', '1954392', '1956411', '1962468', '1964487', '1968525', '1972563', '1974582', '1982658', '1984677', '1986696', '1988715', '1992753', '1994772', '1996791']
#print(len(N))

S = input()
A = []
for j in range(len(S)):
    for i in N:
        a = re.search(i,S[j:])
        #ans += S.count(i)
        if a == None:
            None
        else:
            A.append(a.start()+j)

print(len(set(A)))


'''
N = []
for i in range(2019,1998810,2019):
     if str(i).count("0") == 0:
         N.append(str(i))
print(N)
'''

Submission status: Time Limit Exceeded

Solution code:
def s0():return input()

s=s0()

d=[int(s[0])]
c=0
for i in s[1:]:
    y=int(i)
    d = [x*10+y for x in d]
    d.append(y)
    for j in d:
        if j%2019==0:
            c+=1
#     print(d)
print(c)

Submission status: Time Limit Exceeded

Solution code:
import functools
def solve():
    s = int(input())
    t = [int(x) for x in list(str(s))]

    l = []
    for i in range(1, 10000):
        num = [int(x) for x in list(str(i*2019))]
        if 0 not in num:
            l.append(num)

    cnt = 0
    n= len(t)
    for i in range(len(l)):
        m = len(l[i])
        for j in range(n-m+1):
            if l[i] == t[j:j+m]:
                    cnt += 1

    return cnt
    
print(solve())

Submission status: Time Limit Exceeded

Solution code:
S = input()
ans = 0
for i in range(6, int(S)//2019 + 1):
  d = str(2019*i)
  ans += S.count(d)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()
l = len(s)

count = 0
for i in range(l):
	for j in range(i + 3, l):
		n = int(s[i:j + 1])
		if n % 2019 == 0:
			count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
s = input()
l = list(s)
l = [int(i) for i in l]
lLen = len(l)
lLimit = len(l) - 3
cnt = 0

for i in range(lLen):
    sum = 0
    for j in range(i, lLen):
        sum = sum + l[j]
        if (j > 2) and (sum % 3 == 0):
            r = int(s[i:j+1])
            if r % 673 == 0:
                cnt = cnt + 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
s = input()
n = len(s)
k = 2019
cnt = 0
seenRem = []
for i in range(n):
    seenRem.append(set())
for i in range(n):
    rem = 0
    f = 0
    for j in range(i, n):
        rem = (10 * rem + int(s[j])) % k
        if rem in seenRem[j]:
            break
        seenRem[j].add(rem)
        if rem == 0:
            f += 1
    cnt += (f * ( f + 1) / 2)
print(int(cnt))

Submission status: Time Limit Exceeded

Solution code:

s=input()

nagasa=len(s)
num=0
check=dict()



for i in range(nagasa-3):
    target=s[nagasa-4-i:nagasa-i]
    #print(target)
    mod=int(target)%2019
    if(mod==0):
        num+=1

        
    co=5
    while(co<=nagasa-i):
        target=s[nagasa-co-i]+target
        #print(target)
        #mod=int(target)%2019
        mod=(mod+int(s[nagasa-co-i])*10**(co-1))%2019
        if(mod==0):
            num+=1
        
        co+=1
        
print(num)

Submission status: Time Limit Exceeded

Solution code:
def main():
    s = input()
    ans = 0
    for i in range(4, len(s) + 1, 1):
        for j in range(0, i - 3, 1):
            if j == 0:
                x = int(s[-i:]) % 2019
            else:
                x = int(s[-i:]) - int(s[-j:])
            if x % 2019 == 0:
                ans += 1

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import math

from collections import defaultdict
from collections import deque
def load(vtype=int):
    return vtype(input().strip())

s = load(str)
d = dict()
for i in range(1, 10):
    d[str(i)] = i
cnt = 0
for i in range(len(s)):
    target = int(s[i:i+3])
    for j in range(i+3, len(s)):
        target =  target * 10 + d[s[j]]
        if target % 2019 == 0:
            cnt += 1
            break
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
s=input()
k=0
sij0=0
#sij1=0
l=len(s)
a=[0]*l
for i in range(3,l):
  a[i]=int(s[i])
for i in range(l-3):
  sij0=int(s[i:i+4])
  #print(sij0)
  sij0=sij0 % 2019
  if sij0 == 0:
    k=k+1
  for j in range(i+4,l):
    #sij1=int(s[j])
    sij0*=10
    sij0+=a[j]
    sij0 = sij0 % 2019
    if sij0 == 0:
      k=k+1
print(k)

Submission status: Time Limit Exceeded

Solution code:
s = input()
if len(s) < 4:
  print('0')
else:
  cnt = 0
  for i in range(len(s)-3):
    if int(s[i:i+2]) %2 != 0:
      continue
    if i+3 > len(s):
      break
    for j in range(i+3, len(s)):
      if int(s[i:j+1]) % 2019 == 0:
        cnt += 1
  print(cnt)

Submission status: Time Limit Exceeded

Solution code:
S = input()
r, ans = 0, 0
for l in range(len(S)):
    while r < len(S) and int(S[l:r+1]) % 2019 != 0:
        r += 1
    #print(l,r)
    if int(S[l:r+1]) % 2019 == 0:
        ans += 1
    r = l + 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = input()
l = [i*2019 for i in range(1,200000) ]
m = [str(i) for i in l if str(i).find('0') == -1]
c = 0
st = str(S)
mls = len(S)

sl = [S[mls-i:mls] for i in range(5,mls+1)]

for i in m:
    for j in sl:
        if j.startswith(i):
            c += 1

print(c)

Submission status: Time Limit Exceeded

Solution code:
s = list(input(''))

count = 0
kaisuu = 0
sta = 0

for i in range(sta,len(s)+1):
    for j in range(i+1,len(s)+1):
        slice_s = s[i:j]
        num = int(''.join(slice_s))
        if num % 2019 == 0:
            count += 1
        #     sta = j
        # if sta == j:
        #     continue
        # kaisuu += 1
        # print('i=',i)
        # print('回数：',kaisuu)
print(count)

Submission status: Time Limit Exceeded

Solution code:
S = str(input())

S_list =list(S)


A = 0
for i in range(0,len(S_list)-1):
    for j in range(i+1,len(S_list)+1):
        P = 0
        S_list_P = S_list[i:j]
        for k in range(0,j-i):
            P += int(S_list_P[k])* 10 ** (j-i-k-1)
        
        if P % 2019== 0:
            A += 1



print(A)

Submission status: Time Limit Exceeded

Solution code:
S = input()

ret = 0
mod = [[],[],[]]
mod[int(S[0])%3].append(0)
for j in range(1,len(S)):
    mod3 = int(S[j])%3
    for i in mod[(3-mod3)%3]:
        s = int(S[i:j+1])
        if s % 2019 == 0:
            ret += 1
    idx = [(i+mod3)%3 for i in range(3)]
    tmp = [None for _ in range(3)]
    for i,ii in enumerate(idx):
        tmp[ii] = mod[i]
    mod = tmp
    mod[mod3].append(j)
print(ret)

Submission status: Time Limit Exceeded

Solution code:
S=input()
l=len(S)
z=0
K=[]
for x in range(l):
    for y in range(l-x-3):
        T=S[x:x+y+4]
        t=int(T)
        K.append(t)
K=[x%2019 for x in K]
print(K.count(0))

Submission status: Time Limit Exceeded

Solution code:
def digitSum(n):
    # 数値を文字列に変換
    s = str(n)
    # １文字ずつ数値化し配列にする。
    array = list(map(int, s))
    # 合計値を返す
    return sum(array)
S = input()
Scount = 0
for i in range(len(S)-1):
    for j in range(1,len(S)):
        if (i+j)<=len(S):
            part_S = S[i:i+j]
            num = int(part_S)
            sum3 = digitSum(num)
            while sum3 != digitSum(sum3):
                sum3 = digitSum(sum3)
            if sum3 == 3 or sum3 == 6 or sum3 ==9:
                num = num // 3
                if num % 673==0:
                    Scount += 1
print(Scount)