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: Runtime Error

Solution code:

// C++ implementation of the approach 
#include <bits/stdc++.h> 
using namespace std; 
  
// Function to return the count of sub-strings 
// of str that are divisible by k 
int countSubStr(string str, int len, int k) 
{ 
    int count = 0; 
  
    for (int i = 0; i < len; i++) { 
        int n = 0; 
  
        // Take all sub-strings starting from i 
        for (int j = i; j < len; j++) { 
            n = n * 10 + (str[j] - '0'); 
  
            // If current sub-string is divisible by k 
            if (n % k == 0) 
                count++; 
        } 
    } 
  
    // Return the required count 
    return count; 
} 
  
// Driver code 
int main() 
{ 
    string str;
    cin>>str;
    int len = str.length(); 
    int k = 2019; 
    cout << countSubStr(str, len, k); 
  
    return 0; 
}

Submission status: Runtime Error

Solution code:
if __name__ == '__main__':
    str = input()
    count = 0
    d=[]
    b=(int(str))//2019+1
    for i in range(0,b) :
       d.append(2019*i)
    for item in d:
        for i in range(0,len(str)+1):
            if int(str[i:i+len(item)])==item:
                count=count+1
    print(count)

Submission status: Runtime Error

Solution code:
A=list(input())
ans=0
for i in range(len(A)-1):
  for j in range(i+1,len(A)):
    if sum(A[i:j+1])%3!=0:
      continue
    if int("".join(A[i:j+1]))%2019==0:
      ans+=1
print(ans)

Submission status: Runtime Error

Solution code:
#D
s = input()
count = 0
# print(len(s))
for left in range(len(s) - 1):
    for right in range(left + 1, len(s)):
        # print(left + 1, right + 1)
        if int(float(s[left:right+1])) % 2019 == 0:
            # print(s[left:right])
            count += 1
print(count)

Submission status: Runtime Error

Solution code:
import sys

S = input()

if int(S)<2019:
    print(0)
    sys.exit()

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

print(len(Sl))

Submission status: Runtime Error

Solution code:
a = input()
ans = 0

for i in range(len(a)-1):
  for j in range(len(a)-i-4):
    k = i+j+4
    b = []
    for l in range(k-i):
      l = l+i
      b.append(a[l])
    c = int(b)
    if c%2019 == 0:
      ans = ans +1
      
print(ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
S=int(input())
m=S//2019
ans=0
baisu=[]
for i in range(m):
  baisu.append(2019*(i+1))
for num in baisu:
  if num in str(S):
    ans += 1
print(ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
S = input()

n = [str(2019*i) for i in range(1:100)]
print(n)

Submission status: Runtime Error

Solution code:
s = input()
cnt = 0

for i in range(len(s)):
    for j in range(i, len(s)):
        s_a = s[i:j+1]

        if int(float(s_a))%2019 == 0:
            cnt += 1

print(cnt)

Submission status: Runtime Error

Solution code:
def main():
    s = list(input())
    h = [[] for i in range(10)]
    for i in range(1,100):
        a = 2019 * i
        sa = str(a)
        if '0' in sa:
            continue
        ha = int(sa[0])

        h[ha].append(list(sa))
    ans = 0
    if len(s) < 5:
        print(0)
        return
    for i, s_top in enumerate(s):
        if i > len(s) - 3:
            break
        for j, hh in enumerate(h[int(s_top)]):
            flg = True
            for k, hhs in enumerate(hh):
                if s[i + k] != hhs:
                    flg = False
                    break
            if flg :
                ans += 1
    print(ans)
if __name__=='__main__':
    main()

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
S = input()
s = len(S)
a = []
ans = 0
for i in range(s):
  for j in range(i+3, s):
    if int(S[i:j]) % 3 == 0:
      a.append([i,j])
for t in range(len(a)):
  i, j = a[t]
  if a[i:j] % 673 == 0:
    ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
S=int(input())
m=S//2019
ans=0
baisu=[]
for i in range(m):
  baisu.append(2019*(i+1))
for num in basiu:
  if num in str(S):
    ans += 1
print(ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
S_str=str(input())
S_list=list(S_str)
S=int(S_str)
N=len(S_str)

mod=[0]*2018
mod[0]=1

for i in range(N):
    #print(i+1,S,S%2019)
    mod[S%2019]+=1
    S-=int(S_list[i])*(10**(N-1-i))

def culc(x):
    return x*(x-1)//2


ans=0
for j in range(len(mod)):
    ans+=culc(mod[j])

print(ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
S = input()

fl = [False]*len(S)
l = 0
res = 0

for i in range(len(S)-3):
    if fl[i]:
        continue
    
    x = int(S[i:i+3])
    cnt = 0
    for j in range(i+3, len(S)):
        x *= 10
        x += int(S[j])
        x %= 2019
        if x == 0:
            cnt += 1
            fl[l] = True
            l = j+1
    
    res += (cnt+1)*cnt//2

print(res)

Submission status: Runtime Error

Solution code:
s=input()
a=0
b=''
import sys
for i in range(len(s)):
    b+=(s[i]+s[i+1]+s[i+2])
    for j in range(i+3,len(s)):
        b+=s[j]
        if int(b)%2019==0:
            a+=1
        
    b=''
    if len(s)-i==3:
        break
        
print(a)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
s=int(input())
n=len(str(s))
t=0
for j in n:
    j+=1
    for i in j:
        i+=1
        k=s
        k//=10**(n-j)
        k%=(j-i+1)
        if k%2019==0:
            t+=1
print(t)

Submission status: Runtime Error

Solution code:
S = input()

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
s = input()
L = [s[i] for i in range(len(s))]
ans = 0

for j in range(0,len(L)-3):
  for k in range(3,len(L)):
    a = int(L[j:k+1])
    if a % 2019 == 0:
      ans += 1
print(ans)

Submission status: Runtime Error

Solution code:


anslist = []


def solve():

    S = input()

    def dfs(s, start, end):
        global anslist
        if end == len(s)+1:
            return

        if int(s[start:end]) % 2019 == 0:
            anslist.append(str(start)+str(end))

        dfs(s, start, end+1)
        dfs(s, start+1, end+1)

    dfs(S, 0, 4)
    print(len(set(anslist)))


if __name__ == "__main__":
    solve()

Submission status: Runtime Error

Solution code:
N = int(input())
S = []
ans = N
for i in range(N):
    S.append(input())

for i in range(N):
    flg = 0
    j  = 0
    while(flg == 0 and j < i):
        if i != j:
            if S[j] == S[i]:
                S[j] = ''
                ans = ans - 1
                flg = 1
        j = j+1
print(ans)

Submission status: Runtime Error

Solution code:
S = input()
count = 0
double = [(2019)*i for i in range(int(int(S)/2019)+1)]
for i in double:
  if str(i) in S:
    count += 1
print(count)

Submission status: Runtime Error

Solution code:
s = input()

i = 0
j = 4
ketasu = 4
l = len(s)

c = 0
while True:
  bubun = s[i:j]
  
  if int(bubun) % 2019 == 0:
    c += 1
  
  if j == l:
    i = 0
    ketasu += 1
    j = ketasu
    if ketasu > l:
      break
  else:
    i += 1
    j += 1
  

print(c)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
n=int(input())

n=int(input())

l=len(str(n))

c=0
for i in range(1,l-2):
    for j in range(i+3,l+1):
        if int(str(n)[i-1:j])%2019==0:
            c+=1
            #print(i,j)
            #print(str(n)[0:j])
print(c)

Submission status: Runtime Error

Solution code:
#d
N = int(input())
s  = str(N)

if len(s)<4:
    print(0)
else:
    number=0
    for j in range(N):
        for i in range(j+1,N):
            a=int(s[j:i])
            if a%2019==0:
                number+=1
    print(number)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
List=[0]*len(s)
List[0]=int(s[0])
for i in range(len(s)-1):
  List[i+1]=10*List[i]+int(s[i+1])
count=0
for i in range(len(s)):
  for j in range(i+1):
    if (List[i]%(10**(j+1)))%2019==0:
      count+=1
print(count)

Submission status: Runtime Error

Solution code:
s = input()
s += '0'



mod = 2019
cnt = {}
ans = 0
p = 0
for i in range(len(s)-1,-1,-1):
    m = int(s[i])
    
    
    x = (m*(10**(len(s)-i))+ x )%mod
    if x not in cnt:cnt[x] = 0
    ans += cnt[x]
    cnt[x] +=1
    
print(ans)

Submission status: Runtime Error

Solution code:
/*input
1817181712114
*/
#include <bits/stdc++.h>
using namespace std; 
#define int long long int
#define max(x, y) ((x) > (y) ? (x) :(y))
#define pii pair< int , int> 
#define vi vector<int>
#define fore( i ,st) for ( int i= 0 ; i < (int)(st) ; i ++)
#define REP( i , st , en ) for ( int i =st; i < (int)en; i++)
#define REPD( i , en , st ) for ( int i =en; i >= (int)st; i--)
#define SZ(a) (int)a.size()
#define all(v) v.begin() , v.end()
#define pb push_back
#define F first
#define S second
#define bitch_i_m_on_fiyaah_yeahhhh ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

// const int mod = 998244353;
const int mod = 1e9+7;
ostream& operator << ( ostream&  o, vector<int> s){for ( int i = 0;  i < (int)s.size() ; i++)o << s[i] << " ";o << "\n";return o;}
void  add( int &a, int b){a = a + b;if ( a< 0 ) a += mod; if ( a> mod ) a-= mod;}
void sub( int &a, int b){a = a - b;if ( a < 0) a += mod;}
int mul( int a , int b){return ((a %mod) * (b %mod) ) %mod;}
int exp( int a , int pow){ return (pow == 0 ? 1 : ( pow & 1  ? mul ( a ,exp( mul(a, a) , pow /2) ) : exp(mul(a ,a) , pow/2)));}
int gcd(int a, int b) { return b ? gcd(b, a%b) : a; }
// const int inf = 1e18;
const int maxn = 2e5 + 5;

vector<int> cnt[maxn];

void solve(int test ) 
{		
	string s;
	cin >> s;
	int n = s.size();
	int M=  2019;
	map<int , int > m;
	int sum =0;
	int pow =1;
	m[0] =1;
	int ans=0;
	for ( int i = n -1; i >= 0; i--){
		sum =(sum%M + ((s[i] - '0')*pow)%M)%M;
		pow = (pow%M * 10)%M;
		if ( m.count(sum)) ans+=m[sum];
		m[sum]++;
		// cout << i << " " << sum << "\n";
	}
	cout<< ans;

}
signed main(){
	bitch_i_m_on_fiyaah_yeahhhh
	int t =1; 
	// cin >> t;
	for ( int i = 0 ; i < t; i++)
	solve(i+1 );
}

Submission status: Runtime Error

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

s = input()
MOD = 2019

dp = [0] * ((MOD) * (len(s) + 1))
# dp = [[0] * (MOD) for i in range(len(s) + 1)]

dp[0] = 0
for i in range(len(s)):
    tmp = int(s[i])
    dp[(i + 1) * MOD + tmp] += 1
    for val in range(MOD):
        dp[(i + 1) * MOD + (val * 10 + tmp) % MOD] += dp[i * MOD + val]

ans = 0
for i in range(len(s) + 1):
    ans += dp[i * MOD]
    
print(ans)

Submission status: Runtime Error

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)

def LI(): return list(map(int, stdin.readline().split()))
def LS(): return list(stdin.readline())

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

Submission status: Runtime Error

Solution code:
    all = input()
    total = 0

    for n in range(len(all)):
        i=4
        x=total
        while n+i<=len(all):
            cut = int(all[n:n+i])
            if cut%2019 == 0:
                total+=1
                break
            else:
                i+=1
    print(total)

Submission status: Runtime Error

Solution code:
def main():
    from builtins import int, map, list, print, len
    import sys
    sys.setrecursionlimit(10 ** 6)

    input = sys.stdin.readline
    input_list = (lambda: input().rstrip().split())
    input_number = (lambda: int(input()))
    input_number_list = (lambda: list(map(int, input_list())))

    S = input()
    p = []
    for i in range(len(S)-4):
        for j in range(i+4,len(S)):
            p.append(S[i:j])
    cnt = 0
    for i in range(len(p)):
        pi = int(p[i])
        if pi%2019 == 0:
            cnt+=1
    print(cnt)
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
a, b, c, d = map(int,input().split())

if (a - 1) // d + 1 >= (c - 1) // b + 1 :
    print("Yes")
else : print("No")

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
#d
N = int(input())

if len(N)<4:
    print(0)
else:
    number=0
    for j range(N):
        for i range(N):
            a=N[j:i]%2019
            if a==0:
                number+=1
    print(number)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
s = input()
n = len(s)

l_sum = [0]
for i in range(n):
    x = (l_sum[-1] + int(s[n-i-1]) * (10 ** i)) % 2019
    l_sum.append(x)

#print(l_sum)
l_sum.sort()
ans = 0
tmp = 0
cnt = 1
for i in range(1, len(l_sum)):
    if l_sum[i] == tmp:
        cnt += 1
    else:
        ans += cnt * (cnt - 1) // 2
        cnt = 1
        tmp = l_sum[i]

ans += cnt * (cnt - 1) // 2
print(ans)

Submission status: Runtime Error

Solution code:
A, B, C, D = list(map(int, input().split()))

a_count = A // D + (1 if A % D else 0)
t_count = C // B + (1 if C % B else 0)
ans = 'No' if t_count < a_count else 'Yes'
#  print(t_count, a_count)
print(ans)

Submission status: Runtime Error

Solution code:
s = input()
a = []
for i in range(len(s)):
    for j in range(i+1, len(s)+1):
        a.append(s[i:j])

l = []
x = 2019
while x<=200000:
    l.append(x)
    x += 2019
ans = 0

for x in l:
    ans += a.count(str(x))
print(ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
a=2019
for i in range(int(a**0.5)):
  if a%i==0:
    print(i)
    break

Submission status: Runtime Error

Solution code:
N = int(input())
S = [ input() for _ in range(N) ]
print(len(set(S)))

Submission status: Runtime Error

Solution code:

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

mod = 2019
ss = [0]
tmp = 0
for i, s in enumerate(S[::-1]):
    tmp += s * pow(10, i, mod)
    tmp %= mod
    ss.append(tmp)

cnts = [0] * 2018
ans = 0
for s in ss:
    ans += cnts[s]
    cnts[s] += 1

print(ans)