Milena and Admirer (Codeforces 1898B)
Tags: Greedy, math

Milena has received an array of integers $$$a_1, a_2, \ldots, a_n$$$ of length $$$n$$$ from a secret admirer. She thinks that making it non-decreasing should help her identify the secret admirer.She can use the following operation to make this array non-decreasing:  Select an element $$$a_i$$$ of array $$$a$$$ and an integer $$$x$$$ such that $$$1 \le x < a_i$$$. Then, replace $$$a_i$$$ by two elements $$$x$$$ and $$$a_i - x$$$ in array $$$a$$$. New elements ($$$x$$$ and $$$a_i - x$$$) are placed in the array $$$a$$$ in this order instead of $$$a_i$$$.More formally, let $$$a_1, a_2, \ldots, a_i, \ldots, a_k$$$ be an array $$$a$$$ before the operation. After the operation, it becomes equal to $$$a_1, a_2, \ldots, a_{i-1}, x, a_i - x, a_{i+1}, \ldots, a_k$$$. Note that the length of $$$a$$$ increases by $$$1$$$ on each operation. Milena can perform this operation multiple times (possibly zero). She wants you to determine the minimum number of times she should perform this operation to make array $$$a$$$ non-decreasing.An array $$$x_1, x_2, \ldots, x_k$$$ of length $$$k$$$ is called non-decreasing if $$$x_i \le x_{i+1}$$$ for all $$$1 \le i < k$$$.

Input: Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \leq t \leq 10\,000$$$). The description of test cases follows.The first line of each test case contains a single integer $$$n$$$ ($$$1\leq n\leq 2\cdot 10^5$$$) — the length of the array $$$a$$$.The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1\leq a_i\leq 10^9$$$) – the array $$$a$$$.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.

Output: For each test case, output one integer — the minimum number of operations required to make the array non-decreasing.It can be shown that it is always possible to make the array $$$a$$$ non-decreasing in the finite number of operations.

Note: In the first test case, Milena can replace the second element of array $$$a$$$ by integers $$$1$$$ and $$$2$$$, so the array would become $$$[\, 1, \, \underline{1}, \, \underline{2}, \, 2 \,]$$$. Only $$$1$$$ operation is required.In the second test case, the array $$$a$$$ is already non-decreasing, so the answer is $$$0$$$.In the third test case, Milena can make array $$$a$$$ non-decreasing in $$$3$$$ operations as follows.   Select $$$i=1$$$ and $$$x=2$$$ and replace $$$a_1$$$ by $$$2$$$ and $$$1$$$. The array $$$a$$$ becomes equal to $$$[\, \underline{2}, \, \underline{1}, \, 2, \, 1 \, ]$$$.  Select $$$i=3$$$ and $$$x=1$$$ and replace $$$a_3$$$ by $$$1$$$ and $$$1$$$. The array $$$a$$$ becomes equal to $$$[\, 2, \, 1, \, \underline{1}, \, \underline{1}, \, 1 \,]$$$.  Select $$$i=1$$$ and $$$x=1$$$ and replace $$$a_1$$$ by $$$2$$$ and $$$1$$$. The array $$$a$$$ becomes equal to $$$[\, \underline{1}, \, \underline{1}, \, 1, \, 1, \, 1, \, 1 \,]$$$. It can be shown that it is impossible to make it non-decreasing in $$$2$$$ or less operations, so the answer is $$$3$$$.

Sample Inputs:
4
3
1 3 2
4
1 2 3 4
3
3 2 1
7
1 4 4 3 5 7 6

Sample Outputs:
1
0
3
9

Solution (Python):
import sys
input = sys.stdin.readline

def solve():
    n = int(input())
    A = list(map(int, input().split()))
    ans = 0
    curr = A[-1]
    for i in range(n - 2, -1, -1):
        if A[i] <= curr:
            curr = A[i]
        else:
            (q, r) = divmod(A[i], curr)
            if r == 0:
                ans += q - 1
            else:
                ans += q
                curr = A[i] // (q + 1)
    return ans
T = int(input())
out = [solve() for _ in range(T)]
print('\n'.join(map(str, out)))

Solution (Python):
import math

def helper(n, ar):
    M = ar[-1]
    s = 0
    for i in range(n - 2, -1, -1):
        k = (ar[i] + M - 1) // M
        s += k - 1
        M = ar[i] // k
    return s
t = int(input())
for x in range(t):
    n = int(input())
    ar = list(map(int, input().split()))
    print(helper(n, ar))

Solution (Python):
def solve():
    global ans
    ans = 0
    n = int(input())
    a = list(map(int, input().split()))
    last = a[n - 1]
    for i in range(n - 2, -1, -1):
        parts = (a[i] + last - 1) // last
        ans += parts - 1
        last = a[i] // parts
    print(ans)
t = int(input())
for _ in range(t):
    solve()