#!/usr/bin/env python3.12
from collections import deque
from random import randint, seed, random, choices, shuffle
from math import ceil
from copy import deepcopy
seed("RMC2025")


def sample_case(ind, b, data, plans):
    n = len(data)
    m = len(plans[0])

    sol = solve(b, data, deepcopy(plans))
    with open(f"../data/sample/{ind}.in", 'w') as f:
        print(f"{n} {m} {b}", file=f)
        for d in data:
            print(f"{d[0]} {d[1]} {d[2]}", file=f)
        for plans_ in plans:
            print(" ".join([str(c) for c, _ in plans_]), file=f)
        for plans_ in plans:
            print(" ".join([str(d) for _, d in plans_]), file=f)

    with open(f"../data/sample/{ind}.ans", 'w') as f:
        print(f"{sol}", file=f)


def secret_case(ind, b, data, plans):
    n = len(data)
    m = len(plans[0])

    sol = solve(b, data, deepcopy(plans))
    with open(f"../data/secret/{ind}.in", 'w') as f:
        print(f"{n} {m} {b}", file=f)
        for d in data:
            print(f"{d[0]} {d[1]} {d[2]}", file=f)
        for plans_ in plans:
            print(" ".join([str(c) for c, _ in plans_]), file=f)
        for plans_ in plans:
            print(" ".join([str(d) for _, d in plans_]), file=f)

    with open(f"../data/secret/{ind}.ans", 'w') as f:
        print(f"{sol}", file=f)


def random_case_no_dup(ind, n_max, b_max, p_max, r_max, s_max, m_max):
    n = randint(n_max//5+1, n_max)
    m = randint(m_max//2+1, m_max)
    b = randint(b_max//2+1, b_max)

    data = [(randint(1, p_max), randint(1, r_max), randint(1, s_max))
            for _ in range(n)]

    ds: list[list[int]] = []
    for i in range(n):
        d = set()
        while len(d) < m:
            d.add(randint(1, 2*b))
        d = list(d)
        d.sort()
        ds.append(d)

    cs = []
    for i in range(n):
        p = data[i][0]
        cs.append([min(ceil(random()**3*p*d), 10000) for d in ds[i]])

    plans = [list(zip(c_, d_)) for c_, d_ in zip(cs, ds)]
    sol = solve(b, data, deepcopy(plans))

    with open(f"../data/secret/{ind}.in", 'w') as f:
        print(f"{n} {m} {b}", file=f)
        for d in data:
            print(f"{d[0]} {d[1]} {d[2]}", file=f)
        for plans_ in plans:
            print(" ".join([str(c) for c, _ in plans_]), file=f)
        for plans_ in plans:
            print(" ".join([str(d) for _, d in plans_]), file=f)

    with open(f"../data/secret/{ind}.ans", 'w') as f:
        print(f"{sol}", file=f)

def random_case_with_dup_unsorted(ind, n_max, b_max, p_max, r_max, s_max, m_max):
    n = randint(n_max//5+1, n_max)
    m = randint(m_max//2+1, m_max)
    b = randint(b_max//2+1, b_max)

    data = [(randint(1, p_max), randint(1, r_max), randint(1, s_max))
            for _ in range(n)]

    ds: list[list[int]] = []
    for i in range(n):
        d = list()
        while len(d) < m:
            d.append(randint(1, 2*b))
        ds.append(d)

    cs = []
    for i in range(n):
        p = data[i][0]
        cs.append([min(ceil(random()**3*p*d), 10000) for d in ds[i]])

    plans = [list(zip(c_, d_)) for c_, d_ in zip(cs, ds)]
    sol = solve(b, data, deepcopy(plans))

    with open(f"../data/secret/{ind}.in", 'w') as f:
        print(f"{n} {m} {b}", file=f)
        for d in data:
            print(f"{d[0]} {d[1]} {d[2]}", file=f)
        for plans_ in plans:
            print(" ".join([str(c) for c, _ in plans_]), file=f)
        for plans_ in plans:
            print(" ".join([str(d) for _, d in plans_]), file=f)

    with open(f"../data/secret/{ind}.ans", 'w') as f:
        print(f"{sol}", file=f)



def increasing_price(ind):
    n = 1000
    m = 10
    b = 20

    data = [(x % 100+1, randint(1, 100), randint(1, 100)) for x in range(n)]
    c = [[x*y*137//500+1 for x in range(m)] for y in range(n)]
    d = [[x+1 for x in range(m)] for _ in range(n)]

    plans = [list(zip(c_, d_)) for c_, d_ in zip(c, d)]
    sol = solve(b, data, deepcopy(plans))

    with open(f"../data/secret/{ind}.in", 'w') as f:
        print(f"{n} {m} {b}", file=f)
        for d in data:
            print(f"{d[0]} {d[1]} {d[2]}", file=f)
        for plans_ in plans:
            print(" ".join([str(c) for c, _ in plans_]), file=f)
        for plans_ in plans:
            print(" ".join([str(d) for _, d in plans_]), file=f)

    with open(f"../data/secret/{ind}.ans", 'w') as f:
        print(f"{sol}", file=f)


def decreasing_price(ind):
    n = 1000
    m = 10
    b = 20

    data = [((100-x) % 100+1, randint(1, 100), randint(1, 100))
            for x in range(n)]
    c = [[x*7100//(y+20) +1 for x in range(m)] for y in range(n)]
    d = [[x+1 for x in range(m)] for y in range(n)]

    plans = [list(zip(c_, d_)) for c_, d_ in zip(c, d)]
    sol = solve(b, data, deepcopy(plans))

    with open(f"../data/secret/{ind}.in", 'w') as f:
        print(f"{n} {m} {b}", file=f)
        for d in data:
            print(f"{d[0]} {d[1]} {d[2]}", file=f)
        for plans_ in plans:
            print(" ".join([str(c) for c, _ in plans_]), file=f)
        for plans_ in plans:
            print(" ".join([str(d) for _, d in plans_]), file=f)

    with open(f"../data/secret/{ind}.ans", 'w') as f:
        print(f"{sol}", file=f)


def max_sell(ind):
    n = 1000
    m = 10
    b = 20

    data = [(100, 1, 100) for _ in range(n)]
    c = [[10000 for _ in range(m)] for _ in range(n)]
    d = [[1 for _ in range(m)] for _ in range(n)]

    plans = [list(zip(c_, d_)) for c_, d_ in zip(c, d)]
    sol = solve(b, data, deepcopy(plans))

    with open(f"../data/secret/{ind}.in", 'w') as f:
        print(f"{n} {m} {b}", file=f)
        for d in data:
            print(f"{d[0]} {d[1]} {d[2]}", file=f)
        for plans_ in plans:
            print(" ".join([str(c) for c, _ in plans_]), file=f)
        for plans_ in plans:
            print(" ".join([str(d) for _, d in plans_]), file=f)

    with open(f"../data/secret/{ind}.ans", 'w') as f:
        print(f"{sol}", file=f)


def max_solar(ind):
    n = 1000
    m = 1
    b = 1

    data = [(100, 1, 100) for _ in range(n)]
    c = [[1 for _ in range(m)] for _ in range(n)]
    d = [[100 for _ in range(m)] for _ in range(n)]

    plans = [list(zip(c_, d_)) for c_, d_ in zip(c, d)]
    sol = solve(b, data, deepcopy(plans))

    with open(f"../data/secret/{ind}.in", 'w') as f:
        print(f"{n} {m} {b}", file=f)
        for d in data:
            print(f"{d[0]} {d[1]} {d[2]}", file=f)
        for plans_ in plans:
            print(" ".join([str(c) for c, _ in plans_]), file=f)
        for plans_ in plans:
            print(" ".join([str(d) for _, d in plans_]), file=f)

    with open(f"../data/secret/{ind}.ans", 'w') as f:
        print(f"{sol}", file=f)


def max_buy(ind):
    n = 1000
    m = 1
    b = 1

    data = [(100, 100, 1) for _ in range(n)]
    c = [[1 for _ in range(m)] for _ in range(n)]
    d = [[100 for _ in range(m)] for _ in range(n)]

    plans = [list(zip(c_, d_)) for c_, d_ in zip(c, d)]
    sol = solve(b, data, deepcopy(plans))

    with open(f"../data/secret/{ind}.in", 'w') as f:
        print(f"{n} {m} {b}", file=f)
        for d in data:
            print(f"{d[0]} {d[1]} {d[2]}", file=f)
        for plans_ in plans:
            print(" ".join([str(c) for c, _ in plans_]), file=f)
        for plans_ in plans:
            print(" ".join([str(d) for _, d in plans_]), file=f)

    with open(f"../data/secret/{ind}.ans", 'w') as f:
        print(f"{sol}", file=f)


def multiple_plans_same_price(ind):
    n = 1000
    m = 10
    b = 20

    data = [(100, 100, 50) if x % 2 == 0 else (1, 1, 50) for x in range(n)]
    c = [[1000 for x in range(m)] for _ in range(n)]
    d = [[x for x in range(m)] for _ in range(n)]

    plans = [list(zip(c_, d_)) for c_, d_ in zip(c, d)]
    sol = solve(b, data, deepcopy(plans))

    with open(f"../data/secret/{ind}.in", 'w') as f:
        print(f"{n} {m} {b}", file=f)
        for d in data:
            print(f"{d[0]} {d[1]} {d[2]}", file=f)
        for plans_ in plans:
            print(" ".join([str(c) for c, _ in plans_]), file=f)
        for plans_ in plans:
            print(" ".join([str(d) for _, d in plans_]), file=f)


    with open(f"../data/secret/{ind}.ans", 'w') as f:
        print(f"{sol}", file=f)

def multiple_plans_same_val(ind):
    n = 1000
    m = 10
    b = 20

    data = [(100, 100, 50) if x % 2 == 0 else (1, 1, 50) for x in range(n)]
    c = [[300 for x in range(m)] for _ in range(n)]
    d = [[10 for x in range(m)] for _ in range(n)]

    plans = [list(zip(c_, d_)) for c_, d_ in zip(c, d)]
    sol = solve(b, data, deepcopy(plans))

    with open(f"../data/secret/{ind}.in", 'w') as f:
        print(f"{n} {m} {b}", file=f)
        for d in data:
            print(f"{d[0]} {d[1]} {d[2]}", file=f)
        for plans_ in plans:
            print(" ".join([str(c) for c, _ in plans_]), file=f)
        for plans_ in plans:
            print(" ".join([str(d) for _, d in plans_]), file=f)


    with open(f"../data/secret/{ind}.ans", 'w') as f:
        print(f"{sol}", file=f)


def alternate(ind):
    n = 1000
    m = 10
    b = 20

    data = [(100, 100, 50) if x % 2 == 0 else (1, 1, 50) for x in range(n)]
    c = [[20*y+20 if x % 2 == 0 else y+1 for y in range(m)] for x in range(n)]
    d = [[y+1 for y in range(m)] for x in range(n)]

    plans = [list(zip(c_, d_)) for c_, d_ in zip(c, d)]
    sol = solve(b, data, deepcopy(plans))

    with open(f"../data/secret/{ind}.in", 'w') as f:
        print(f"{n} {m} {b}", file=f)
        for d in data:
            print(f"{d[0]} {d[1]} {d[2]}", file=f)
        for plans_ in plans:
            print(" ".join([str(c) for c, _ in plans_]), file=f)
        for plans_ in plans:
            print(" ".join([str(d) for _, d in plans_]), file=f)

    with open(f"../data/secret/{ind}.ans", 'w') as f:
        print(f"{sol}", file=f)


def alternate2(ind):
    n = 1000
    m = 10
    b = 20

    data = [(100, 100, 50) if x % 2 == 0 else (1, 1, 50) for x in range(n)]
    c = [[20*y+20 if x % 2 == 1 else y+1 for y in range(m)] for x in range(n)]
    d = [[y+1 for y in range(m)] for x in range(n)]

    plans = [list(zip(c_, d_)) for c_, d_ in zip(c, d)]
    sol = solve(b, data, deepcopy(plans))

    with open(f"../data/secret/{ind}.in", 'w') as f:
        print(f"{n} {m} {b}", file=f)
        for d in data:
            print(f"{d[0]} {d[1]} {d[2]}", file=f)
        for plans_ in plans:
            print(" ".join([str(c) for c, _ in plans_]), file=f)
        for plans_ in plans:
            print(" ".join([str(d) for _, d in plans_]), file=f)

    with open(f"../data/secret/{ind}.ans", 'w') as f:
        print(f"{sol}", file=f)


def zigzag_price(ind, p, r, s):
    n = 1000
    m = 10
    b = 20

    def zigzag_(i, factor): return i % factor + \
        1 if (i//factor) % 2 == 0 else (factor*n-i-1) % factor+1

    data = [(zigzag_(x, p), zigzag_(2*x, r), zigzag_(3*x, s))
            for x in range(n)]
    
    c = [[zigzag_(x+y, p) for y in range(m)] for x in range(n)]
    d = [[zigzag_(x+y, r) for y in range(m)] for x in range(n)]

    plans = [list(zip(c_, d_)) for c_, d_ in zip(c, d)]
    sol = solve(b, data, deepcopy(plans))

    with open(f"../data/secret/{ind}.in", 'w') as f:
        print(f"{n} {m} {b}", file=f)
        for d in data:
            print(f"{d[0]} {d[1]} {d[2]}", file=f)
        for plans_ in plans:
            print(" ".join([str(c) for c, _ in plans_]), file=f)
        for plans_ in plans:
            print(" ".join([str(d) for _, d in plans_]), file=f)

    with open(f"../data/secret/{ind}.ans", 'w') as f:
        print(f"{sol}", file=f)


def subset_sum_case(ind):
    """
    Each block forces them to solve a (small) subset sum problem to get the optimal answer.

    In each block:
    Day 1  : (100, 1, capacity + 1)    <-- Gives you a full tank
    Day 2-6: (100, 1, 1)               <-- Does nothing
    Day 8  : (1, capacity + 1, 1)      <-- Empties your bank account. Tomorrow, you're going to get a full tank for free. So cheap is okay.

    Cost is always $100 to buy, so never worth it to buy.
    We'll give you $100 per item you buy on days 2-6, where the subset sum is happening (max $500).
    Then give you $10000 for (capacity - desired_sum).

    So optimal answer is to buy $10000, plus subset sum the desired_sum.
    """
    capacity = 20

    def subset_sum(desired_sum: int, d: list[int]) -> bool:
        possible = [False for _ in range(desired_sum + 1)]
        possible[0] = True
        for x in d:
            for v in range(desired_sum, x - 1, -1):
                if possible[v - x]:
                    possible[v] = True
        return possible[desired_sum]


    def block(desired_sum: int, binary_block: bool) -> list[tuple[int, int]]:
        d = [1, 2, 4, 8, 16]
        if not binary_block:
            d = []
            while not subset_sum(desired_sum, d):
                d = list(choices(range(1, desired_sum+1), k=5))
        shuffle(d)
        d = [1] + d + [capacity - desired_sum]
        c = [100 for _ in range(len(d))]
        c[0] = 1
        c[-1] = 10000

        return list(zip(c, d))

    plans = []
    days = []

    for desired_sum in range(1, capacity):
        me = block(desired_sum, True)
        plans.extend(me)
        days.extend([(100, 1, desired_sum + 1)] + [(100, 1, 1) for _ in range(len(me)-2)] + [(1, capacity + 1, 1)])

    while len(plans) <= 800:
        desired_sum = randint(1, capacity - 1)
        me = block(desired_sum, False)
        plans.extend(me)
        days.extend([(100, 1, desired_sum + 1)] + [(100, 1, 1) for _ in range(len(me)-2)] + [(1, capacity + 1, 1)])

    formatted_plans = [[t] for t in plans]
    sol = solve(capacity, days, formatted_plans)

    n = len(days)
    m = 1
    b = capacity
    data = days

    with open(f"../data/secret/{ind}.in", 'w') as f:
        print(f"{n} {m} {b}", file=f)
        for d in data:
            print(f"{d[0]} {d[1]} {d[2]}", file=f)
        for c, _ in plans:
            print(c, file=f)
        for _, d in plans:
            print(d, file=f)

    with open(f"../data/secret/{ind}.ans", 'w') as f:
        print(f"{sol}", file=f)


def solve(b, data: list[tuple[int, int, int]], plans: list[list[tuple[int, int]]]):
    INIT = 1 << 63
    min_cost = [INIT for _ in range(b+1)]
    min_cost[0] = 0

    for plans_ in plans:
        plans_.append((0, 0))
    for (d, plans_) in zip(data, plans):
        new_min_cost = [INIT for _ in range(b+1)]
        p = d[0]
        r = d[1]
        s = d[2]

        for end_bat in range(b+1):
            new_min = INIT
            for start_bat in range(b+1):
                for (c, d) in plans_:
                    # how much do we need to buy? we need to have r+end_bat+d power, and we get s+start_bat for free
                    # if the value is negative it means the end_bat is too low and we can't reach this number, and have
                    # to waste some power
                    new_min = min(
                        new_min, min_cost[start_bat] + max((r + end_bat + d - s - start_bat) * p, 0) - c)
            # new_min_cost[end_bat] = min([ min_cost[start_bat] + (r + end_bat + d - s - start_bat) * p  for start_bat in range(b+1)])
            new_min_cost[end_bat] = new_min
        min_cost = new_min_cost

    return min(min_cost)


sample_case(1, 10, [(4, 3, 3), (1, 5, 3)], [[(4, 2),], [(9, 3)]])
sample_case(2, 5, [(1, 5, 3), (9, 4, 3), (10, 6, 3)], [[(1, 1), (3, 2), (4, 3), (9, 4)], [
            (1, 1), (3, 2), (6, 3), (9, 4)], [(1, 1), (3, 2), (6, 3), (30, 4)]])
sample_case(3, 2, [(1, 3, 6), (4, 6, 3), (10, 6, 3)], [
            [(4, 1), (10, 10)], [(2, 2), (9, 4)], [(10, 1), (20, 3)]])

secret_case("break_greedy0", 5, [[10, 1, 1], [100, 1, 1]], [
            [(1, 100)], [(100, 3)]])
secret_case("break_greedy1", 6, [[1, 1, 1], [100, 1, 1], [100, 1, 1]], [
            [(1, 100)], [(100, 3)], [(50, 2)]])

random_case_no_dup(1, 10, 10, 10, 10, 10, 5)
random_case_no_dup(2, 5, 10, 10, 10, 10, 10)
random_case_no_dup(3, 5, 10, 10, 10, 10, 10)
random_case_no_dup(4, 100, 20, 10, 10, 10, 10)
random_case_no_dup(5, 100, 20, 10, 10, 10, 10)
random_case_no_dup(6, 100, 20, 10, 10, 10, 10)
random_case_no_dup(7, 100, 20, 10, 10, 10, 10)
random_case_no_dup(8, 100, 20, 10, 10, 10, 10)
random_case_no_dup(9, 100, 20, 10, 10, 10, 10)
random_case_no_dup(10, 1000, 20, 100, 100, 80, 10)
random_case_no_dup(11, 1000, 20, 100, 100, 90, 10)
random_case_no_dup(12, 1000, 20, 100, 100, 100, 10)
random_case_no_dup(13, 1000, 20, 100, 100, 70, 10)
random_case_with_dup_unsorted(14, 100, 20, 10, 10, 10, 10)
random_case_with_dup_unsorted(15, 100, 20, 10, 10, 10, 10)
random_case_with_dup_unsorted(16, 100, 20, 10, 10, 10, 10)
max_sell("max_sell")
max_solar("max_solar")
max_buy("max_buy")
alternate("alternate_price")
alternate2("alternate_price2")
increasing_price("increasing")
decreasing_price("decreasing")
zigzag_price("zigzag", 100, 71, 59)
zigzag_price("zigzag2", 2, 5, 8)
subset_sum_case("subset_sum")