Problem:


Score : 700 points

Problem Statement

N people are waiting in a single line in front of the Takahashi Store. The cash on hand of the i-th person from the front of the line is a positive integer A_i.

Mr. Takahashi, the shop owner, has decided on the following scheme: He picks a product, sets a positive integer P indicating its price, and shows this product to customers in order, starting from the front of the line. This step is repeated as described below.

At each step, when a product is shown to a customer, if price P is equal to or less than the cash held by that customer at the time, the customer buys the product and Mr. Takahashi ends the current step. That is, the cash held by the first customer in line with cash equal to or greater than P decreases by P, and the next step begins.

Mr. Takahashi can set the value of positive integer P independently at each step.

He would like to sell as many products as possible. However, if a customer were to end up with 0 cash on hand after a purchase, that person would not have the fare to go home. Customers not being able to go home would be a problem for Mr. Takahashi, so he does not want anyone to end up with 0 cash.

Help out Mr. Takahashi by writing a program that determines the maximum number of products he can sell, when the initial cash in possession of each customer is given.

Constraints

1 ≦ | N | ≦ 100000

1 ≦ A_i ≦ 10^9(1 ≦ i ≦ N)

All inputs are integers.

Input

Inputs are provided from Standard Inputs in the following form.

N
A_1
:
A_N

Output

Output an integer representing the maximum number of products Mr. Takahashi can sell.

Sample Input 1

3
3
2
5

Sample Output 1

3

As values of P, select in order 1, 4, 1.

Sample Input 2

15
3
1
4
1
5
9
2
6
5
3
5
8
9
7
9

Sample Output 2

18



Sample input:
3
3
2
5


Sample output:
3

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
gosa = 1.0 / 10**10
mod = 10**9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    n = I()
    a = [I() for _ in range(n)]
    t = 1
    r = a[0] - 1
    for c in a[1:]:
        if c > t+1:
            r += (c-t-2) // (t+1) + 1
        elif c == t+1:
            t = c

    return r


print(main())

Submission status: Accepted

Solution code:
def main():
    n = int(raw_input())
    a = [int(raw_input()) for _ in xrange(n)]
    #p = []
    plen = 0
    maxa = 0
    for amt in a:
        minp = maxa + 1
        items = (amt - 1) / minp
        #print amt, minp, items
        #p.extend([minp] * items)
        plen += items
        if items > 0:
            #p[-1] += (amt - 1) % minp
            rem = 1
        else:
            rem = amt
        maxa = max(maxa, rem)
    #print len(p)
    #for pi in p:
    #    print pi
    print plen
main()

Submission status: Accepted

Solution code:
n=int(input())
m1=int(input())
ans=m1-1
cur=2
for i in range(n-1):
    m=int(input())
    if m==cur:
        cur+=1
    ans+=(m-1)//cur
print(ans)

Submission status: Accepted

Solution code:
N = int(raw_input())
res = 0
q = 1
 
for i in range(N):
    m = int(raw_input())
    res += int((m-1)/q)
    if q == 1 or m == q:
        q += 1
print res

Submission status: Accepted

Solution code:
N = int(input())
A = [int(input()) for _ in range(N)]

now = 2
ans = 0
for i, a in enumerate(A):
    if i == 0:
        ans += a - 1
    else:
        if a > now:
            ans += (a - 1) // now
        elif a == now:
            now = a + 1
print(ans)

Submission status: Accepted

Solution code:
n = int(raw_input())
a = []
t = 1
count = 0
for i in xrange(n):
    a.append(int(raw_input()))
for v in a:
    if t == 1:
        count += v - 1
        t += 1
    elif v > t:
        if v % t == 0:
            count += v / t - 1
        else:
            count += v / t
    elif v == t:
        t += 1
print count

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

n = int(input())
arr = [int(input()) for i in range(n)]
count = arr[0]-1
m = 2
for a in arr[1:]:
    if a > m:
        count += (a - 1) // m
    if a == m:
        m += 1
print(count)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

n = int(input())
arr = []
for i in range(n):
    arr.append(int(input()))
count = max(arr[0]-1,0)
index = 2
for i in range(1,n):
    if arr[i] > index:
        count += (arr[i] - 1) // index
    if arr[i] == index:
        index += 1
print(count)

Submission status: Accepted

Solution code:
N = int(input())
A = []
for i in range(N):
	A.append(int(input()))
c = 0
sold = 0
i = 0
while i<len(A):
	if A[i] == c+1:
		i+=1
		c+=1
	elif A[i]<=2*(c+1) and A[i]>c+1:
		i+=1
		sold+=1
		if c == 0:
			c = 1
	elif A[i]>2*(c+1) and A[i]>c+1:
		sold+=((A[i]-1)//(c+1))
		i+=1
		if c == 0:
			c = 1
	else:
		i+=1
print(sold)

Submission status: Accepted

Solution code:
n=int(raw_input())
a=[int(raw_input()) for _ in xrange(n)]
ans=a[0]-1
maxa=2
for i in xrange(1,n):
    if maxa==a[i]:
        maxa=a[i]+1
    else:
        if maxa<a[i]:
            if a[i]%maxa==0:
                ans+=a[i]/maxa-1
            else:
                ans+=a[i]/maxa
print(ans)

Submission status: Accepted

Solution code:
N = int(raw_input())
A = [int(raw_input()) for i in xrange(N)]
ans = A[0] - 1
d = 2
for i in xrange(1, N):
    ans += (A[i] - 1)/d
    if A[i] == d: d += 1
print ans

Submission status: Accepted

Solution code:
def read():
    return int(input())

def reads(sep=None):
    return list(map(int, input().split(sep)))

def main():
    n = read()
    a = [read() for _ in range(n)]
    s = 0
    c = 2
    for i in range(n):
        if i == 0:
            s = a[i] - 1
            continue
        x = a[i] // c
        if c == a[i]:
            c += 1
            x = 0
        elif a[i] % c == 0:
            x -= 1
        s += x
    print(s)

main()

Submission status: Accepted

Solution code:
N=int(input())
a=[0]*N
for i in range(N):
    a[i]=int(input())

minimum=2
count=a[0]-1
a.pop(0)
for i in  a:
   if(minimum<i):
       if i%minimum:
           count+= i//minimum
       else :
           count+= (i//minimum-1)
   else:
       minimum=max(minimum,i+1)
print(count)

Submission status: Accepted

Solution code:
n = int(raw_input())
a = [int(raw_input()) for i in range(n)]
res = 0
m = 0
for i, e in enumerate(a):
    if e - (m+1) > 0:
        t = e - (m+1)
        if t % (m+1) == 0:
            res += t / (m+1)
            m = min(m, e - t)
        else:
            res += t / (m+1) + 1
    else:
        m = max(e, m)
    if m == 0:
        m += 1
print res

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
N = int(input())
As = []
for i in range(N):
    As.append(int(input()))

mn = 1
ans = 0
for a in As:
    if mn == 1:
        ans += a - 1
        mn = 2
    else:
        if mn == a:
            mn += 1
        else:
            ans += (a - 1) // mn
print(ans)

Submission status: Accepted

Solution code:
import sys

n = int(input())

ai = []
for i in range(0, n):
    ai.append(int(input()))

count = 0
iter = 0
r = 1

if len(ai) == 1:
    print(ai[0] - 1)
    sys.exit()

while True:
    if iter == 0 and ai[0] > 1:
        count += ai[0] - 1
        ai[0] = 1
    else:
        while ai[iter] <= r + 1:
            r = max(r, ai[iter])
            iter += 1
            if iter >= len(ai):
                print(count)
                sys.exit()
        div = int(ai[iter] / (r + 1))
        mod = ai[iter] % (r + 1)
        if mod == 0:
            count += div - 1
            ai[iter] = 1
        else:
            count += div
            ai[iter] = mod

Submission status: Accepted

Solution code:
N = input()
maximum = 1
ans = int(raw_input()) - 1
for i in xrange(N-1):
    n = int(raw_input())
    if n <= maximum:
        continue
    if n == maximum + 1:
        maximum += 1
        continue
    ans += (n-1)/(maximum+1)
print ans

Submission status: Accepted

Solution code:
# def makelist(n, m):
# 	return [[0 for i in range(m)] for j in range(n)]

N = int(input())
A = [0]*N
for i in range(N):
	A[i] = int(input())

ans = A[0] - 1
A[0] = 1

cnt = 1
# yobi = 1

for i in range(1, N):
	now = A[i]

	if now > cnt:
		if now == cnt + 1: ## 0 ni nattyau
			cnt += 1
		else: ## now >= cnt + 2
			ans += now // (cnt + 1)
			if now % (cnt + 1) == 0:
				ans -= 1

print(ans)

Submission status: Accepted

Solution code:
now = 2
n = int(raw_input())
a = []
for i in xrange(n):
    p = int(raw_input())
    a.append(p)

res = a[0]-1
a.pop(0)

for x in a:
    if x > now:
        if x % now:
            res += x / now
        else:
            res += x / now - 1
    if x == now:
        now += 1
print res

Submission status: Accepted

Solution code:
num=input()
a=[]
for i in range(num):
    p=input()
    a.append(p)
ans=a[0]-1
a.pop(0)
nowprice=2
for custom in a:
    if (custom>nowprice):
        if custom % (nowprice)==0:
            ans += custom / (nowprice )-1
        else:
            ans+=custom/(nowprice)
    if (custom==nowprice):
        nowprice+=1
print ans

Submission status: Accepted

Solution code:
N = int(raw_input())
res = 0
q = 1

for i in range(N):
    m = int(raw_input())
    res += int((m-1)/q)
    if q == 1 or m == q:
        q += 1
print res

Submission status: Accepted

Solution code:
N =int(input())

A = [int(input()) for _ in range(N)]



def solve(target,min_n):
    if A[target] > min_n:
        return (((A[target]-1)//min_n),max(min_n,2))
    else:
        return (0, max(min_n , A[target]+1))

ans =0
min_n=1
for i in range(N):
    res,min_n =solve(i,min_n)
    #print(res)
    ans +=res

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(input()) for _ in range(N)]
ans = A[0] - 1
m = 1
for a in A[1:]:
    if a == m + 1:
        m += 1
    else:       
        ans += (a-1) // (m + 1)
print(ans)

Submission status: Accepted

Solution code:
n = input()
A = [int(raw_input()) for i in xrange(n)]
B = [0]*n

can = 1
ans = 0
for i in xrange(n):
    cnt = (A[i]-1)/can
    ans += cnt
    B[i] = A[i] - cnt*can
    if cnt > 0 and can > 1 and B[i]==can:
        B[i] -= 1
    #print A[i], B[i], (A[i]-1)/can, can
    can = max(can, B[i]+1)
print ans

Submission status: Accepted

Solution code:
N = int(input())
As = [int(input()) for _ in range(N)]

s = As[0]-1
killer = 1
for a in As[1:]:
    if a == killer+1:
        killer = a
    elif a > killer+1:
        s += (a-1)//(killer+1)
print(s)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import math,string,itertools,fractions,heapq,collections,re,array,bisect

def s():
    return raw_input().strip()
def n():
    return int(raw_input())
def d():
    return float(raw_input())

def ls():
    return raw_input().strip().split()
def ln():
    return map(int, raw_input().strip().split())
def ld():
    return map(float, raw_input().strip().split())

def fs():
    return [raw_input().strip() for i in xrange(input())]
def fn():
    return [int(raw_input().strip()) for i in xrange(input())]
def fd():
    return [float(raw_input().strip()) for i in xrange(input())]

def eratosthenes_sieve(n):
    table = [0] * (n + 1)
    prime_list = []
    
    for i in xrange(2, n + 1):
        if table[i] == 0:
            prime_list.append(i)
            for j in xrange(i + i, n + 1, i):
                table[j] = 1
    
    return prime_list

def trial_division_sqrt(n):
    prime_count = collections.Counter()
    
    for i in xrange(2, int(math.sqrt(n)) + 2):
        while n % i == 0:
            n /= i
            prime_count[i] += 1
    if n > 1:
        prime_count[n] += 1
    
    for p, c in prime_count.iteritems():
        prime_count[p] = c % 3
    
    return prime_count

def trial_division_prime(n, prime_list):
    prime_count = collections.Counter()
    
    for i in prime_list:
        if i * i > n:
            break
        while n % i == 0:
            n /= i
            prime_count[i] += 1
    if n > 1:
        prime_count[n] += 1
    
    for p, c in prime_count.iteritems():
        prime_count[p] = c % 3
    
    return prime_count

N = n()

A = []
for i in xrange(N):
    A.append(n())

result = A[0] - 1
th = 2
#print 1
for a in A[1:]:
    if a > th:
        num = (a - 1) / th
        rest = a - th * num
        a = rest
        result += num
        if rest > th:
            th = rest
#        print rest
    elif a == th:
        th = a + 1
#        print a
#    else:
#        print a
#    print 'th', th

#print
print result

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys,copy,math,heapq,itertools as it,fractions,re,bisect,collections as coll

N = int(raw_input())
A = [int(raw_input()) for i in xrange(N)]
ans = A[0] - 1
d = 2
for i in xrange(1, N):
    k = (A[i] - 1)/d
    if A[i] == d:
        d += 1
    ans += k
print ans

Submission status: Runtime Error

Solution code:
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = [ir() for _ in range(N)]
answer = A[0] - 1
cur_limit = 2
for a in A[1:]:
    if a == cur_limit:
        cur_limit += 1
        continue
    answer += (a-cur_limit) // cur_limit)

print(answer)
# 44

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
a = [int(input()) for i in range(n)]
cnt = 1
ans = 0
for i in range(n):
  if a[i] = cnt+1:
    cnt += 1
  else:
    ans += (a[i]-1)//cnt
    if cnt == 1:
      cnt += 1
print(ans)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

n = int(input())
arr = [int(input()) for _ in range(N)]
count = arr[0]-1
m = 1
for a in arr[1:]:
    if a == m:
        m += 1
    if a > m:
        count += (a - 1) // (m+1)
print(count)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# !/usr/bin/env python
# vim: set fileencoding=utf-8 :

"""
#
# Author:   Noname
# URL:      https://github.com/pettan0818
# License:  MIT License
# Created:  2016-10-10
#

# Usage
#
"""

def read_value():
    num_customer = input()

    return [int(input()) for _ in range(num_customer)]


def greed_canceler(customers):
    """

    >>> greed_canceler([3,2,5])
    3
    >>> greed_canceler([3,1,4,1,5,9,2,6,5,3,5,8,9,7,9])
    18
    """
    selled = 0
    must_above = 1
    for i, n in enumerate(customers):
        flag = False
        while must_above < customers[i]:
            flag = True
            selled += 1
            #print("Processing col: {0} of {1}".format(i, customers[i]))
            customers[i] = customers[i] - must_above
            #print("must_above: {0}".format(must_above))
            #print(customers[i])
        if not must_above < customers[i]:
            must_above = customers[i] + 1


    return selled

if __name__ == "__main__":
    import doctest
    doctest.testmod()

    greed_canceler(read_value())

Submission status: Runtime Error

Solution code:
N=int(input())
a=[0]*N
for i in range(N):
    a.[i]=int(input())
minimum=1
count=0
for i in  a:
   if(minimum<i):
       if i%minimum:
           count+= i//minimum
       else :
           count+= (i//minimum-1)
   else:
       minimum=max(minimum,i+1)
print(count)

Submission status: Runtime Error

Solution code:
# def makelist(n, m):
# 	return [[0 for i in range(m)] for j in range(n)]

n = int(input())
A = [0]*N
for i in range(N):
	A[i] = int(input())

ans = A[0] - 1
A[0] = 1

cnt = 1
# yobi = 1

for i in range(1, N):
	now = A[i]

	if now > cnt:
		if now == cnt + 1: ## 0 ni nattyau
			cnt += 1
		else: ## now >= cnt + 2
			ans += now // (cnt + 1)
			if now % (cnt + 1) == 0:
				ans -= 1

print(ans)