Make Them Equal (Codeforces 1633D)
Tags: Greedy, dp

You have an array of integers $$$a$$$ of size $$$n$$$. Initially, all elements of the array are equal to $$$1$$$. You can perform the following operation: choose two integers $$$i$$$ ($$$1 \le i \le n$$$) and $$$x$$$ ($$$x > 0$$$), and then increase the value of $$$a_i$$$ by $$$\left\lfloor\frac{a_i}{x}\right\rfloor$$$ (i.e. make $$$a_i = a_i + \left\lfloor\frac{a_i}{x}\right\rfloor$$$).After performing all operations, you will receive $$$c_i$$$ coins for all such $$$i$$$ that $$$a_i = b_i$$$.Your task is to determine the maximum number of coins that you can receive by performing no more than $$$k$$$ operations.

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases.The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 10^3; 0 \le k \le 10^6$$$) — the size of the array and the maximum number of operations, respectively.The second line contains $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_i \le 10^3$$$).The third line contains $$$n$$$ integers $$$c_1, c_2, \dots, c_n$$$ ($$$1 \le c_i \le 10^6$$$).The sum of $$$n$$$ over all test cases does not exceed $$$10^3$$$.

Output: For each test case, print one integer — the maximum number of coins that you can get by performing no more than $$$k$$$ operations.


Sample Inputs:
4
4 4
1 7 5 2
2 6 5 2
3 0
3 5 2
5 4 7
5 9
5 2 5 6 3
5 9 1 9 7
6 14
11 4 6 2 8 16
43 45 9 41 15 38

Sample Outputs:
9
0
30
167

Solution (Python):
from collections import deque
N = 1000 + 10

def get_cost():
    cost = [-1] * N
    vis = [False] * N
    cost[1] = 0
    vis[1] = True
    queue = deque([1])
    while queue:
        cur = queue.popleft()
        for i in range(1, cur + 1):
            nxt = cur + cur // i
            if nxt >= N:
                continue
            if vis[nxt]:
                continue
            vis[nxt] = True
            cost[nxt] = cost[cur] + 1
            queue.append(nxt)
    return cost

def main():
    cost = get_cost()
    T = int(input())
    while T > 0:
        (n, k) = map(int, input().split())
        b = list(map(int, input().split()))
        c = list(map(int, input().split()))
        w = [cost[b_i] for b_i in b]
        sum_w = sum(w)
        sum_c = sum(c)
        if k >= sum_w:
            print(sum_c)
        else:
            max_w = max(w)
            if k >= max_w * n:
                print(sum_c)
            else:
                dp = [0] * (k + 1)
                for i in range(n):
                    for j in range(k, w[i] - 1, -1):
                        v = dp[j - w[i]] + c[i]
                        if dp[j] < v:
                            dp[j] = v
                print(dp[k])
        T -= 1
if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
N = 1000 + 10

def get_cost():
    cost = [-1] * N
    vis = [False] * N
    cost[1] = 0
    vis[1] = True
    queue = deque([1])
    while queue:
        cur = queue.popleft()
        for i in range(1, cur + 1):
            nxt = cur + cur // i
            if nxt >= N:
                continue
            if vis[nxt]:
                continue
            vis[nxt] = True
            cost[nxt] = cost[cur] + 1
            queue.append(nxt)
    return cost

def main():
    cost = get_cost()
    T = int(input())
    while T > 0:
        (n, k) = map(int, input().split())
        b = list(map(int, input().split()))
        c = list(map(int, input().split()))
        w = [cost[b_i] for b_i in b]
        sum_w = sum(w)
        sum_c = sum(c)
        if k >= sum_w:
            print(sum_c)
        else:
            dp = [0] * (k + 1)
            for i in range(n):
                for j in range(k, w[i] - 1, -1):
                    v = dp[j - w[i]] + c[i]
                    if dp[j] < v:
                        dp[j] = v
            print(dp[k])
        T -= 1
if __name__ == '__main__':
    main()

Solution (Python):
def money(n, k, b, c):
    t = [0] * n
    for a in range(n):
        t[a] = res[b[a]]
    s = 0
    sum = 0
    for d in range(n):
        s += t[d]
        sum += c[d]
    if k >= s:
        return sum
    dp = [0] * (k + 1)
    for i in range(n):
        for j in range(k, t[i] - 1, -1):
            temp = dp[j - t[i]] + c[i]
            if temp > dp[j]:
                dp[j] = temp
    return dp[k]
if __name__ == '__main__':
    res = [float('inf')] * 1001
    res[1] = 0
    res[2] = 1
    for i in range(2, 1000):
        for x in range(1, i + 1):
            if i + i // x <= 1000:
                res[i + i // x] = min(res[i + i // x], res[i] + 1)
    t = int(input())
    for i in range(t):
        (n, k) = list(map(int, input().split()))
        b = list(map(int, input().split()))
        c = list(map(int, input().split()))
        r = money(n, k, b, c)
        print(r)