from os import mkdir
from random import *
from math import sqrt

seed('space')

logger = lambda s : print (s)

def solve2(n, a, b, w, h):
    left, right = 0, max(w, h)
    while right - left > 1:
        mid = (left + right) // 2
        w1, h1 = w // (a + 2 * mid), h // (b + 2 * mid)
        if w1 * h1 >= n:
            left = mid
        else:
            right = mid
    return left

def solve(n, a, b, w, h):
    return max(solve2(n, a, b, w, h), solve2(n, a, b, h, w))

rand = lambda n, p, c: [(randint(1, p), randint(1, c)) for i in range(n)]

validator = lambda n, a, b, w, h: n <= max((w // a) * (h // b), (w // b) * (h // a))

prevalidators = {
        1: lambda n, a, b, w, h: all(1 <= i <= 1000 for i in [n, a, b, w, h]),
        2: lambda n, a, b, w, h: 1 <= n <= 1000 and all(1 <= i <= 10**9 for i in [a, b, w, h]),
        3: lambda n, a, b, w, h: 1 <= n <= 10**9 and all(1 <= i <= 10**18 for i in [a, b, w, h]),
        4: lambda n, a, b, w, h: all(1 <= i <= 10**18 for i in [n, a, b, w, h])
}

class Printer:
    def __init__(self, path, desc):
        self.path = "../" + path
        try:
            mkdir(self.path)
            logger("Creating directory %s"%self.path)
        except:
            pass
        self.desc = desc
        self.tests = 0

    def print(self, n, a, b, w, h, subtask=None, comment=None):
        assert validator(n, a, b, w, h), "Main validator {} {} {} {} {}".format(n, a, b, w, h)
        assert (not subtask) or prevalidators[subtask](n, a, b, w, h), "Subtask validator {} {} {} {} {} {}".format(subtask, n, a, b, w, h)
        self.tests += 1
        sub = ("subtask" + str(subtask)) if subtask else ""
        d = self.path + "/" + sub
        try:
            mkdir(d)
            logger("Creating directory %s"%d)
        except:
            pass
        p = d + "/" + "%02d"%self.tests
        logger("Printing test %s"%p)
        out = open(p, "w")
        print(n, a, b, w, h, file=out)
        if comment:
            comment += ", "
        else:
            comment = "n={}, a={}, b={}, w={}, h={}, ans={}".format(
                n, a, b, w, h, solve(n, a, b, w, h))
        print("{}\t{}".format(p, comment), file=desc)

desc = open("../tests.desc", "w")

prelim = Printer("preliminary", desc)
prelim.print(11, 2, 3, 21, 25)
prelim.print(1, 5, 5, 6, 6)

tests = Printer("tests", desc)
# 26 points, 1 <= * <= 1000
tests.print(1, 1, 1, 1, 1, subtask=1, comment="Smallest test")
tests.print(1, 1, 1, 3, 3, subtask=1, comment="Smallest test with non-zero answer")
tests.print(1, 1, 2, 2, 1, subtask=1, comment="Smallest test with rotation")
tests.print(1, 1, 1, 1000, 1, subtask=1)
tests.print(100, 1, 10, 1, 1000, subtask=1)
tests.print(100, 1, 10, 1000, 1, subtask=1)
tests.print(1000, 1, 1, 1000, 1000, subtask=1, comment="Largest test for this subtask")

for maxwh in [10, 100, 500, 1000, 1000]:
    n = randint(5, 20)
    a = randint(1, 2 * int(sqrt(n)))
    b = randint(1, 2 * int(sqrt(n)))
    w = randint(1, maxwh)
    h = randint(1, maxwh)
    tests.print(n, a, b, w, h, subtask=1)

# 23 points, 1 <= n <= 1000, 1 <= * <= 10**9
tests.print(999, 1, 1, 1, 10**9, subtask=2)
tests.print(999, 7, 2, 10**9, 10**9, subtask=2)
tests.print(1, 1, 1, 10**9, 10**9-3, subtask=2)
tests.print(999, 1, 2, 9, 10**9, subtask=2)
tests.print(2, 1, 2, 10**9, 10**9, subtask=2)
tests.print(3, 1, 1, 10**9, 10**9, subtask=2)

for maxwh in [10000, 10**5, 10**6, 10**7, 10**8, 10**9, 10**9]:
    n = randint(5, 1000)
    a = randint(1, 2 * int(sqrt(n)))
    b = randint(1, 2 * int(sqrt(n)))
    w = randint(1, maxwh)
    h = randint(1, maxwh)
    tests.print(n, a, b, w, h, subtask=2)

# 24=8*3 points, 1 <= n <= 10**9, 1 <= * <= 10**18
tests.print(3, 1, 2, 10**18, 10**18, subtask=3)
tests.print(10**9, 10**9, 10**9, 10**18, 10**18, subtask=3)
tests.print(10**9, 10**18 - 100, 10**7, 10**18, 10**18-1234, subtask=3)
tests.print(10, 10**17, 10**15, 10**18, 10**17, subtask=3)

for maxwh in [10**18] * 4:
    n = randint(5, 10**9)
    a = randint(1, 2 * int(sqrt(n)))
    b = randint(1, 2 * int(sqrt(n)))
    w = randint(1, maxwh)
    h = randint(1, maxwh)
    tests.print(n, a, b, w, h, subtask=3)
    
# 27=9*3 points, 1 <= * <= 10**18
tests.print(10**10, 10**10, 10**15, 10**18, 10**18 // 2, subtask=4)
tests.print(10**18, 1, 10**18, 10**18, 10**18, subtask=4)

for maxwh in [10**18] * 7:
    n = randint(10**9, 10**randint(14, 18))
    a = randint(1, 2 * int(sqrt(n)))
    b = randint(1, 2 * int(sqrt(n)))
    w = randint(1, maxwh)
    h = randint(1, maxwh)
    tests.print(n, a, b, w, h, subtask=4)
