Tea with Tangerines (Codeforces 1735B)
Tags: Greedy, math

There are $$$n$$$ pieces of tangerine peel, the $$$i$$$-th of them has size $$$a_i$$$. In one step it is possible to divide one piece of size $$$x$$$ into two pieces of positive integer sizes $$$y$$$ and $$$z$$$ so that $$$y + z = x$$$.You want that for each pair of pieces, their sizes differ strictly less than twice. In other words, there should not be two pieces of size $$$x$$$ and $$$y$$$, such that $$$2x \le y$$$. What is the minimum possible number of steps needed to satisfy the condition?

Input: The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases. The description of test cases follows.The first line of each test case contains the integer $$$n$$$ ($$$1 \le n \le 100$$$).Then one line follows, containing $$$n$$$ integers $$$a_1 \le a_2 \le \ldots \le a_n$$$ ($$$1 \le a_i \le 10^7$$$).

Output: For each test case, output a single line containing the minimum number of steps.

Note: In the first test case, we initially have a piece of size $$$1$$$, so all final pieces must have size $$$1$$$. The total number of steps is: $$$0 + 1 + 2 + 3 + 4 = 10$$$.In the second test case, we have just one piece, so we don't need to do anything, and the answer is $$$0$$$ steps.In the third test case, one of the possible cut options is: $$$600,\ 900,\ (600 | 700),\ (1000 | 1000),\ (1000 | 1000 | 550)$$$. You can see this option in the picture below. The maximum piece has size $$$1000$$$, and it is less than $$$2$$$ times bigger than the minimum piece of size $$$550$$$. $$$4$$$ steps are done. We can show that it is the minimum possible number of steps.  

Sample Inputs:
3
5
1 2 3 4 5
1
1033
5
600 900 1300 2000 2550

Sample Outputs:
10
0
4

Solution (Python):
for _ in range(int(input())):
    ans = int()
    n = int(input())
    lis = list(map(int, input().split()))
    sm = min(lis) * 2 - 1
    for i in lis:
        if i > sm:
            if not i % sm:
                ans -= 1
                ans += i // sm
            else:
                ans += i // sm
    print(ans)

Solution (Python):
for s in [*open(0)][2::2]:
    a = (*map(int, s.split()),)
    print(-sum((-x // (2 * min(a) - 1) + 1 for x in a)))

Solution (Python):
from math import ceil
t = int(input())
for q in range(t):
    n = int(input())
    a = list(map(int, input().split(' ')))
    c = min(a)
    count = 0
    for i in range(len(a)):
        if a[i] > 2 * c - 1:
            count += int(ceil(a[i] / (2 * c - 1))) - 1
    print(count)