# PBinfo #4133 – microbuz – Rezolvare C++ Sursa: Codul lui Andrei Limbaj: C++ Autor rezolvare: deivid ## Enunț 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. ## Cod sursă C++ ```cpp #include #define INF (INT_MAX >> 2) #define K_MAX 10 #define S_MAX (K_MAX * (K_MAX + 1) / 2) #define C_MAX 100 using namespace std; ifstream fin("microbuz.in"); ofstream fout("microbuz.out"); int T; int N; int C[K_MAX + 5]; pair D[S_MAX + 5]; ///D[i] = perechea (cost, conf) unde cost reprezinta costul minim sa obtinem distanta i ///si conf reprezinta configuratia cu care acest cost a fost obtinut bitset A[(1 << K_MAX) + 5]; pair compute_conf(int conf) { int cost = 0; int dist = 0; for(int i = 0; i < K_MAX; i++) { if(conf & (1 << i)) { dist += i + 1; cost += C[i]; } } return make_pair(cost, dist); } int main() { fin >> T; for(int i = 0; i < K_MAX; i++) { fin >> C[i]; } fin >> N; if(T <= 2) { for(int i = 1; i <= S_MAX; i++) { D[i].first = INF; } for(int conf = 0; conf < (1 << K_MAX); conf++) { int cost = 0, dist = 0; tie(cost, dist) = compute_conf(conf); if(D[dist].first > cost) { D[dist] = make_pair(cost, conf); } } int ans = INF; int ans_conf[4]; for(int dist_1 = 0; dist_1 <= S_MAX; dist_1++) { for(int dist_2 = 0; dist_2 <= S_MAX && dist_1 + dist_2 <= N; dist_2++) { int dist_3 = N - dist_1 - dist_2; if(dist_3 > S_MAX) { continue; } if(ans > D[dist_1].first + D[dist_2].first + D[dist_3].first) { ans = D[dist_1].first + D[dist_2].first + D[dist_3].first; ans_conf[1] = D[dist_1].second; ans_conf[2] = D[dist_2].second; ans_conf[3] = D[dist_3].second; } } } if(T == 1) { fout << ans << "\n"; } else { for(int i = 1; i <= 3; i++) { for(int j = 0; j < K_MAX; j++) { if(ans_conf[i] & (1 << j)) { fout << j + 1 << " " << C[j] << "\n"; } } } } } else { for(int conf = 1; conf < (1 << K_MAX); conf++) { int cost = 0, dist = 0; tie(cost, dist) = compute_conf(conf); for(int i = 0; i < K_MAX; i++) { if(conf & (1 << i)) { A[conf] |= A[conf ^ (1 << i)]; } } A[conf][cost] = 1; } int ans = 0, ans_conf = 0; for(int conf = 1; conf < (1 << K_MAX) - 1; conf++) { int cost = 0, dist = 0; tie(cost, dist) = compute_conf(conf); int flip = ((1 << K_MAX) - 1) ^ conf; if(A[flip][cost]) { if(cost > ans) { ans = cost; ans_conf = conf; } } } fout << ans << "\n"; for(int i = 0; i < K_MAX; i++) { if(ans_conf & (1 << i)) { fout << i + 1 << " "; } } fout << "\n"; int flip = ((1 << K_MAX) - 1) ^ ans_conf; for(int conf = 1; conf <= flip; conf++) { if((conf & flip) == conf) { ///conf este submultime a lui flip int cost = 0, dist = 0; tie(cost, dist) = compute_conf(conf); if(cost == ans) { for(int i = 0; i < K_MAX; i++) { if(conf & (1 << i)) { fout << i + 1 << " "; } } return 0; } } } } return 0; } ``` ## Resurse - [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/4133) - [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/4133/cod.cpp) - [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-4133/main.cpp) - [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)