import os
import random
import sys
import math

MAX_K = 10
MAX_T = 10**6
MAX_F = 10**6
MAX_Q = 10**5


CASE = 1
DEST = os.path.join(os.getcwd(), '../data/secret')

def next_file(short_desc=None, long_desc=None):
    global CASE
    basename = os.path.join(DEST, '%02d' % CASE)
    CASE += 1
    if short_desc is not None:
        basename += '-' + short_desc
    if long_desc is not None:
        with open(basename+'.desc', 'w') as desc_out:
            desc_out.write(long_desc)
    return open(basename+'.in', 'w')

def save_case(faucets, queries, short_desc=None, long_desc=None, shuffle_adj_list=True):
    assert 1 <= len(faucets) <= MAX_K
    assert 1 <= len(queries) <= MAX_Q
    sys.stderr.write('save case k=%d r=%d short_desc=%s\n' % (len(faucets), len(queries), short_desc))
    f = next_file(short_desc, long_desc)
    random.shuffle(faucets)
    random.shuffle(queries)
    f.write('%d\n' % len(faucets))
    for (t, a, b) in faucets: f.write('%d %d %d\n' % (t, a, b))
    f.write('%d\n' % len(queries))
    for (tau, phi) in queries: f.write('%d %d\n' % (tau, phi))
    f.close()


def random_faucet(min_t=0, max_t=MAX_T, min_a=0, max_a=MAX_F, min_b=0, max_b=MAX_F):
    t = random.randint(min_t, max_t)
    a = random.randint(min_a, max_a)
    b = random.randint(min_b, max_b)
    if b < a: (a, b) = (b, a)
    return (t, a, b)
    
def random_faucets(k, min_t=0, max_t=MAX_T, min_a=0, max_a=MAX_F, min_b=0, max_b=MAX_F):
    return [random_faucet(min_t, max_t, min_a, max_a, min_b, max_b) for _ in range(k)]


def random_query(min_t=0, max_t=MAX_T, min_f=1, max_f=MAX_F):
    return (random.randint(min_t, max_t), random.randint(min_f, max_f))

def random_queries(q, min_t=0, max_t=MAX_T, min_f=1, max_f=MAX_F):
    return [random_query(min_t, max_t, min_f, max_f) for _ in range(q)]

def gen_random_case(k, q, short_desc='random'):
    faucets = random_faucets(k)
    queries = random_queries(q)
    save_case(faucets, queries, short_desc=short_desc)

    
def make_flow(flow, faucets):
    baseflow = 0
    basetemp = 0
    for (t, a, b) in faucets:
        baseflow += a
        basetemp += a*t
    if baseflow > flow: return -1
    addtemp = 0
    addflow = flow - baseflow
    for (t, a, b) in faucets:
        addtemp += min(addflow, b-a)*t
        addflow -= min(addflow, b-a)
    if addflow > 0: return 1<<60
    return (basetemp + addtemp)/flow


def get_max_temp(faucets, flow): # assumes faucets sorted by temp
    return int(math.floor(make_flow(flow, list(reversed(faucets)))))

def get_min_temp(faucets, flow): # assumes faucets sorted by temp
    return int(math.ceil(make_flow(flow, faucets)))

def perturbed_queries(t, f):
    return [(tt, ff) for tt in [t-1, t, t+1] for ff in [f-1, f, f+1]]

def factor_queries(t, f):
    res = []
    tf = t*f
    r = 2
    while r*r <= tf and r <= MAX_F:
        if tf % r == 0:
            if tf // r <= MAX_T:
                res.append((tf // r , r))
            if r*r < tf and tf // r <= MAX_F:
                res.append((r, tf // r))
        r += 1
    return res

def integer_faucets(k, descending_temp=False, temp_off=0):
    sys.stderr.write('gen_integer %d...' % k)
    queries = []
    a = [random.randint(1, MAX_F//(10*k)) for x in range(k)]
    cur_flow = sum(a)

    while True:
        t = list(sorted([random.randint(0, MAX_T) for _ in range(k)], reverse=descending_temp))
        cur_temp = sum(t[i]*a[i] for i in range(k)) + temp_off
        if cur_temp % cur_flow == 0:
            break
    queries.extend(perturbed_queries(cur_temp//cur_flow, cur_flow))
    queries.extend(factor_queries(cur_temp//cur_flow, cur_flow))
    sys.stderr.write('0..')
    x = []
    while len(x) != k:
        ti = t[len(x)]
        while True:
            z = random.randint(1, 3*MAX_F//(2*k))
            if (cur_temp + z*ti) % (cur_flow + z) == 0:
                break
        x.append(z)
        cur_temp += z*ti
        cur_flow += z
        assert cur_temp % cur_flow == 0
        queries.extend(perturbed_queries(cur_temp/cur_flow, cur_flow))
        queries.extend(factor_queries(cur_temp//cur_flow, cur_flow))
        sys.stderr.write('%d..' % len(x))
    sys.stderr.write('\n')
    assert cur_flow <= MAX_F

    b = [a[i]+x[i] for i in range(k)]
    faucets = zip(t, a, b)
    random.shuffle(faucets)
    random.shuffle(queries)
    save_case(faucets, queries, 'integer_points')
    

def gen_random_faucets_near_boundary(k, q):
    while True:
        faucets = random_faucets(k, max_a=MAX_F/k, max_b=min(MAX_F, 2*MAX_F/k))
        faucets.sort()
        minflow = sum(a for (_, a, _) in faucets)
        if minflow <= MAX_F/10: break
    maxflow = min(sum(b for (_, _, b) in faucets), MAX_F)
    queries = []
    for _ in range(q):
        f = random.randint(minflow, maxflow)
        if random.randint(0, 1):
            t = get_min_temp(faucets, f)
            if random.randint(0, 1): t -= 1
        else:
            t = get_max_temp(faucets, f)
            if random.randint(0, 1): t += 1
        queries.append((t, f))
    save_case(faucets, queries, short_desc='near_boundary')
    
def main():
    random.seed(13)

    gen_random_faucets_near_boundary(1, 20)
    
    for k in range(2, MAX_K+1):
        gen_random_case(k, 10)

    for k in range(2, MAX_K+1):
        gen_random_faucets_near_boundary(k, MAX_Q)

    random.seed(12332)
    integer_faucets(2, False)
    integer_faucets(2, True)
    integer_faucets(3, False)
    integer_faucets(3, True)
    random.seed(144)
    integer_faucets(MAX_K, False)
    random.seed(1750)
    integer_faucets(MAX_K, True)

    random.seed(47)
    integer_faucets(2, False, -1)
    integer_faucets(2, False, +1)

    random.seed(49)
    integer_faucets(3, False, -1)
    integer_faucets(3, False, +1)
    integer_faucets(7, False, -1)

    random.seed(51)
    integer_faucets(7, False, +1)

    random.seed(59)
    integer_faucets(10, False, -1)

    random.seed(80)
    integer_faucets(10, False, +1)
    
if __name__=='__main__':
    main()