Equalize by Divide (Codeforces 1799B)
Tags: Greedy, brute force

You are given an array $$$a_1, a_2, \ldots, a_n$$$ of positive integers.You can make this operation multiple (possibly zero) times:  Choose two indices $$$i$$$, $$$j$$$ ($$$1 \leq i, j \leq n$$$, $$$i \neq j$$$).  Assign $$$a_i := \lceil \frac{a_i}{a_j} \rceil$$$. Here $$$\lceil x \rceil$$$ denotes $$$x$$$ rounded up to the smallest integer $$$\geq x$$$. Is it possible to make all array elements equal by some sequence of operations (possibly empty)? If yes, print any way to do it in at most $$$30n$$$ operations.It can be proven, that under the problem constraints, if some way exists to make all elements equal, there exists a way with at most $$$30n$$$ operations.

Input: The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases. Descriptions of test cases follow.The first line of each test case description contains a single integer $$$n$$$ ($$$1 \leq n \leq 100$$$).The second line of each test case description contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$).It is guaranteed, that the sum of $$$n$$$ for all test cases does not exceed $$$1000$$$.

Output: For each test case print a single integer $$$q$$$ ($$$-1 \leq q \leq 30n$$$). If $$$q=-1$$$, there is no solution, otherwise $$$q$$$ is equal to the number of operations.If $$$q \geq 0$$$, on the next $$$q$$$ lines print two integers $$$i$$$, $$$j$$$ ($$$1 \leq i, j \leq n$$$, $$$i \neq j$$$) — descriptions of operations.If there are multiple solutions, you can print any.

Note: In the first and second, fourth test cases all numbers are equal, so it is possible to do nothing.In the third test case, it is impossible to make all numbers equal.In the fifth test case: $$$[\color{red}{4}, 3, \color{blue}{2}] \to [\color{blue}{2}, \color{red}{3}, 2] \to [2, 2, 2]$$$.In the sixth test case: $$$[\color{blue}{3}, 3, \color{red}{4}, 4] \to [3, \color{blue}{3}, 2, \color{red}{4}] \to [\color{red}{3}, 3, \color{blue}{2}, 2] \to [2, \color{red}{3}, 2, \color{blue}{2}] \to [2, 2, 2, 2]$$$.Here the red numbers are $$$i$$$ indices (that will be assigned), blue numbers are $$$j$$$ indices.

Sample Inputs:
10
1
100
3
1 1 1
2
2 1
2
5 5
3
4 3 2
4
3 3 4 4
2
2 100
5
5 3 6 7 8
6
3 3 80 3 8 3
4
19 40 19 55

Sample Outputs:
0
0
-1
0
2
1 3
2 1
4
3 1
4 2
1 3
2 4
6
2 1
2 1
2 1
2 1
2 1
2 1
8
5 2
4 2
3 2
1 3
1 3
2 1
4 1
5 1
4
5 1
3 1
3 1
3 1
9
4 2
2 1
1 2
1 2
3 2
3 2
1 4
2 4
3 4

Solution (Python):
import sys
input = sys.stdin.readline
print = sys.stdout.write
import math

def main():
    t = int(input().strip())
    for _ in range(t):
        n = int(input().strip())
        a = list(map(int, input().split()))
        h = {}
        flag = True
        for i in range(n):
            if a[i] == 1:
                flag = False
            h[a[i]] = h.get(a[i], i)
        if not flag and len(h) != 1:
            print('-1\n')
            continue
        if len(h) == 1:
            print('0\n')
            continue
        mn = min(a)
        min_idx = h[mn]
        mx = max(a)
        res = []
        while mn != mx:
            for i in range(n):
                if a[i] == mn:
                    continue
                else:
                    while math.ceil(a[i] / mn) > 1:
                        a[i] = int(math.ceil(a[i] / mn))
                        res.append([i + 1, min_idx + 1])
                    h[a[i]] = h.get(a[i], i)
            b = sorted(a)
            mn = b[0]
            min_idx = h[mn]
            mx = b[n - 1]
        print(f'{len(res)}\n')
        for i in res:
            print(f'{i[0]} {i[1]}\n')
if __name__ == '__main__':
    main()

Solution (Python):
import math
count = 0
cosmos3 = 0

def cosmos2(cosmos, n):
    global cosmos3
    global count
    cosmos.sort()
    m = 0
    for i in range(1, n):
        if cosmos[i][0] != cosmos[i - 1][0]:
            if i == n - 1 and cosmos[i - 1][0] == 1:
                return False
            break
        m = i
    if m == n - 1:
        return True
    for i in range(n - 2, -1, -1):
        if cosmos[n - 1][0] != cosmos[i][0]:
            cosmos[n - 1][0] = math.ceil(cosmos[n - 1][0] / cosmos[i][0])
            cosmos3 += [[cosmos[n - 1][1], cosmos[i][1]]]
            count += 1
            break
    return cosmos2(cosmos, n)
t = int(input())
for i in range(t):
    count = 0
    cosmos3 = []
    n = int(input())
    a = [0]
    a += [int(x) for x in input().split()]
    if 1 not in a:
        cosmos4 = [[a[i], i] for i in range(1, n + 1)]
        if cosmos2(cosmos4, n):
            print(count)
            for i in range(0, len(cosmos3)):
                print(cosmos3[i][0], cosmos3[i][1])
        else:
            print(-1)
    elif a == [0] + [1] * n:
        print(0)
    else:
        print(-1)

Solution (Python):
import sys, math

def inp():
    return int(input())

def inlt():
    return list(map(int, input().split()))

def insr():
    s = input()
    return list(s[:len(s) - 1])

def invr():
    return map(int, input().split())

def outp(s):
    sys.stdout.write(s + '\n')

def loutp(l):
    sys.stdout.write(' '.join(map(str, l)) + '\n')

def solve():
    n = inp()
    for _ in range(n):
        inp()
        ns = inlt()
        steps = []
        while True:
            nss = set(ns)
            mx = max(nss)
            if len(nss) > 1:
                nss.remove(mx)
                smx = max(nss)
                nn = math.ceil(mx / smx)
                imx = ns.index(mx)
                ismx = ns.index(smx)
                if nn == ns[imx]:
                    outp('-1')
                    break
                else:
                    steps.append((imx + 1, ismx + 1))
                    ns[imx] = nn
            else:
                outp(str(len(steps)))
                for step in steps:
                    loutp(step)
                break
if __debug__:
    input = sys.stdin.readline
    solve()