Problem:


Score : 600 points

Problem Statement

We have a sequence of k numbers: d_0,d_1,...,d_{k - 1}.

Process the following q queries in order:

The i-th query contains three integers n_i, x_i, and m_i.
Let a_0,a_1,...,a_{n_i - 1} be the following sequence of n_i numbers: \begin{eqnarray} a_j =  \begin{cases}    x_i & ( j = 0 ) \\    a_{j - 1} + d_{(j - 1)~\textrm{mod}~k} & ( 0 < j \leq n_i - 1 )  \end{cases}\end{eqnarray}
Print the number of j~(0 \leq j < n_i - 1) such that (a_j~\textrm{mod}~m_i) < (a_{j + 1}~\textrm{mod}~m_i).

Here (y~\textrm{mod}~z) denotes the remainder of y divided by z, for two integers y and z~(z > 0).

Constraints

All values in input are integers.

1 \leq k, q \leq 5000

0 \leq d_i \leq 10^9

2 \leq n_i \leq 10^9

0 \leq x_i \leq 10^9

2 \leq m_i \leq 10^9

Input

Input is given from Standard Input in the following format:

k q
d_0 d_1 ... d_{k - 1}
n_1 x_1 m_1
n_2 x_2 m_2
:
n_q x_q m_q

Output

Print q lines.

The i-th line should contain the response to the i-th query.

Sample Input 1

3 1
3 1 4
5 3 2

Sample Output 1

1

For the first query, the sequence {a_j} will be 3,6,7,11,14.

(a_0~\textrm{mod}~2) > (a_1~\textrm{mod}~2)

(a_1~\textrm{mod}~2) < (a_2~\textrm{mod}~2)

(a_2~\textrm{mod}~2) = (a_3~\textrm{mod}~2)

(a_3~\textrm{mod}~2) > (a_4~\textrm{mod}~2)

Thus, the response to this query should be 1.

Sample Input 2

7 3
27 18 28 18 28 46 1000000000
1000000000 1 7
1000000000 2 10
1000000000 3 12

Sample Output 2

224489796
214285714
559523809



Sample input:
3 1
3 1 4
5 3 2


Sample output:
1

Submission status: Wrong Answer

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

mod = 10**9+7 #出力の制限
N = 10**5 * 2
def cmb(n, r):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
def p(n,r):
    if ( r<0 or r>n ):
        return 0
    return g1[n] * g2[n-r] % mod

g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
# a = cmb(n,r)

import fractions
from functools import reduce
def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

k,q = m()

d = l()


for i in range(q):
    n,x,mm = m()
    co = 0

    po = [d[j] % mm for j in range(k)]


    for j in range(k):
        if po[j] == 0:
            ccc = -(-(n - j) // k)
            if ccc >= 0:
                co += ccc
    
    pp = sum(po) * ((n-1)//k)
    pp += x
    for j in range((n-1)%k):
        pp += po[j]
    
    co += pp//mm - x//mm
    
    print((n-co-1))

Submission status: Wrong Answer

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

mod = 10**9+7 #出力の制限
N = 10**5 * 2
def cmb(n, r):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
def p(n,r):
    if ( r<0 or r>n ):
        return 0
    return g1[n] * g2[n-r] % mod

g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
# a = cmb(n,r)

import fractions
from functools import reduce
def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

k,q = m()

d = l()


for i in range(q):
    n,x,mm = m()
    co = 0

    po = [d[j] % mm for j in range(k)]


    for j in range(min(k,n)):
        if po[j] == 0:
            co += -(-(n - j) // k)
    
    pp = sum(po) * ((n-1)//k)
    pp += x
    for j in range((n-1)%k):
        pp += po[j]
    
    co += pp//mm - x//mm
    
    print((n-co-1))

Submission status: Wrong Answer

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

mod = 10**9+7 #出力の制限
N = 10**5 * 2
def cmb(n, r):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
def p(n,r):
    if ( r<0 or r>n ):
        return 0
    return g1[n] * g2[n-r] % mod

g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
# a = cmb(n,r)

import fractions
from functools import reduce
def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

k,q = m()

d = l()


for i in range(q):
    n,x,mm = m()
    co = 0

    po = [d[j] % mm for j in range(k)]


    for j in range(k):
        if po[j] == 0:
            co += -(-(n - j+1) // k)
    
    pp = sum(po) * ((n-1)//k)
    pp += x
    for j in range((n-1)%k):
        pp += po[j]
    
    co += pp//mm - x//mm
    
    print((n-co-1))

Submission status: Wrong Answer

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

mod = 10**9+7 #出力の制限
N = 10**5 * 2
def cmb(n, r):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
def p(n,r):
    if ( r<0 or r>n ):
        return 0
    return g1[n] * g2[n-r] % mod

g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
# a = cmb(n,r)

import fractions
from functools import reduce
def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

k,q = m()

d = l()


for i in range(q):
    n,x,mm = m()
    co = 0

    po = [d[j] % mm for j in range(k)]


    for j in range(k):
        if po[j] == 0:
            co += -(-(n - j) // k)
    
    pp = sum(po) * ((n-1)//k)
    pp += x
    for j in range((n-1)%k):
        pp += po[j]
    
    co += pp//mm - x//mm
    
    print((n-co-1))

Submission status: Wrong Answer

Solution code:
k, q = list(map(int, input().split()))
D = list(map(int, input().split()))


for qi in range(q) :
  n, x, m = list(map(int, input().split()))
  temp_d = [0 for d in D]
  n_zero = [0 for d in D]
  for i in range(len(D)) :
    temp_d[i] = D[i] % m
    if(temp_d[i] == 0) :
      n_zero[i] = 1
  start = int(x/m)
  an = int(n/k)*sum(temp_d)+sum(temp_d[0:max((n%k)-1, 0)])+x
  end = int(an/m)
  print(n-(end-start)-(sum(n_zero)*int(n/k))-sum(n_zero[0:max((n%k)-1, 0)])-1)

Submission status: Wrong Answer

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

mod = 10**9+7 #出力の制限
N = 10**5 * 2
def cmb(n, r):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
def p(n,r):
    if ( r<0 or r>n ):
        return 0
    return g1[n] * g2[n-r] % mod

g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
# a = cmb(n,r)

import fractions
from functools import reduce
def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

k,q = m()

d = l()


for i in range(q):
    n,x,mm = m()
    co = 0

    po = [d[j] % mm for j in range(k)]


    for j in range(k):
        if po[j] == 0:
            co += -(-(n - j) // k)
    
    pp = sum(po) * ((n-1)//k)
    pp += x
    for j in range((n-1)%k):
        pp += po[j]
    
    co += pp//mm - x//mm
    
    print((n-co-1)%mod)

Submission status: Wrong Answer

Solution code:
k, q = list(map(int, input().split()))
D = list(map(int, input().split()))


for qi in range(q) :
  n, x, m = list(map(int, input().split()))
  temp_d = [0 for d in D]
  n_zero = [0 for d in D]
  for i in range(len(D)) :
    temp_d[i] = D[i] % m
    if(temp_d[i] == 0) :
      n_zero[i] = 1
  start = int(x/m)
  an = int(n/k)*sum(temp_d)+sum(temp_d[0:(n%k)-1])+x
  end = int(an/m)
  print(n-(end-start)-(sum(n_zero)*int(n/k))-sum(n_zero[0:(n%k)-1])-1)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
import pprint
sys.setrecursionlimit(10 ** 9)


INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007



k, q = LI()
D = LI()
for _ in range(q):
    n, x, m = LI()
    ret = x
    D_m = [d % m for d in D]
    zero_or_one = list(accumulate([1 if d == 0 else 0 for d in D_m]))
    Dm_acc = list(accumulate(D_m))
    ret = x + (n - 1) // k * Dm_acc[-1] + Dm_acc[(n - 1) % k - 1]
    zero_ret = (n - 1) // k * zero_or_one[-1] + zero_or_one[(n - 1) % k - 1]
    b = zero_or_one[(n - 1) % k - 1]
    print(n - 1 - (ret // m - x // m) - zero_ret)

Submission status: Wrong Answer

Solution code:
#>=はmの倍数をまたいだ回数
k,q = map(int, input().split( ))
d = list(map(int, input().split( )))
from collections import Counter
for i in range(q):
    n,x,m=map(int, input().split( ))
    dx = [di%m for di in d]
    ##あまり0をあまりmで処理
    for i in range(k):
        if dx[i]==0:
            dx[i]=m
    sm = x%m+sum(dx)*(n//k)+sum(dx[:n%k])
    print(n-1 -sm//m)

Submission status: Wrong Answer

Solution code:
k, q = map(int, input().split())
d = list(map(int, input().split()))
nxm = [list(map(int, input().split())) for _ in range(q)]

for n, x, m in nxm:
    dd = [e % m for e in d]

    ans = n - 1
    divq, divr = divmod(n, k)
    ans -= dd.count(0) * divq
    ans -= dd[:divr].count(0)

    last = x + sum(dd) * divq + sum(dd[:divr])
    ans -= last // m - x // m

    print(ans)

Submission status: Wrong Answer

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

k,q = LI()
d = LI()
nxm = [LI() for _ in range(q)]

for n,x,m in nxm:
    e = list(map(lambda x:x%m,d))
    zero = e.count(0)
    zero = zero*((n-1)//k)
    for i in range((n-1)%k+1):
        if e[i] == 0:
            zero += 1
    f = list(accumulate(e))
    s = f[-1] * ((n-1)//k)
    if (n-1)%k != 0:
        s += f[(n-1)%k-1]
    tmp = (s+x%m)//m
    print(n-1-zero-tmp)

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    k,q = LI()
    d = LI()
    for _ in range(q):
        n,x,m = LI()
        a = [((i-1)%m)+1 for i in d]
        S = sum(a)
        r = n//k
        s = S*r+(x%m)
        for i in range((n-1)%k):
            s += a[i]
        print(n-1-(s//m))
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
k,q=list(map(int,input().split()))
d=list(map(int,input().split()))
for i in range(q):
  n,x,m=list(map(int,input().split()))
  d2=[0]*k
  d0=0
  a=x
  for j in range(k):
    d2[j]=d[j]%m
    a+=d2[j]*((n+j-1)//k)
    if(d2[j]==0):
      d0+=(n+j+1)//k
  d0+=(a//m)-(x//m)
  print(n-1-d0)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

k,q = map(int,input().split())
D =list(map(int,input().split()))
for _ in range(q):
  n,x,m = map(int,input().split())
  DD = [(d-1+m)%m+1 for d in D]
  tmp = x; s = (n-1) // k
  for i, di in enumerate(DD):
    tmp += di*(s + int(n%k-1 > i))
  print(n-1-(tmp//m-x//m))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import math

#############
# Constants #
#############

MOD = 10**9 +7
INF = float('inf')

#############
# Functions #
#############

kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

#############
# Main Code #
#############

k,q = map(int, input().split())
d = list(map(int, input().split()))

while(q):
  n,x,m = map(int, input().split())
  
  for i in range(k):
    d[i] = d[i] % m
  a = x
  ans = n-1
  for i in range(n-1):
    a += d[i%k]
    if d[i%k] == 0:
      ans -= 1
    if math.floor(a/m) > math.floor((a-d[i%k])/m):
      ans -= 1

  
    
  
    
  
  
  
  print(ans)
  q -= 1

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

k,q = map(int,input().split())
D =list(map(int,input().split()))
for _ in range(q):
  n,x,m = map(int,input().split())
  DD = [(d-1+m)%m+1 for d in D]
  tmp = x; s = n // k
  for i, di in enumerate(DD):
    tmp += di*(s + int(n%k-1 > i))
  print(n-1-(tmp//m-x//m))

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline


def main():
    K, Q = map(int, input().split())
    D = list(map(int, input().split()))

    for _ in range(Q):
        n, x, m = map(int, input().split())
        md = [D[i] % m for i in range(K)]
        smda = 0
        mda0 = 0
        for i in range((n - 1) % K):
            if md[i] == 0:
                mda0 += 1
            smda += md[i]
        smd = smda
        md0 = mda0
        for i in range((n - 1) % K, K):
            if md[i] == 0:
                md0 += 1
            smd += md[i]
        roop = (n - 1) // K
        res = n - 1 - (x % m + smd * roop + sum(md)) // m - md0 * roop - mda0
        print(res)


main()

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
printV = lambda x: print(*x, sep="\n")
printH = lambda x: print(" ".join(map(str,x)))
def IS(): return sys.stdin.readline()[:-1]
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LII(rows_number): return [II() for _ in range(rows_number)]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]

def main():
	k,q = MI()
	d = LI()
	d = np.array(d)
	ans = [0]*q
	for i in range(q):
		n,x,m = MI()
		d_modm = d%m
		zero = (n//k)*np.sum(d_modm==0) + np.sum((d_modm==0)[:n%k-1])
		lst = x + (n//k)*np.sum(d_modm) + np.sum((d_modm)[:n%k-1])
		ans[i]=n-1-zero-(lst//m-x//m)
	printV(ans)
if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline


def main():
    K, Q = map(int, input().split())
    D = list(map(int, input().split()))

    for _ in range(Q):
        n, x, m = map(int, input().split())
        md = []
        smd = 0
        md0 = 0
        roop = (n - 1) // K
        amari = (n - 1) % K
        for i in range(K):
            d = D[i] % m
            md.append(d)
            smd += d
            if d == 0:
                md0 += 1
            if i == amari - 1 or i == amari + K - 1:
                smda = smd
                mda0 = md0
        res = n - 1 - (x % m + smd * roop + smda) // m - md0 * roop - mda0
        print(res)


main()

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline


def main():
    K, Q = map(int, input().split())
    D = list(map(int, input().split()))

    for _ in range(Q):
        n, x, m = map(int, input().split())
        md = []
        smd = 0
        md0 = 0
        roop = (n - 1) // K
        amari = (n - 1) % K
        for i in range(K):
            d = D[i] % m
            md.append(d)
            smd += d
            if d == 0:
                md0 += 1
            if i == amari - 1:
                smda = smd
                mda0 = md0
        res = n - 1 - (x % m + smd * roop + smda) // m - md0 * roop - mda0
        print(res)


main()

Submission status: Wrong Answer

Solution code:
k, q = map(int, input().split())
d = list(map(int, input().split()))

def solve():
    n, x, m = map(int, input().split())
    ans = 0
    rn = (n - 1) % k
    f = x % m
    for i in range(k):
        if d[i] % m == 0:
            continue
        if i < rn:
            c = (n - 1) // k + 1
        else:
            c = (n - 1) // k
        print(i, c)
        ans += c
        f += c * (d[i] % m)
    print(ans, f)
    ans -= f // m
    print(ans)

for _ in range(q):
    solve()

Submission status: Wrong Answer

Solution code:
k, q = map(int, input().split())
d = list(map(int, input().split()))

def sof(n, a, b, c):
    if a == 0:
        return (n + 1) * (b // c)
    if a >= c or b >= c:
        return n * (n + 1) // 2 * (a // c) + (n + 1) * (b // c) + sof(n, a % c, b % c, c)
    m = (a * n + b) // c
    return n * m - sof(m - 1, c, c - b - 1, a)

def solve():
    n, x, m = map(int, input().split())
    ans = 0
    rn = (n - 1) % k
    final = x
    for i in range(k):
        if d[i] % m == 0:
            continue
        if i < rn:
            c = (n - 1) // k + 1
        else:
            c = (n - 1) // k
        ans += c
        final += c * (d[i] % m)
    ans -= final // m
    print(ans)

for _ in range(q):
    solve()

Submission status: Wrong Answer

Solution code:
from collections import *
from itertools import *
from bisect import *
import copy

k,q=map(int,input().split())
D=list(map(int,input().split()))
nxm=[list(map(int,input().split())) for i in range(q)]

for n,x,m in nxm:
    dlst=[d%m for d in D]
    count0=[(dlst[0]==0 )* 1]

    lst=[dlst[0]]
    for i in range(1,k):
        lst.append(lst[i-1]+dlst[i])
        count0.append(count0[i-1]+1*(dlst[i]==0))

    num2=(n-1)//k * lst[-1] +  x
    if n%k-2>=0:
        num2+=lst[n%k-2]
    #print(num2,n%k)
    num1=n-1-((n-1)//k)*count0[-1]-(num2//m-x//m)
    if n%k-2>=0:
        num1-=count0[n%k-2]
    print(num1)

Submission status: Wrong Answer

Solution code:
from collections import *
from itertools import *
from bisect import *
import copy

k,q=map(int,input().split())
D=list(map(int,input().split()))
nxm=[list(map(int,input().split())) for i in range(q)]

for n,x,m in nxm:
    dlst=[d%m for d in D]
    count0=[(dlst[0]==0 )* 1]

    lst=[dlst[0]]
    for i in range(1,k):
        lst.append(lst[i-1]+dlst[i])
        count0.append(count0[i-1]+1*(dlst[i]==0))

    num2=(n-1)//k * lst[-1] +  x
    if n%k-2>=0:
        num2+=lst[n%k-2]
    #print(num2,n%k)
    num1=n-1-((n-1)//k)*count0[-1]-(num2//m-x//m)
    if n%k-2:
        num1-=count0[n%k-2]
    print(num1)

Submission status: Wrong Answer

Solution code:
K, Q = map(int, input().split())
D = [int(a) for a in input().split()]
for _ in range(Q):
    N, X, M = map(int, input().split())
    if N <= K + 1:
        A = [0] * N
        A[0] = X % M
        ans = 0
        for i in range(N-1):
            A[i+1] = (A[i] + D[i]) % M
            if A[i+1] > A[i]:
                ans += 1
        print(ans)
        continue
    ans = N - 1
    A = [0] * (K+1)
    A[0] = X % M
    for i in range(K):
        d = D[i] % M
        if d == 0:
            ans -= (N-i-1) // K + 1
        A[i+1] = A[i] + d
    ans -= (A[(N-1)%K] + (A[K] - A[0]) * ((N-1) // K))//M - A[0]//M
    print(ans)

Submission status: Wrong Answer

Solution code:
K, Q = map(int, input().split())
D = [int(a) for a in input().split()]
for _ in range(Q):
    N, X, M = map(int, input().split())
    if N <= K:
        A = [0] * N
        A[0] = X % M
        ans = 0
        for i in range(N-1):
            A[i+1] = (A[i] + D[i]) % M
            if A[i+1] > A[i]:
                ans += 1
        print(ans)
        continue
    ans = N-1
    A = [0] * (K+1)
    A[0] = X % M
    for i in range(K):
        d = D[i] % M
        if d == 0:
            ans -= (N-i-1) // K + 1
        A[i+1] = A[i] + d
    ans -= (A[(N-1)%K] + (A[K] - A[0]) * ((N-1) // K))//M - A[0]//M
    print(ans)

Submission status: Wrong Answer

Solution code:
k,q=map(int,input().split())
d=list(map(int,input().split()))
for i in range(q):
    n,x,m=map(int,input().split())
    l=[i%m if i%m!=0 else m for i in d]
    print(n-1-(x+((n-1)//k)*sum(l)+sum(l[:(n-1)%k]))//m+x//k)

Submission status: Wrong Answer

Solution code:
k,q=map(int,input().split())
d=list(map(int,input().split()))
for i in range(q):
    n,x,m=map(int,input().split())
    l=[i%m if i%m!=0 else m for i in d]
    print(n-1-(x+((n-1)//k)*sum(l)+sum(l[:(n-1)%k]))//m+x//k)

Submission status: Wrong Answer

Solution code:
k,q=map(int,input().split())
d=list(map(int,input().split()))
for i in range(q):
    n,x,m=map(int,input().split())
    l=[i%m if i%m!=0 else m for i in d]
    print(n-((n//k)*sum(l)+sum(l[:n%k-1]))//m)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline

k, q = [int(item) for item in input().split()]
d = [int(item) for item in input().split()]
nxm = []
for _ in range(q):
    n, x, m = [int(item) for item in input().split()]
    nxm.append((n, x, m))

for n, x, m in nxm:
    newd = []
    is_zero = []
    sum_newd = 0
    for item in d:
        sum_newd += item % m
        newd.append(item % m)
        is_zero.append(item % m == 0)
    loop = n // k
    rest = n % k
    total = loop * (sum_newd) + (x % m) 
    zeros = loop * sum(is_zero)
    if rest > 0:
        total += sum(newd[:rest-1])
        zeros += sum(is_zero[:rest-1])
    rollover = total // m
    ret = n - 1 -rollover - zeros
    print(ret)

Submission status: Wrong Answer

Solution code:
import sys
from itertools import accumulate


def solve(n, x, m):
    eee = [d % m for d in ddd]
    acc = list(accumulate(eee))
    zero = [int(e == 0) for e in eee]
    zero_acc = list(accumulate(eee))
    loop, rem = divmod(n - 1, k)
    tot = x % m + acc[-1] * loop
    tot_zero = zero[-1] * loop
    if rem > 0:
        tot += acc[rem - 1]
        tot_zero += zero_acc[rem - 1]
    dame = tot // m
    # print(n, x, m)
    # print(eee)
    # print(acc)
    # print(loop, rem)
    # print(tot, dame)
    return n - 1 - dame - tot_zero


k, q = map(int, input().split())
ddd = list(map(int, input().split()))
buf = []
for line in sys.stdin:
    n, x, m = map(int, line.split())
    buf.append(solve(n, x, m))
print('\n'.join(map(str, buf)))

Submission status: Wrong Answer

Solution code:
kq = input().split()
k, q = int(kq[0]), int(kq[1])
d = input().split()
for i in range(len(d)):
    d[i] = int(d[i])
for i in range(q):
    nxm = input().split()
    n,x,m = int(nxm[0]),int(nxm[1]),int(nxm[2])
    count = 0
    mem = 0
    for j in range(n-1):
        if j == 0:
            if (x % m) < ((x+(d[0])) % m):
                count += 1
            mem = x + (d[0]%k)
        else:
            mem = mem+(d[(j-1)%k])
            if (mem % m) < ((mem+(d[j%k])) % m):
                count += 1 
                
print(count)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

from itertools import accumulate

def solve():
    k,q = map(int, input().split())
    D = [0]+list(accumulate(map(int, input().split())))
    res_l = []
    for _ in range(q):
        n,x,m = map(int, input().split())
        c = 0
        S = D[-1]%m
        RS = [(i*S)%m for i in range((n//k)+2)]
        R = [(x+d)%m for d in D[::-1]]
        c = sum(R[j%k]+RS[j//k] < R[(j+1)%k]+RS[(j+1)//k] for j in range(n))

        res_l.append(str(c))
    res = '\n'.join(res_l)
    return res

if __name__ == '__main__':
    print(solve())