Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], skipTags: ["script","noscript","style","textarea","code"], processEscapes: true }});

Slimming Plan

  Chokudai loves eating so much. However, his doctor Akensho told him that he was overweight, so he finally decided to lose his weight.

  Chokudai made a slimming plan of a $D$-day cycle. It is represented by $D$ integers $w_0, ..., w_{D-1}$. His weight is $S$ on the 0-th day of the plan and he aims to reduce it to $T$ ($S > T$). If his weight on the $i$-th day of the plan is $x$, it will be $x + w_{i\%D}$ on the $(i+1)$-th day. Note that $i\%D$ is the remainder obtained by dividing $i$ by $D$. If his weight successfully gets less than or equal to $T$, he will stop slimming immediately.

  If his slimming plan takes too many days or even does not end forever, he should reconsider it.

  Determine whether it ends or not, and report how many days it takes if it ends.

Input

  The input consists of a single test case formatted as follows.

$S$ $T$ $D$
$w_0 ... w_{D-1}$

  The first line consists of three integers $S$, $T$, $D$ ($1 \leq S, T, D \leq 100,000, S > T$). The second line consists of $D$ integers $w_0, ..., w_{D-1}$ ($-100,000 \leq w_i \leq 100,000$ for each $i$).

Output

  If Chokudai's slimming plan ends on the $d$-th day, print $d$ in one line. If it never ends, print $-1$.

Sample Input 1

65 60 3
-2 3 -4

Output for Sample Input 1

4

  Chokudai's weight will change as follows: $65 \rightarrow 63 \rightarrow 66 \rightarrow 62 \rightarrow 60$.

Sample Input 2

65 60 3
-2 10 -3

Output for Sample Input 2

-1

  Chokudai's weight will change as follows: $65 \rightarrow 63 \rightarrow 73 \rightarrow 70 \rightarrow 68 \rightarrow 78 \rightarrow 75 \rightarrow ...$.

  

Sample Input 3

100000 1 1
-1

Output for Sample Input 3

99999

Sample Input 4

60 59 1
-123

Output for Sample Input 4

1



Sample input:
65 60 3
-2 3 -4


Sample output:
4

Submission status: Accepted

Solution code:
S, T, D = map(int, input().split())
S -= T
*W, = map(int, input().split())
F = sum(W)
if F >= 0:
    su = S
    for i, w in enumerate(W):
        su += w
        if su <= 0:
            print(i+1)
            break
    else:
        print(-1)
    exit(0)
su = 0
mi = 0
for d in W:
    su += d
    mi = min(mi, su)

k = max((S+mi-F-1) // -F, 0)
S += k*F
for i, w in enumerate(W):
    S += w
    if S <= 0:
        print(i+1+k*D)
        break
else:
    assert 0

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    s, t, d = LI()
    w = LI()
    sumw = sum(w)
    sb = s
    mins = s
    for i in range(d):
        sb += w[i]
        mins = min(mins, sb)
        if sb <= t:
            print(i + 1)
            return
    if sumw >= 0:
        print(-1)
    else:
        ans = ((mins - t) // abs(sumw)) * d
        #print(ans, s, d, t, sumw)
        s += ans // d * sumw
        i = 0
        while 1:
            if s <= t:
                print(ans + i)
                return
            s += w[i%d]
            i += 1
        print(ans+i+1)
    return

#B
def B():
    return

#C
def C():
    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    A()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
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():
    s,t,d = LI()
    w = LI()
    W = -sum(w)
    if W <= 0:
        for i in range(d):
            s += w[i]
            if s <= t:
                print(i+1)
                return
        print(-1)
    else:
        S = [s]
        for i in range(d):
            S.append(S[-1]+w[i])
            if S[-1] <= t:
                print(i+1)
                return
        m = min(S)
        for j in range(d+1):
            if S[j] == m:
                break
        s = S[j]
        w = w[j:]+w[:j]
        k = (s-t)//W
        s -= k*W
        if s <= t:
            print(k*d+j)
            return
        for i in range(d):
            s += w[i]
            if s <= t:
                print(k*d+i+1+j)
                return
    return

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