Gift Set (Codeforces 1538G)
Tags: Math, ternary search

Polycarp has $$$x$$$ of red and $$$y$$$ of blue candies. Using them, he wants to make gift sets. Each gift set contains either $$$a$$$ red candies and $$$b$$$ blue candies, or $$$a$$$ blue candies and $$$b$$$ red candies. Any candy can belong to at most one gift set.Help Polycarp to find the largest number of gift sets he can create.For example, if $$$x = 10$$$, $$$y = 12$$$, $$$a = 5$$$, and $$$b = 2$$$, then Polycarp can make three gift sets:   In the first set there will be $$$5$$$ red candies and $$$2$$$ blue candies;  In the second set there will be $$$5$$$ blue candies and $$$2$$$ red candies;  In the third set will be $$$5$$$ blue candies and $$$2$$$ red candies. Note that in this example there is one red candy that Polycarp does not use in any gift set.

Input: The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$). Then $$$t$$$ test cases follow.Each test case consists of a single string containing four integers $$$x$$$, $$$y$$$, $$$a$$$, and $$$b$$$ ($$$1 \le x, y, a, b \le 10^9$$$).

Output: For each test case, output one number — the maximum number of gift sets that Polycarp can make.


Sample Inputs:
9
10 12 2 5
1 1 2 2
52 311 13 27
1000000000 1000000000 1 1
1000000000 1 1 1000000000
1 1000000000 1000000000 1
1 2 1 1
7 8 1 2
4 1 2 3

Sample Outputs:
3
0
4
1000000000
1
1
1
5
0

Solution (Python):
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
T = int(input())
t = 1
while t <= T:
    (x, y, a, b) = map(int, input().split())
    ans = 0
    if x < y:
        (y, x) = (x, y)
    if a < b:
        (b, a) = (a, b)
    if a == b:
        print(y // a)
        t += 1
        continue
    change = (x - y) // (a - b)
    if y // b < change:
        print(y // b)
        t += 1
        continue
    ans = change
    x -= change * a
    y -= change * b
    coup = y // (a + b)
    ans += coup * 2
    x -= coup * (a + b)
    y -= coup * (a + b)
    if x >= a and y >= b:
        ans += 1
    print(ans)
    t += 1

Solution (Python):
from sys import stdin, stdout
import collections, heapq, bisect, math
input = stdin.readline

def rint():
    return int(input())

def rstr():
    return input().strip()

def rlstr():
    return list(input().strip().split())

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

def main():
    (x, y, a, b) = rlint()
    res = 0
    if x < y:
        (x, y) = (y, x)
    if a < b:
        (a, b) = (b, a)
    if a == b:
        print(y // b)
        return
    z = (x - y) // (a - b)
    if y // b < z:
        print(y // b)
        return
    res += z
    x = x - z * a
    y = y - z * b
    z = y // (a + b)
    res += z * 2
    x = x - z * (a + b)
    y = y - z * (a + b)
    if x >= a and y >= b:
        res += 1
    print(res)
if __name__ == '__main__':
    for _ in range(rint()):
        main()

Solution (Python):
S = sorted
for s in [*open(0)][1:]:
    (x, y, a, b) = map(int, s.split())
    (x, y) = S((x, y))
    (a, b) = S((a, b))
    try:
        s = a + b
        A = k = min((y - x) // (b - a), x // a)
        x -= a * k
        y -= b * k
        k = min(x, y) // s
        A += 2 * k
        (y, x) = S((x - k * s, y - k * s))
        print(A + 1 - (x < b or y < a))
    except:
        print(x // a)