3762 - Butoi

Cerința

Vară, căldură mare. Gigel se joacă în curte udând florile. După ce a terminat, mama lui îi dă o sarcină mai grea. Gigel trebuie să umple un butoi cu apă de rezervă în caz de secetă. Dar nu oricum! El are la dispoziție un șir de găleți de diferite capacități și trebuie să le folosească doar pe acestea pentru umplerea completă a butoiului. O operație constă în umplerea completă a unei o găleți de la sursa de apă și golirea ei în butoi. Desigur, o găleată se poate folosi de mai multe ori. Butoiul are capacitate de V litri, Gigel are N găleți de capacități c1, c2, …, cN litri, numere întregi și distincte și poate folosi o găleată de cel mult K ori. Ajutați-l pe Gigel să umple butoiul. Scrieți un program care să rezolve următoarele cerințe:

1. Determinați câte modalități de umplere a butoiului există; 2. Determinați o modalitate de umplere a butoiului cu număr minim de operații; 3. O secvență de exact P găleți alăturate se numește norocoasă dacă prin efectuarea operației de același număr de ori pentru fiecare dintre ele, vom putea umple complet butoiul. Determinați secvența norocoasă care permite folosirea celor P găleți de un număr minim de ori pentru umplerea completă a butoiului. Secvența norocoasă se va identifica prin poziția primei găleți folosite. Dacă există mai multe soluții se va afișa cea cu poziția minimă. Gălețile din secvența norocoasă se pot folosi de câte ori este nevoie.

Date de intrare

Fișierul de intrare butoi.in conține pe prima linie un număr natural C care poate avea valorile 1, 2 sau 3 și reprezintă numărul cerinței. Linia a doua conține patru valori naturale V N K P, separate prin câte un spațiu, reprezentând în ordine capacitatea butoiului, numărul de găleți, numărul maxim de operații care poate fi efectuat cu o găleată, în cazul cerințelor 1 și 2, iar ultimul număr reprezintă lungimea secvenței norocoase căutate la cerința 3. Linia a treia conține N valori naturale distincte c1, c2, …, cN, separate prin câte un spațiu, reprezentând, în ordine, capacitățile celor N găleți din șir.

Date de ieșire

Fișierul de ieșire butoi.out va conține pentru cerința 1, pe prima linie, un întreg reprezentând numărul de modalități de a umple butoiul. Pentru cerința 2 prima linie va conține N valori naturale separate prin câte un spațiu, reprezentând numărul de utilizări a fiecărei găleți iar pentru cerința 3 prima linie va conține un număr natural reprezentând poziția din șir a primei găleți din secvența norocoasă determinată.

Restricții și precizări

• 5 ≤ V ≤ 360.000
• Pentru cerințele 1 și 2 restricțiile sunt: 1 ≤ N ≤ 9; 1 ≤ ci ≤ 8.000 și 1 ≤ K ≤ 5
• Pentru cerința 3 restricțiile sunt: 3 ≤ N ≤ 100.000; 1 ≤ ci ≤ 200.000; 3 ≤ P ≤ 10.000 și P ≤ N
• Pentru cerința 3 capacitățile c1, c2, …, cN ale găleților nu sunt neapărat distincte

Exemplu 1

Intrare

1
90 7 1 2
30 56 70 34 60 15 5

Iesire

3

Rezolvare

def read_input(file_name):
    with open(file_name, 'r') as file:
        c = int(file.readline().strip())
        V, N, K, P = map(int, file.readline().strip().split())
        galeata_capacities = list(map(int, file.readline().strip().split()))
        if c == 1 or c == 2:
            return c, V, N, K, P, galeata_capacities
        elif c == 3:
            seq_length = P
            return c, V, N, K, P, seq_length, galeata_capacities


def cerinta_1(V, N, K, P, galeata_capacities):
    dp = [0] * (V + 1)
    dp[0] = 1
    for i in range(N):
        for j in range(V, galeata_capacities[i] - 1, -1):
            dp[j] += dp[j - galeata_capacities[i]]
    return dp[V]


def cerinta_2(V, N, K, P, galeata_capacities):
    dp = [float('inf')] * (V + 1)
    dp[0] = 0
    for i in range(N):
        for j in range(galeata_capacities[i], V + 1):
            dp[j] = min(dp[j], dp[j - galeata_capacities[i]] + 1)
    return dp[V] if dp[V] != float('inf') else -1


def cerinta_3(V, N, K, P, seq_length, galeata_capacities):
    from itertools import combinations
    min_index = float('inf')
    for comb in combinations(enumerate(galeata_capacities), P):
        if sum(g[1] for g in comb) == V:
            first_index = min(g[0] for g in comb)
            min_index = min(min_index, first_index)
    return min_index if min_index != float('inf') else -1


def write_output(file_name, result):
    with open(file_name, 'w') as file:
        if isinstance(result, list):
            file.write(' '.join(map(str, result)) + '\n')
        else:
            file.write(str(result) + '\n')


def main():
    input_file = 'butoi.in'
    output_file = 'butoi.out'
    data = read_input(input_file)
    c = data[0]

    if c == 1:
        result = cerinta_1(*data[1:])
    elif c == 2:
        result = cerinta_2(*data[1:])
    elif c == 3:
        result = cerinta_3(*data[1:])

    write_output(output_file, result)


if __name__ == '__main__':
    main()