Rezolvare PBinfo #4133

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

De exemplu:

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).

Cerința

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

Exemplul 1:

microbuz.in

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

microbuz.out

86

Explicație

Cerința este 1. Costul minim total este 86.

Exemplul 2:

microbuz.in

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

microbuz.out

3 18
4 23
8 45

Explicație

Cerința este 2. Biletele cumpărate și prețurile lor sunt:
3 km parcurși, preț 18
4 km parcurși, preț 23
8 km parcurși, preț 45

Exemplul 3:

microbuz.in

2
13 17 18 19 21 22 25 28 31 37
39

microbuz.out

7 25
7 25
8 28
8 28
9 31

Explicație

Cerința este 2. Biletele cumpărate și prețurile lor sunt:
7 km parcurși, preț 25
7 km parcurși, preț 25
8 km parcurși, preț 28
8 km parcurși, preț 28
9 km parcurși, preț 31

Exemplul 4:

microbuz.in

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

microbuz.out

163
2 3 4 7 10 
5 6 8 9

Explicație

Cerința este 3. Prețul maxim comun este 163.
Setul 1: câte un bilet cu prețurile 14 18 23 44 64.
Setul 2: câte un bilet cu prețurile 29 36 45 53.