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:
import sys
import math
import queue
import copy
import bisect#2分探索
from collections import deque #popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意

def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s): return sorted(range(len(s)), key=lambda k: s[k])

#mod = 10**9+7

S = int(input())
#N, K = map(int, input().split())
#L = [int(input()) for i in range(N)]
#A = list(map(int, input().split()))
#S = [inputl() for i in range(H)]
#q = queue.Queue() #q.put(i) #q.get() 
#q = queue.LifoQueue() #q.put(i) #q.get() 

#a= [[0]*3 for i in range(5)] #2次元配列はこう準備、[[0]*3]*5だとだめ
#b=copy.deepcopy(a)  #2次元配列はこうコピーする
#w.sort(key=lambda x:x[1],reverse=True)  #二個目の要素で降順並び替え

#素数リスト
# n = 100
# primes = set(range(2, n+1))
# for i in range(2, int(n**0.5+1)):
#     primes.difference_update(range(i*2, n+1, i))
# primes=list(primes)

#bisect.bisect_left(a, 4)#aはソート済みである必要あり。aの中から4未満の位置を返す。rightだと以下
#bisect.insort_left(a, 4)#挿入

ss=str(S)
# #print(ss)
ls=len(ss)
# l=[0]*(ls+1)

    #print(l[i])
#print(l)

import heapq #優先度付きqueue

kl=[0]*2019
kl[0]=1
a = [0]
heapq.heapify(a)  # aを優先度付きキューに

for i in range(0,ls):
    kl[(S%10**(i+1))%2019]+=1
#print(a)


ans=0

for k in kl:
    ans+=k*(k-1)//2

print(ans)
# cur=-1
# ans=0
# for i, li in enumerate(l):
#     if cur==-1:
#         cur=li
#         count=1
#     elif li==cur:
#         count+=1
#     else:
#         ans+=count*(count-1)//2
#         cur=li
#         count=1

# print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = input()

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

Submission status: Time Limit Exceeded

Solution code:
S=input()
A=0

SL=list(S)
for i in range(len(SL)):
    SL[i]=int(SL[i])

while len(S)>3:
    SL_sum=SL.copy()
    for i in range(1, len(SL_sum)):
        SL_sum[i] += SL_sum[i-1]
    for i in range(len(SL_sum)):
        if SL_sum[i]%3 == 0 :
            if int(S[:i+1])%673 ==0 :
                A+=1
    S=S[1:]
    SL=SL[1:]
print(A)

Submission status: Time Limit Exceeded

Solution code:
S=input()
N=len(S)
cnt=0
begin=0
end=0
for i in range(0,N+1):
    begin=i
    end=i+4
    
    while begin<N-3 and end<=N:
        if int(S[begin:end])%2019==0:
            cnt+=1
            if begin==N-5 and end==N:
                print(cnt)
                exit()
            else:
                begin= end-1
                end+=4
        else:
            end+=1
            continue
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
s = input()
s_l = [s_l for s_l in s]
n=len(s_l)
cou = 0
for x in range(n):
    for y in range(x+3,n):
        st = ''
        for u in s_l[x:y+1]:
            st += u
            m = int(st)
        if m % 3 == 0 and m % 673 ==0:
            if m == 0:
                continue
            cou +=1
            
print(cou)

Submission status: Time Limit Exceeded

Solution code:
S = input()
S = S[::-1]
L = [0]
i = 0
for x in S:
    tmp = L[-1] + 10 ** i * int(x) % 2019
 #   print(tmp % 2019)
    L.append(tmp % 2019)
    i += 1
L = sorted(L[1::])
def counter(array):
    from collections import Counter
    return list(Counter(array).most_common())
c = counter(L)
from math import factorial
def comb(n,r):
    if n == 1: return 0
    return  factorial(n) / factorial(r) / factorial(n - r)
ans = 0
for x in c:
    if x[0] == 0: ans += x[1]
    ans += comb(x[1],2)
#print(L,c)
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
#ABC 164D

def count(text, part):
    return sum(text.startswith(part, i) for i in range(len(text)))

s = str(input())
#s = '1817181712114'
#s = '14282668646'

cnt = 0

for i in range(1, 1000):
    if count(s, str(2019*i)) > 0:
#        print(i*2019)
#        print(count(s, str(2019*i)))
        cnt += count(s, str(2019*i))

print(cnt)

"""
for i in range(0, 11):
    if s.count(str(2019*i)) > 0:
        print(i)
        print(s.count(str(2019*i)))
        cnt += s.count(str(2019*i))

print(cnt)
"""
"""

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

print(cnt)

"""

Submission status: Time Limit Exceeded

Solution code:
def n_gram(target,n):
    count = 0
    for idx in range(len(target) - n + 1):
        if int(target[idx:idx+n]) % 2019 == 0:
            count += 1
    return count

c = 0
s = input()
n = 4
num_list = ()
s_len = len(s)
while n <= s_len:
    c += n_gram(s,n)
    n += 1
print(c)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
if n<10000:
  if n%2019 == 0:
    print(1)
  else:
    print(0)
else:
  x=str(n)
  c=0
  used=[]
  for i in range(len(x)-4):
    if i not in used:
      for j in range(i+4, len(x)):
        if int(x[i:j+1]) % 2019 == 0:
          c+=1
          used.append(i)
          i=j
          j+=4
  print(c)

Submission status: Time Limit Exceeded

Solution code:
def slove(n):

    count = 0
    for i in range(4, len(n)+1):
        start = 0
        end = i
        while True:
            if end > len(n):
                break
            tmp = int(n[start:end])
            if tmp % 2019 == 0:
                count += 1

            start +=1
            end +=1

    return count

if __name__ == "__main__":
    n = input()
    print(slove(n))

Submission status: Time Limit Exceeded

Solution code:
s=input()
if len(s)<=4:
  if int(s)%2019==0:
    print(1)
  else:
    print(0)

else:
  from collections import deque
  count=0
  for i in range(4,len(s)):
    sub=deque()
    j=0
    while True:
      if len(sub)>=i:
        break
      sub.append(s[j])
      j+=1
    
    for k in range(i-1,len(s)):
      # print("k=",k)
      if k>=i:
        sub.popleft()
        sub.append(s[k])
      tmp="".join(sub)
      # print("tmp=",tmp)
      if int(tmp)%2019==0:
        count+=1
        # print("ktkr")
  print(count)

Submission status: Time Limit Exceeded

Solution code:
s = input()
c = 0
for i in range(0, len(s)): 
    t = 0
    for j in range(i, len(s)): 
        t = t*10 + int(s[j])
        if (t%2019==0) :
            c+=1
            #print(t)
print(c)

Submission status: Time Limit Exceeded

Solution code:
S = input()
kumi = []
count_start = 0
while count_start <= len(S) - 4:
    count_end = 4
    while count_end <= len(S):
        if count_start + 2 < count_end:
            check = int(S[count_start:count_end])
            if check % 2019 == 0:
                kumi.append(check)
        count_end += 1
    count_start += 1
print(len(kumi))

Submission status: Time Limit Exceeded

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

ans = 0
digit_sum_mod3 = 0
start = 0

while start <= n-4:
    end = start + 4
    while end <= n:
      if end == start + 4:
        for k in range(4):
          index = start + k
          digit_sum_mod3 += int(s[index])
          digit_sum_mod3 %= 3
      if digit_sum_mod3 == 0:
        if int(s[start:end]) % 2019 == 0:
          ans += 1
      if end == n:
        break
      else:
        digit_sum_mod3 += (int(s[end]) % 3)
        digit_sum_mod3 %= 3
      end += 1
    digit_sum_mod3 = 0
    start += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = input()


count = 0

for i in range(len(S)+1):
    for j in range(i + 4,len(S)+1):
       
        x = int(S[i:j])
        

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

print(count)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
s=input()
N=len(s)
ans=0
li=[1,2,4,6,8]
num=[]

"""
for i in range(N):
    for j in range(i,N):
        if int(s[i:j+1])%2019==0:
            ans+=1
"""
for i in range(N):
    if int(s[i]) in li:
        num.append(i)

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

Submission status: Time Limit Exceeded

Solution code:
import sys

s = str(input())
tisa = []
for i in range(1,1000000):
  ww = str(2019*i)
  if '0' not in ww:
    tisa.append(ww)
#ok
#print(s)
#print(tisa)
#print(len(tisa))
#重複　count methodは無理
ans = 0
for c in tisa:
  for i in range(0,len(s)-len(c)+1):
    if s[i:i+len(c)]==c:
      ans += 1

      
  

print(ans)

Submission status: Time Limit Exceeded

Solution code:
numberString= input()
ijList=[];
i=j=0
while i<len(numberString):
  j=i+3
  while j < len(numberString):
    checkNum=int(numberString[i:j+1])
    if checkNum>2019 and checkNum%2019==0:
      ijList.append([i,j])
    j+=1
  i+=1

print(str(len(ijList)))

Submission status: Time Limit Exceeded

Solution code:
S = input()
 
length = len(S)
count = 0
 
i = 0
while i < (length - 3):
  j = i + 4
  while j < (length + 1):
    number = int(S[i:j])
    if number % 2019 == 0:
      count += 1
      j += 4
    j += 1
  i += 1
 
print(count)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
#この解放だとTLE....
s = input()
c = 0
l = len(s)
for i in range(l+1):   #開始インデックスを外側のループに
  for j in range(i+4, l+1):     #j:4桁以下の探索やめた
        #print(s[i:j])
        if(int(s[i:j]) % 2019 == 0):
            c += 1        
print(c)

Submission status: Time Limit Exceeded

Solution code:
N = input()
nagasa = len(N)
count = 0
for a in range(1, nagasa+1):
    for b in range(a+1, nagasa+2):
        c = 0
        keta = b - a + 1
        if keta < 5:
            if keta == 2019 or keta ==4038 or keta ==6057 or keta == 8076:
                count += 1
                continue
            else:
                continue
        for k in range(1,keta):
            c += int(N[a - 2 + k]) * 10 ** (keta-k-1)
        if c % 2019 == 0  and c != 0:
            count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
S = input()

Len = len(S)
N = 0
for Num1 in range(0, Len-2):
    #0-> 3
    #Len-4 -> Len-1
    Remainder = int(S[Num1:Num1+3])
    for Num2 in range(Num1+4, Len+1):
        Remainder = (10 * Remainder + int(S[Num2-1]) ) % 2019
        if(Remainder == 0):
            N+= 1
            Num2 += 3
print(N)

Submission status: Time Limit Exceeded

Solution code:
import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
import numpy as np
def resolve():
    S = sr()
    N = len(S)
    a = ['']
    for i in range(N):
        a.append(int(S[-1-i]+str(a[i])))
    a = a[::-1]
    a[-1] = 0
    a = np.array(a, np.int64)
    ans = 0
    for i in range(N):
        t = a%2019
        ans += np.sum(t==0)-1
        a = a//10
        a = np.delete(a, -1)
    print(ans)
resolve()

Submission status: Time Limit Exceeded

Solution code:
S = input()
N = len(S)
cnt =0
for i in range(N-3):
  for j in range(i+3, N+1):
    if int(S[i:j]) % 2019 == 0:
      cnt +=1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
S=input()
count=0
def n_gram(target, n):
  return [ target[idx:idx + n] for idx in range(len(target) - n + 1)]
  #この部分はN-gramで検索して引用した

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

print(count)

Submission status: Time Limit Exceeded

Solution code:
s = list(input())
ans = 0
for i in range(4,len(s)+1):
    for j in range(0,len(s)+1-i):
      d = s[j:j+i]
      l = ''.join(d)
      if int(l) % 2019 == 0:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = str(input())
s = len(S)
cnt = 0
A = [0]*2019
for i in range(s):
  x = int(S[i:])%2019
  A[x] += 1
for i in range(1,2019):
  cnt += A[i]*(A[i]-1)//2
cnt += A[0]*(A[0]+1)//2
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
#d
N = str(input())
a = []
 
def func(string,p):
    count=0
    for x in range(len(string)-len(p)+1):
        if string[x:x+len(p)]==p:
            count+=1
    return count
 
for i in range(1,10000):
    a.append(str(2019*i))

if len(N)<4:
    print(0)
else:
    ans=0
    for j in a:
        ans+=func(N,j)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import pow
def get_table():
    table = []
    for i in range(10):
        a = int(pow(10, i))
        table.append(a % 2019)
    return table

table = get_table()
# print(table)

def get_power_2019(idx):
    if (idx < len(table)):
        return table[idx]
    else:
        j = int(idx/2)
        i = idx - j
        return (get_power_2019(i) * get_power_2019(j)) % 2019

s = input()
mod_dict = {}

last_mod = 0
for i in range(len(s)-1, -1, -1):
    current_lowest_digit = int(s[i])
    current_mod = ((current_lowest_digit * get_power_2019(len(s)-1-i))% 2019 + last_mod) % 2019
    if (current_mod not in mod_dict.keys()):
        mod_dict[current_mod] = [i]
    else:
        mod_dict[current_mod].append(i)
    last_mod = current_mod

# print(mod_dict)

count = 0
for k in mod_dict.keys():
    n = len(mod_dict[k])
    count += int(n*(n-1)/2)
    if (k == 0):
        count += n
print(count)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

S = input()
lis_2019 = [2019 * i for i in range(1, 99)]
cnt = 0
S_len = len(S)
cnt_1 = 0
S_lis = [S]

for i in range(4, S_len):
    while cnt_1 != S_len - i + 1:
        for j in lis_2019:
            if str(j) == str(S[cnt_1:cnt_1+i]):
                cnt += 1
        cnt_1 += 1
    cnt_1 = 0

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
s = input()
l = len(s)
r = 0
m = [0]*2019
for i in range(3,l):
    num = int(s[i])
    m2 = [0]*2019
    for j in range(1,2019):
        j2 = (j*10+num) % 2019
        m2[j2] += m[j]
    m2[int(s[i-3:i+1]) % 2019] += 1
    r += m2[0]
    m2[0] = 0
    m = m2.copy()
print(r)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
s = input()
ls = len(s)
l_2019_set = set(list(range(2019, 20190000, 2019)))
d = deque()
ans = 0
for i in range(ls-3):
    for j in range(i+3, ls+1):
        d.append(int(s[i:j]))
for x in l_2019_set:
    ans += d.count(x)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
a=input()
count=0
for i in range(len(a)-3):
  t=a[i]+a[i+1]+a[i+2]+a[i+3]
  if int(t)%2019==0:
    count+=1
  for j in range(i+4,len(a)):
    t+=a[j]
    if int(t)%2019==0:
      count+=1
    
 
print(count)

Submission status: Time Limit Exceeded

Solution code:
S = input()
answer = 0
for i in range(len(S)-2):
    for j in range(i+5,len(S)+1):
        if int(S[i:j]) % 2019 ==0:
                answer += 1
print(answer)

Submission status: Time Limit Exceeded

Solution code:
S = 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:
import numpy as np
s = list(map(int,input()))
n = len(s)
ans = 0
mod = 2019
wa = [0 for i in range(n)]
wa[0] = s[n-1]
for i in range(1,n):
    ii = i
    now = 10
    aaa = 1
    while ii > 0:
        if ii%2 == 1:
            aaa = (aaa*now)%mod
        now = (now**2)%mod
        ii //= 2
    wa[i] = (wa[i-1]+s[n-i-1]*aaa)%mod
    if wa[i] == 0:
        ans += 1

for i in range(n):
    for j in range(i+1,n):
        if wa[i] == wa[j]:
            ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    def input():
        return sys.stdin.readline()[:-1]
    S=input()
    result=0
    for i in range(len(S)-3):
        k=i
        for j in range(i+4,len(S)+1):            
            a=S[k:j]
            if int(a)%2019==0:
                result+=1
                k+=j-k
    print(result)

if __name__ == '__main__':
    main()