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 numpy as np

S = input()
n = len(S)
A = np.zeros([n,2019]) 


A[0][int(S[0])] = 1
next_index = [int(S[0])]
for i in range(0,n-1):
    s = int(S[i+1])
    next2 = []
    for j in next_index:
        #pre = (j+2019-10-s)%2019
        fol = (10*j+s)%2019
        next2.append(fol)
        A[i+1][fol] += A[i][j]
    A[i+1][s]+=1
    next2.append(s)
    next_index = set(next2)


print(int(np.sum(A[:,0])))

Submission status: Time Limit Exceeded

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

a = 0
count = 0

for i in range(l):
    a = int(S[l-i-1])
    for j in range(i+1,l):
        if int(S[l-j-1]) != 0:
            a += int(S[l-j-1])*10**(j-i)
            if j-i > 2:
                if a % 2019 == 0:
                    count += 1
            
print(count)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Apr 26 22:28:26 2020

@author: Kanaru Sato
"""

s = input()
n = len(s)
s = int(s)
dic = {}
mod = 2019

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

summation = 0
for factor in dic:
    if factor != 0:
        summation += dic[factor]

if 0 in dic:
    ans = summation-(len(dic)-1)+dic[0]
elif 0 not in dic:
    ans = summation-(len(dic))

print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
S = input()
le = len(S)
counter = 0
for i in range(4,le):
    for l in range(le-i+1):
        if i==4:
            if int(S[l:l+i])==2019  or int(S[l:l+i])==4038 or int(S[l:l+i])==6057 or int(S[l:l+i])==8076:
                counter += 1
        else: 
            if int(S[l:l+i]) % 2019 == 0:
                counter += 1
print(counter)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys

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

def main():
    s = ns()
    ans = 0
    ssum = [0]
    for si in s:
        ssum += [(ssum[-1] + int(si))%3]
    for i in range(len(s)-3):
        for j in range(i+3,len(s)):
            if ssum[i] == ssum[j+1] and ((j !=len(s)-1 and int(s[i:j+1])%2019==0) or (j ==len(s)-1 and int(s[i:])%2019==0)):
                ans += 1
    print(ans) 
    return

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
S = input()
count = 0

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

print(count)

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8
import math

s = int(input())
n = math.ceil(math.log10(s))
count = 0


for i in range(n):
    num = s % (10 ** (n - i))
    if num < 2019:
        break
    while True:
        if num % 2019 == 0:
            count += 1
            break
        num = num // 10
        if num == 0:
            break
        if num < 2019:
            break
        
print("{}".format(count))

Submission status: Time Limit Exceeded

Solution code:
S=input()
n=len(S)
count=0

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

print(count)

Submission status: Time Limit Exceeded

Solution code:
S = input()
count = 0
for i in range(len(S)):
	for j in range(i, len(S)):
		if len(S[i:j+1]) < 4:
			pass
		elif int(S[i:j+1]) % 2019 == 0:
			count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
def to10sin(listo):
  retval=0
  for i in listo:
    retval*=10
    retval += i
  return retval

#intarray=input()
intarray=[int(i) for i in input()]

nisennzyuukyuuwarikirecnt=0
#print(intarray)
#print(len(intarray))
#先頭
renzokucnt=0
for i in range(0, len(intarray) - 3):
  #ケツ
  tmp = to10sin(intarray[i:i+3])#←あえて一個少なくしている
  #print(tmpsum)
  for j in range(i+3, len(intarray)):
    tmp *= 10
    tmp+=intarray[j]
    if tmp%2019==0 :
      #print(tmp)
      i = j + 1
      renzokucnt+=1
      break
    elif renzokucnt > 0:
      nisennzyuukyuuwarikirecnt+=renzokucnt*(renzokucnt+1)//2
      renzokucnt=0

nisennzyuukyuuwarikirecnt+=renzokucnt*(renzokucnt+1)//2
print(nisennzyuukyuuwarikirecnt)

Submission status: Time Limit Exceeded

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


def solve(S: int):
    cnt = 0
    for i in range(len(str(S))):
        for j in range(i + 1, len(str(S))):
            s = str(S)[i:j+1]
            if '0' in s:
                continue
            if not int(str(S)[i:j+1]) % 2019:
                cnt += 1
    print(cnt)
    # cnt = 0
    # l = filter(lambda x: '0' not in str(x), range(2019, 200000, 2019))
    # l = [str(i) for i in l]
    # s = str(S)
    # for i in range(len(s)):
    #     if 5 + i > len(s) - 1:
    #         continue
    #     if s[i:4 + i] in l or s[i:5 + i] in l:
    #         cnt += 1
    # print(cnt)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = int(next(tokens))  # type: int
    solve(S)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
baisu=set([])

i=1
while 1:
    temp=2019*i
    if "0" not in str(temp):
        baisu.add(str(temp))
    
    if temp>20000000000:
        break
    i+=1

n=input()
cnt=0
for i in baisu:
    if i in n:
        cnt+=1

print(cnt)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
S = list(input())
n = len(S)
res = 0
cur = 0
count = [0] * 2020
ten = 10 ** n
for i, c in enumerate(map(int, S)):
    cur = cur * 10 + c
    if cur % 2019 == 0:
        res += 1
    temp = (cur * ten) % 2019
    ten //= 10
    res += count[temp]
    count[temp] += 1
print(res)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def calc(list, idx_i, idx_j):
#  target_list = list[idx_i:(idx_j + 1)]
#  int_val = int("".join(target_list))
  int_val = int("".join(list[idx_i:(idx_j + 1)]))
  return int_val % 2019 == 0

inputs = list(input())
max_idx = len(inputs) - 1
  
count = 0;
for i in range(0, max_idx + 1):
  for j in range(i + 1, max_idx + 1):
    if(j - i > 4):
      continue
    else:
      if(calc(inputs, i, j)):
        count+=1

    
print(count)

Submission status: Time Limit Exceeded

Solution code:
a=list(map(int,input()))
o=len(a)
da=0
cx=0
for i in range(o):
    for j in range(o):
        x=a[i:j+1]
        z=len(x)-1
        for h in x:
            da+=h*(10**(z))
            z = z-1
        if da%2019==0 and da!=0:
            cx+=1
        da=0
print(cx)

Submission status: Time Limit Exceeded

Solution code:
S = input()

ans = 0
for i in range(0, len(S)+1) :
    for j in range(0, len(S)+1) :
        if i>=j :
            continue

        num = int(S[i:j])

        if num >= 2019 and num % 2019 == 0 :
            ans = ans + 1

print(ans)