from math import ceil

files = ['a_example', 'b_read_on', 'c_incunabula', 'd_tough_choices', 'e_so_many_books', 'f_libraries_of_the_world']

def load_data(file):
    with open(file, 'r') as f:
        res = f.read().split('\n')
        if res[-1] == '':
            return res[0:-1]
        return res


def parse_data(data):
    libraries = []
    first_row = data[0].split(' ')
    num_of_libs = int(first_row[1])
    time = int(first_row[2])
    book_scores = [int(elem) for elem in data[1].split(" ")]
    for i in range(2, num_of_libs * 2 + 1, 2):
        row = data[i].split(' ')
        books = [int(book) for book in data[i + 1].split(" ")]
        registration_time = int(row[1])
        shipping_amount = int(row[2])
        num_of_books_send = (time - registration_time) * shipping_amount
        books_in_lib = [book_scores[j] for j in books]
        books_dict = {k: v for k, v in zip(books, books_in_lib)}
        lib = {
            'registration_time': registration_time,
            'shipping_amount': shipping_amount,
            'books': books_dict,
            'max_books': num_of_books_send if num_of_books_send < len(books_in_lib) else len(books_in_lib)
        }
        lib['books'] = {k: v for k, v in sorted(lib['books'].items(), key=lambda item: item[1], reverse=True)}
        libraries.append(lib)

    return (book_scores, libraries, time)


def when_books_run_out(library, time_left):
    commited_books_amount = sum([1 if v != 0 else 0 for k, v in library['books'].items()])
    days_needed = ceil(commited_books_amount / library['shipping_amount'])
    res = time_left - days_needed
    return res if res > 0 else 0

def wasted_days_coefficient(wasted_days, time_left): # time
    D = time_left
    x = wasted_days
    q = 1.3
    a = -D*(1-q)*q
    p = D - D*(1-q)
    return a/(x-p) + q
    #(D*(1 - q) * q)/(x - (D - (1 - q) * D)) + q

def calculate_coefficients(libs, time_left):
    coefficients = []
    for lib in libs:
        book_values = list(lib['books'].values())
        book_score = sum(book_values[0:lib['max_books']])
        wasted_days = when_books_run_out(lib, time_left)
        wdc = wasted_days_coefficient(wasted_days, time_left)
        coefficients.append(book_score / lib['registration_time'] * wdc)
        # print(wdc)
    return coefficients


def get_max_coefficient_index(coefficients):
    return coefficients.index(max(coefficients))


def reset_used_books(used_books_indexes):
    for i in used_books_indexes:
        book_scores[i] = 0


def recalculate(libs, time_left, book_scores):
    for lib in libs:
        k = (time_left - lib['registration_time'])  * lib['shipping_amount']
        lib['max_books'] = k if k < len(lib['books']) else len(lib['books'])
        books_indexes = lib['books'].keys()
        books_in_lib = [book_scores[j] for j in books_indexes]
        books_dict = {k: v for k, v in zip(books_indexes, books_in_lib)}
        lib['books'] = books_dict
        lib['books'] = {k: v for k, v in sorted(lib['books'].items(), key=lambda item: item[1], reverse=True)}


def print_result(res):
    with open("res.txt", "w+") as f:
        f.write(str(len(res)) + "\n")
        for k, v in zip(res.keys(), res.values()):
            f.write(str(k) + " " + str(len(v)) + "\n")
            for book in v:
                f.write(str(book))
                if book != list(v)[-1]:
                    f.write(' ')
            f.write("\n")


book_scores, libraries, time = parse_data(load_data(files[2] + ".txt"))
old_time = 0
res = {}
while 0 < time != old_time:
    coefficients = calculate_coefficients(libraries, time)
    best_library_index = get_max_coefficient_index(coefficients)
    best_library = libraries[best_library_index]
    print(best_library)
    res[best_library_index] = best_library['books'].keys()
    reset_used_books(best_library['books'].keys())
    old_time = time
    time = time - best_library['registration_time']
    recalculate(libraries, time, book_scores)

print_result(res)