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:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys


def input():
    return sys.stdin.readline()


def resolve():
    s = input().rstrip()

    count = 0
    if len(s) < 5:
        if int(s) % 2019 == 0:
            print("1")
            exit()
        else:
            print("0")
            exit()

    one_digit_list = ["2", "4", "6", "8"]
    for i in range(0, len(s)):
        for j in range(4, len(s)):
            if i // j >= 1:
                continue


            if j == 4:
                one_num = s[i]
                if one_num not in one_digit_list:
                    continue


            for k in range(0, len(s), j):
                start = i + k
                end = start + j

                if end > len(s):
                    continue

                # print(start, end)
                int_s = int(s[start:end])

                if int_s % 2019 == 0:
                    count += 1
    print(count)



if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
from sys import setrecursionlimit, exit
setrecursionlimit(1000000000)

def main():
    s = input()
    l = len(s)
    m = [0] * (l + 1)
    for i in range(l - 1, -1, -1):
        m[i] = (m[i+1] + int(s[i]) * pow(10, l - i - 1)) % 2019
    mod = [0] * 2019
    for i in m:
        mod[i] += 1
    ans = 0
    for i in range(2019):
        ans += (mod[i] - 1) * mod[i] // 2
    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
S = input().strip()
N = len(S)
SS = S[::-1]

mod_count = [0] * 2019
mod_count[0] = 1
sums = [0]
for i in range(N):
    sums.append((sums[-1] + int(SS[i]) * (10**i)) % 2019)
    mod_count[sums[-1]] += 1

print(sum([m * (m - 1) for m in mod_count]) // 2)

Submission status: Time Limit Exceeded

Solution code:
s=input()
n=len(s)
t=int(s)
dict={}
sum=0
for i in range(n):
    for j in range(i+1,n):
        string=str(i)+"_"+str(j)
        if string not in dict.keys():
            dict[string]=0
            num=s[i:j+1]
            num=int(num)
            if num%2019==0:
                sum+=1
        
print(sum)

Submission status: Time Limit Exceeded

Solution code:
# 解説を参考に作成
def solve():
    S = input()
    lenS = len(S)
    # modS = []
    mod_list = [0] * 2019
    for i in range(lenS):
        x = int(S[lenS - 1 - i:]) % 2019
        # modS.append(int(S[lenS - 1 - i:]) % 2019)
        mod_list[x] += 1
    result = 0
    for i, ml in enumerate(mod_list):
        if i == 0:
            result += ml
        result += int(ml * (ml - 1) / 2)
    print(result)


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
#n,p = map(int,input().split())
s = input()
p = 2019
n = len(s)
u_i = []
ans = 0
for i in range(n):
    u_i.append(int(s[i:])%p)
u_i.append(0)
amari = [0]*p
for i in u_i:
    amari[i] += 1
for i in amari:
    ans+= i*(i-1)//2
print(ans)

Submission status: Time Limit Exceeded

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

c=0
S = input().rstrip("\n")
len_s = len(S)
for i in range(len_s-3):
    for j in range(len_s-i-3):
        s = int(S[j:])
        if s%2019 ==0:
            c +=1
        else:
            pass
    S = S[:-1]

print(c)

Submission status: Time Limit Exceeded

Solution code:
S = input()
N = len(S)
mod2019 = [0] * 2019
mod2019[0] = 1

for i in range(N):
    mod2019[int(S[i:]) % 2019] += 1
sum = 0
for i in range(2019):
    sum += mod2019[i] * (mod2019[i]-1) // 2
print(sum)

Submission status: Time Limit Exceeded

Solution code:
def D():
    s = input()
    sketa = len(s)
    ans = 0
    mods = {0:1}
    for i in range(1,sketa+1):
        mod = int(s[-i:])%2019
        try:
            ans += mods[mod]    
            mods[mod] += 1
        except KeyError:
            mods[mod] = 1
    print(ans)
D()

Submission status: Time Limit Exceeded

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

countdic = {}
mod = 2019

for i in range(1,n+1):
    num = s%(pow(10,i))
    remainder = num%mod
    if remainder in countdic:
        countdic[remainder] += 1
    if remainder not in countdic:
        countdic[remainder] = 1

ans = 0
for key in countdic:
    ans += countdic[key]*(countdic[key]-1)//2

if 0 in countdic:
    ans += countdic[0]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
s = input()
ans = 0
mod = []
t = s[len(s)-1]
for i in range(len(s)-1,-1,-1):
#     mod.append(int(s[i:])%2019)
    mod.append(int(t)%2019)
#     t = int(t) + (10**(len(s)-i-1))*int(s[i])
    t = int(t) + 10**(len(s)-i)*int(s[i-1])
for i in range(1,2019):
    ans += mod.count(i)*(mod.count(i)-1)/2
ans += mod.count(0)
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
import collections

def main():
    S = list(map(int,list(input())))
    t = [0] * (len(S) + 1)
    for i in range(len(S)):
        t[i+1] = (t[i] + S.pop() * 10 ** i) % 2019
    count_dict = collections.Counter(t)
    result = sum([b*(b-1)//2 for a, b in count_dict.items()])
    print(result)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
S = input().strip()
N = len(S)

mod_count = {0: 1}
SS = S[::-1]
sums = [0]
for i in range(N):
    sums.append((sums[-1] + int(SS[i]) * (10**i)) % 2019)
    mod_count[sums[-1]] = mod_count.get(sums[-1], 0) + 1

print(sum([m * (m - 1) for m in mod_count.values()]) // 2)

Submission status: Time Limit Exceeded

Solution code:
S = input()[::-1]
dp = [0]*2019
dp[0] = 1
P = [int(S[:i][::-1]) for i in range(1,len(S)+1)]
for i in P:
    dp[i%2019] += 1
print(sum([i*(i-1)//2 for i in dp]))

Submission status: Time Limit Exceeded

Solution code:
# 解説を参考に作成
def solve():
    S = input()
    lenS = len(S)
    modS = []
    mod_list = [0] * 2019
    for i in range(lenS):
        x = int(S[lenS - 1 - i:]) % 2019
        modS.append(int(S[lenS - 1 - i:]) % 2019)
        mod_list[x] += 1
    result = 0
    for i, ml in enumerate(mod_list):
        if i == 0:
            result += ml
        result += int(ml * (ml - 1) / 2)
    print(result)


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
# import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)


def main():
    S = input().rstrip()

    N = len(S)

    M = [0 for i in range(2019)]
    T = 0
    M[0] += 1

    for i in range(N):
        T = int(S[N-i-1]) * 10 ** i + T
        M[T%2019] += 1

    res = 0

    for m in M:
        res += m * (m-1) // 2


    print(res)



main()

Submission status: Time Limit Exceeded

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

c=0
S = input().rstrip("\n")
len_s = len(S)
for i in range(len_s-3):
    for j in range(len_s-i-3):
        s = int(S[j:])
        if s%2019 ==0:
            c +=1
        else:
            pass
    S = S[:-1]

print(c)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
s = deque(input())
n = len(s)

temp = [0]*2019
num = 0
for i in range(n):
    num += int(s.pop())*10**(i)
    temp[num % 2019] += 1

ans = temp[0]
for t in temp:
    if t > 1:
        ans += t*(t-1)/2

print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

S = input()
B = defaultdict(int)
B[0]=1

for i in range(len(S)):
    B[int(S[-i-1:])%2019]+=1

ans=0

for j in B:
    ans+=(B[j]-1)*B[j]/2

print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
s=input()
N=len(s)
kyonen=2019
modlist=[]
for i in range(N):
    modlist.append(int(s[i:N])%kyonen)
modlist.sort()
now=modlist[0]
nowc=1
ans=0
if modlist[0]==0:
    ans+=1
for i in range(1,N):
    if modlist[i]==0:
        ans+=1
    if modlist[i]==now:
        nowc+=1
    else:
        if nowc>=2:
            ans+=int(nowc*(nowc-1)/2)
        nowc=1
        now=modlist[i]

if nowc>=2:
    ans+=int(nowc*(nowc-1)/2)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = input()
n = len(S)
T = {}
T['0']=1
t = 0
ans = 0
for i in range(n):
    t = (t + (int(S[-i-1]))*(10**i))%2019
    if str(t) in T: T[str(t)] +=1
    else: T[str(t)]=1
for v in T.values():
    ans +=int(( int(v)*(int(v)-1))/2)
print(ans)

Submission status: Time Limit Exceeded

Solution code:

S = list(map(int, list(input())))

mod = 2019
ctr = [0] * mod
p = 1
t = 0
for i, v in enumerate(reversed(S)):
    t = (t + int(v) * 10 ** i) % mod
    ctr[t] += 1

ans = ctr[0]
for v in ctr[1:]:
    ans += v * (v - 1) // 2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections
S = input()[::-1]
N = len(S)
mod = 2019

ans = 0
x = [0] * N
x[0] = int(S[0]) % mod

for i in range(1, N):
    x[i] = ((10 ** i) * int(S[i]) + x[i - 1]) % mod
    if x[i] % mod == 0:
        ans += 1
    
d = collections.Counter(x)

for i in d.values():
    ans += i * (i - 1) // 2
    
print(ans)

Submission status: Time Limit Exceeded

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

countdic = {}
mod = 2019

for i in range(1,n+1):
    num = s%(10**i)
    remainder = num%mod
    if remainder in countdic:
        countdic[remainder] += 1
    if remainder not in countdic:
        countdic[remainder] = 1

ans = 0
for key in countdic:
    ans += countdic[key]*(countdic[key]-1)//2

if 0 in countdic:
    ans += countdic[0]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = input()[::-1]
dp = [0]*2019
dp[0] = 1
for i in range(1,len(S)+1):
    dp[int(S[:i][::-1])%2019] += 1
print(sum([i*(i-1)//2 for i in dp]))

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()))
def resolve():
    S = sr()
    N = len(S)
    a = [0]*2019
    a[0] += 1
    t = 0
    r = 1
    for s in reversed(S):
        t += int(s)*r
        r *= 10
        a[t%2019] += 1
    ans = 0
    for i in range(2019):
        ans += a[i]*(a[i]-1)//2
    print(ans)
resolve()

Submission status: Time Limit Exceeded

Solution code:
S = input()[::-1]
dp = [0]*2019
dp[0] = 1
for i in range(1,len(S)+1):
    dp[int(S[:i][::-1])%2019] += 1

print(sum([i*(i-1)//2 for i in dp]))

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import numpy as np


def merge_sort(lst, low, high):
    if low >= high:
        return
    mid = int((low+high)/2)
    merge_sort(lst, low, mid)
    merge_sort(lst, mid+1, high)
    for i in range(low, mid+1):
        tmp_array[i] = lst[i]
    j = high
    for i in range(mid+1, high+1):
        tmp_array[i] = lst[j]
        j -= 1
    i = low
    j = high
    for k in range(low, high+1):
        if tmp_array[i] <= tmp_array[j]:
            lst[k] = tmp_array[i]
            i += 1
        else:
            lst[k] = tmp_array[j]
            j -= 1


S = stdin.readline().rstrip()
N = len(S)
Sp = S

res_map = [0 for _ in range(N)]

aa_list2 = [1]
for i in range(1,N):
    aa_list2.append((aa_list2[i-1]*10)%2019)

tmp_array = [None for _ in range(N)]
res_map[N-1] = int(S[N-1])
index=1
for i in range(N-2,-1,-1):
    res_map[i] = (int(S[i])*aa_list2[index] + res_map[i+1])%2019
    index+=1
#merge_sort(res_map,0,N-1)
#res_map = list(np.sort(np.array(res_map)))
res_map.sort()
temp_num=int(res_map[0])
index=1
tot = 0

#for i in range(1,N):
#    if temp_num==res_map[i]:
#        index+=1
#        continue
#    else:
#        if temp_num==0:
#            tot += int(index*(index+1)/2)
#        elif index>1:
#            tot += int(index*(index-1)/2)
#            #tot += index/2
#        index=1
#        temp_num=res_map[i]


for i in range(2018):
    num = np.sum(np.array(res_map)==i)
    if i ==0:
        num+=1
    tot += int(num*(num-1)/2)
    

print(tot)

Submission status: Time Limit Exceeded

Solution code:
def D():
    s = input()
    sketa = len(s)
    ans = 0
    mods = {0:1}
    for i in range(1,sketa+1):
        mod = int(s[-i:])%2019
        if mod in mods.keys():
            ans += mods[mod]
            mods[mod] += 1
        else:
            mods[mod] = 1
    print(ans)
D()

Submission status: Time Limit Exceeded

Solution code:
import collections

def main():
    S = list(map(int,list(input())))
    result = 0
    t = [0] * (len(S) + 1)
    for i in range(len(S)):
        t[i+1] = (t[i] + S[-i-1] * 10 ** i) % 2019
    count_dict = collections.Counter(t)
    for a, b in count_dict.items():
        result += b*(b-1) // 2

    print(result)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
S = str(input())
s = len(S)
c = 0

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

Submission status: Time Limit Exceeded

Solution code:
S = list(input())
N = len(S)

l = [0] * 2019
index = 0
temp = 0
for i in range(N-1, -1, -1):
    temp += int(S[i]) * pow(10,index) % 2019
    temp %= 2019
    l[temp] += 1
    index += 1

ans = l[0]

for i in range(1, 2019):
    ans += l[i] * (l[i]-1) // 2

print(ans)

Submission status: Time Limit Exceeded

Solution code:
s=[int(i) for i in input()]
s.reverse()

a=0
l=[0 for i in range(2019)]
l[0]=1
for i in range(len(s)):
  a+=s[i]*(10**i)
  a%=2019
  l[a]+=1

answer=0
for i in range(2019):
  answer+=l[i]*(l[i]-1)//2
  
print(answer)

Submission status: Time Limit Exceeded

Solution code:
import bisect

s = input()
n = len(s)

s2 = [0 for _ in range(n)]

zero = []
one = []
two = []
s2[0] = int(s[0]) % 3
if s2[0] == 0:
  zero.append(0)
elif s2[0] == 1:
  one.append(0)
elif s2[0] == 2:
  two.append(0)
for i in range(1,n):
  s2[i] = s2[i-1] + int(s[i])
  s2[i] %= 3
  if s2[i] == 0:
    zero.append(i)
  elif s2[i] == 1:
    one.append(i)
  elif s2[i] == 2:
    two.append(i)
ans = 0
length = len(zero)
for i in range(length):
    if int(s[:zero[i]+1]) % 2019 == 0:
      ans += 1
length = len(zero)
for i in range(length-1):
  tmp = s[zero[i]+1:]
  index = bisect.bisect_left(zero,zero[i]+4)
  for j in range(index,length):
    if int(tmp[:zero[j]-zero[i]]) % 2019 == 0:
      ans += 1

length = len(one)
for i in range(length-1):
  tmp = s[one[i]+1:]
  index = bisect.bisect_left(one,one[i]+4)
  for j in range(index,length):
    if int(tmp[:one[j]-one[i]]) % 2019 == 0:
      ans += 1

length = len(two)
for i in range(length-1):
  tmp = s[two[i]+1:]
  index = bisect.bisect_left(two,two[i]+4)
  for j in range(index,length):
    if int(tmp[:two[j]-two[i]]) % 2019 == 0:
      ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# 2019は10と互いに素なので、
# N%2019と(N*(10**正整数))%2019は一致する
# pppppxxxxxxxを2019で割った余りとxxxxxxxを2019で割った余りが一致すれば、
# pppppは2019で割り切れることが言える

S = input()
from collections import defaultdict
amari = defaultdict(int)
for i in range(1,len(S)+1):
  amari[int(S[len(S)-i:])%2019] += 1
  
ans = 0
if 0 in amari:
  ans += amari[0]
for n in amari.values():
  ans += (n * (n-1)) // 2
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:

S = input()

mod = 2019
ctr = [0] * mod
t = 0
for i, v in enumerate(reversed(S)):
    t = (t + int(v) * 10 ** i) % mod
    ctr[t] += 1

ans = ctr[0]
for v in ctr[1:]:
    ans += v * (v - 1) // 2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections

def main():
    S = input()
    result = 0
    t = [0] * (len(S) + 1)
    for i in range(len(S)):
        t[i+1] = int(S[-i-1:]) % 2019
    count_dict = collections.Counter(t)
    for a, b in count_dict.items():
        result += b*(b-1) // 2

    print(result)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
S = input()
count = 0
exist = [0]*2019
flg = False
N = len(S)
for j in range(1,N+1):
    s = int(S[N-j:N])
    exist[s%2019] += 1
for e in exist[1:]:
    if e > 1:
        count += e-1
count += exist[0]
print(count)

Submission status: Time Limit Exceeded

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

countdic = {}
mod = 2019

for i in range(1,n+1):
    num = int(s[n-i:n])
    remainder = num%mod
    if remainder in countdic:
        countdic[remainder] += 1
    if remainder not in countdic:
        countdic[remainder] = 1

ans = 0
for key in countdic:
    ans += countdic[key]*(countdic[key]-1)//2

if 0 in countdic:
    ans += countdic[0]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# 2019は10と互いに素なので、
# N%2019と(N*(10**正整数))%2019は一致する
# pppppxxxxxxxを2019で割った余りとxxxxxxxを2019で割った余りが一致すれば、
# pppppは2019で割り切れることが言える

S = input()
from collections import defaultdict
amari = defaultdict(int)
for i in range(1,len(S)+1):
  amari[int(S[len(S)-i:])%2019] += 1
  
ans = 0
if 0 in amari:
  ans += amari[0]
for n in amari.values():
  ans += (n * (n-1)) // 2
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

s = input()
n = len(s)
ans = 0
now = 0
mp = np.zeros(2019, np.int)
mp[0] += 1
tmp = np.zeros(2019, np.int)

id = np.zeros(2019, np.int)
for i in range(2019):
    id[i] = i * 10 % 2019

for c in s:
    now *= 10;
    now += ord(c) - ord("0")
    now %= 2019

    ans += mp[now]
    mp[now] += 1
    for i in range(2019):
        tmp[id[i]] = mp[i]
    for i in range(2019):
        mp[i] = tmp[i]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
arr = [0 for i in range(2019)]
arr[0] = 1

s = input()
n = len(s)

num = 0
for i,ele in enumerate(s[::-1]):
    num += int(ele) * 10**i
    arr[num%2019] += 1


ans = 0
for m in arr:
    if m==0: continue
    ans += m*(m-1)//2

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#-------------------------------------------------------------------
import sys
def p(*_a):
  _s=" ".join(map(str,_a))
  #print(_s)
  sys.stderr.write(_s+"\n")
#-------------------------------------------------------------------

S = input()
S = S[::-1]

m = 2019

A=[0]*m
A[0]=1

a = 0
ans=0
for i,s in enumerate(S):
	a = a + ((int(s) * 10**i ) % m)
	a %= m
	
	ans += A[a]
	A[a] += 1

print(ans)

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()))
def resolve():
    S = [s for s in sr()]
    N = len(S)
    a = [0]*2019
    a[0] += 1
    t = 0
    for i in range(N):
        t += int(S.pop())*pow(10, i)
        a[t%2019] += 1
    ans = 0
    for i in range(2019):
        ans += a[i]*(a[i]-1)//2
    print(ans)
resolve()

Submission status: Time Limit Exceeded

Solution code:

S = input()

mod = 2019
ctr = [0] * mod
t = 0
for i, v in enumerate(S[::-1]):
    t = (t + int(v) * 10 ** i) % mod
    ctr[t] += 1

ans = ctr[0]
for v in ctr[1:]:
    ans += v * (v - 1) // 2
print(ans)