Yet Another Promotion (Codeforces 1793A)
Tags: Greedy, math

The famous store "Second Food" sells groceries only two days a month. And the prices in each of days differ. You wanted to buy $$$n$$$ kilos of potatoes for a month. You know that on the first day of the month $$$1$$$ kilo of potatoes costs $$$a$$$ coins, and on the second day $$$b$$$ coins. In "Second Food" you can buy any integer kilograms of potatoes.Fortunately, "Second Food" has announced a promotion for potatoes, which is valid only on the first day of the month — for each $$$m$$$ kilos of potatoes you buy, you get $$$1$$$ kilo as a gift! In other words, you can get $$$m + 1$$$ kilograms by paying for $$$m$$$ kilograms.Find the minimum number of coins that you have to spend to buy at least $$$n$$$ kilos of potatoes.

Input: Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10\,000$$$). Description of the test cases follows.The first line of each test case contains two integers $$$a$$$ and $$$b$$$ $$$(1 \leq a, b \leq 10^9)$$$ — the prices of $$$1$$$ kilo of potatoes on the first and second days, respectively.The second line contains two integers $$$n$$$ and $$$m$$$ $$$(1 \leq n, m \leq 10^9)$$$ — the required amount of potatoes to buy and the amount of potatoes to use the promotion.

Output: For each test case print one integer — the minimum number of coins that you have to pay to buy at least $$$n$$$ kilos of potatoes.

Note: In the first test case, on the first day you buy $$$1$$$ kilo and get $$$1$$$ more for a promotion. On the second day, you can buy $$$1$$$ kilo of potatoes. Thus, you will spend $$$5+4=9$$$ coins in total.In the second test case, on the first day you buy $$$2$$$ kilo and get another $$$1$$$ more for a promotion. This way you will spend $$$2 \cdot 5 = 10$$$ coins.

Sample Inputs:
5
5 4
3 1
5 4
3 2
3 4
3 5
20 15
10 2
1000000000 900000000
1000000000 8

Sample Outputs:
9
10
9
135
888888888900000000

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

def solve():
    (a, b) = map(int, input().split())
    (n, m) = map(int, input().split())
    if m >= n:
        print(min(n * a, n * b))
    elif a * m >= b * (m + 1):
        print(n * b)
    else:
        k = n // (m + 1)
        r = n % (m + 1)
        print(k * m * a + r * min(a, b))
t = int(input())
for _ in range(t):
    solve()

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
T = int(input())
res = []
for _ in range(T):
    (day1, day2) = map(int, input().split())
    (need, firstadd) = map(int, input().split())
    if need < firstadd:
        if day1 < day2:
            res.append(day1 * need)
        else:
            res.append(day2 * need)
    elif firstadd * day1 < (firstadd + 1) * day2:
        fv = need // (firstadd + 1) * (firstadd * day1)
        f = need // (firstadd + 1) * (firstadd + 1)
        if day1 < day2:
            res.append(fv + (need - f) * day1)
        else:
            res.append(fv + day2 * (need - f))
    else:
        res.append(day2 * need)
print('\n'.join(map(str, res)))

Solution (Python):
import math

def aloooo(a, b, n, m):
    t = n * b
    f = a * (n // (m + 1)) * m + (n - n // (m + 1) * (m + 1)) * b
    g = n * a
    x = a * (n // (m + 1)) * m + (n - n // (m + 1) * (m + 1)) * a
    return min(t, f, g, x)
t = int(input())
result = []
for j in range(t):
    s = input()
    alist = [int(d) for d in s.split()]
    m = input()
    blist = [int(d) for d in m.split()]
    result.append(aloooo(alist[0], alist[1], blist[0], blist[1]))
for res in result:
    print(res)