4133 - microbuz

Cerința

O companie de transport cu microbuze din județul Iași a adoptat o strategie proprie pentru rutele din județ:

• niciun traseu nu poate avea mai mult de 165 kilometri
• distanța între două stații consecutive este de un kilometru
• un pasager poate pleca din orice stație şi poate să își cumpere bilete pentru parcurgerea a 1, 2, ..., 10 kilometri
• fiecare dintre cele zece distanţe posibile au bilete cu preţuri distincte

Gigel, care călătoreşte cu microbuzul exact N kilometri, poate să aleagă una sau mai multe distanţe dintre cele zece stabilite și să cumpere biletele corespunzătoare. Compania impune ca un pasager să poată cumpăra maxim 3 bilete de același tip. Gigel observă că pentru aceeași sumă poate achiziționa seturi diferite de bilete cu prețuri distincte. Pentru exemplu de mai sus, cu 98 de lei el poate cumpăra câte un bilet cu prețurile 11, 14, 29, 44 lei sau câte un bilet cu prețurile 45, 53 lei (11+14+29+44 = 45+53).

Scrieţi un program care să rezolve următoarele cerințe:

• determină preţul minim al unui set de bilete ce poate fi achiziționat pentru parcurgerea a exact N kilometri;
• determină distanţele alese de Gigel, astfel încât preţul total al călătoriei să fie minim;
• determină două seturi distincte de bilete pentru care prețul total al biletelor este același și este cel mai mare posibil. Pentru fiecare set nu este permisă alegerea mai multor bilete cu același preț și nu există două bilete cu același preț în ambele seturi.

Date de intrare

Fișierul de intrare microbuz.in are trei linii. Pe prima linie se află un număr natural C ce reprezintă cerința (1, 2 sau 3). Linia a doua conține zece valori naturale ordonate strict crescător, separate prin câte un spaţiu, reprezentând preţurile pentru parcurgerea a 1, 2, …, 10 kilometri. Linia a treia conţine valoarea N reprezentând distanţa pe care doreşte să o parcurgă Gigel.

Date de ieșire

Fișierul de ieșire microbuz.out are următoarea structură:

• dacă C = 1, pe prima linie se va afișa un întreg reprezentând costul minim al călătoriei;
• dacă C = 2, pe fiecare linie se vor afișa câte două numere întregi, separate printr-un spaţiu, reprezentând distanța parcursă şi preţul biletului corespunzător;
• dacă C = 3, pe prima linie se va afișa prețul comun al celor două seturi de bilete, iar pe următoarele două linii câte un set de bilete dat prin numărul de km pentru biletele din set, în ordine strict crescătoare, separate prin câte un spațiu.

Restricții și precizări

• C ∈ {1, 2, 3}
• 1 ≤ N ≤ 165
• cele 10 prețuri sunt numere naturale din intervalul [10, 99]
• răspunsul la cerința 3 nu depinde de valoarea lui N
• Pentru 28 de puncte, C = 1
• Pentru 38 de puncte, C = 2
• Pentru 34 de puncte, C = 3

Exemplu 1

Intrare

1
11 14 18 23 29 36 44 45 53 64
15

Iesire

86

Rezolvare

def solve_case_1(prices, N):
    # Initialize dp array where dp[i] will be the minimum cost to travel i kilometers
    dp = [float('inf')] * (N + 1)
    dp[0] = 0
    
    for i in range(1, N + 1):
        for j in range(1, 11):
            if i >= j:
                dp[i] = min(dp[i], dp[i - j] + prices[j - 1])
    
    return dp[N]

def solve_case_2(prices, N):
    # Initialize dp array and tracking array
    dp = [float('inf')] * (N + 1)
    dp[0] = 0
    track = [-1] * (N + 1)
    
    for i in range(1, N + 1):
        for j in range(1, 11):
            if i >= j and dp[i - j] + prices[j - 1] < dp[i]:
                dp[i] = dp[i - j] + prices[j - 1]
                track[i] = j
    
    distance = 0
    km = N
    tickets = []
    
    while km > 0:
        ticket = track[km]
        tickets.append(ticket)
        distance += ticket
        km -= ticket
    
    return distance, dp[N], tickets

def solve_case_3(prices, N):
    dp = [float('inf')] * (N + 1)
    dp[0] = 0
    track = [-1] * (N + 1)
    
    for i in range(1, N + 1):
        for j in range(1, 11):
            if i >= j and dp[i - j] + prices[j - 1] < dp[i]:
                dp[i] = dp[i - j] + prices[j - 1]
                track[i] = j
    
    tickets1 = []
    km = N
    while km > 0:
        ticket = track[km]
        tickets1.append(ticket)
        km -= ticket
    
    max_price = 0
    best_comb = []
    
    for i in range(len(tickets1)):
        for j in range(i + 1, len(tickets1)):
            if tickets1[i] != tickets1[j]:
                remaining = N - tickets1[i] - tickets1[j]
                if remaining >= 0:
                    price = prices[tickets1[i] - 1] + prices[tickets1[j] - 1]
                    if price > max_price:
                        max_price = price
                        best_comb = [tickets1[i], tickets1[j]]
    
    return tickets1, best_comb

def main():
    with open('microbuz.in', 'r') as f:
        data = f.read().strip().split('\n')
    
    C = int(data[0].strip())
    prices = list(map(int, data[1].strip().split()))
    N = int(data[2].strip())
    
    if C == 1:
        result = solve_case_1(prices, N)
        with open('microbuz.out', 'w') as f:
            f.write(str(result) + '\n')
    
    elif C == 2:
        distance, price, tickets = solve_case_2(prices, N)
        with open('microbuz.out', 'w') as f:
            f.write(f"{distance} {price}\n")
            for ticket in tickets:
                f.write(f"{ticket} {prices[ticket - 1]}\n")
    
    elif C == 3:
        tickets1, best_comb = solve_case_3(prices, N)
        with open('microbuz.out', 'w') as f:
            f.write(str(len(tickets1)) + '\n')
            for ticket in tickets1:
                f.write(f"{ticket} {prices[ticket - 1]}\n")
            f.write(str(len(best_comb)) + '\n')
            for ticket in best_comb:
                f.write(f"{ticket} {prices[ticket - 1]}\n")

if __name__ == "__main__":
    main()