Pentru o paradă a modei sunt pregătite seturi de bijuterii, un set fiind format din cercei și pandantiv, cu câte
cel puțin două pietre prețioase și semiprețioase. Sunt utilizate nouă tipuri de pietre, numerotate de la 1 la 9,
iar orice bijuterie are o etichetă, număr natural în care fiecare cifră corespunde unei pietre din montură, în
ordinea descrescătoare a importanței în cadrul modelului. Un set este potrivit dacă cele mai importante
două pietre ale fiecărei bijuterii din set sunt de același tip, chiar dacă nu în aceeași ordine a importanței.
Fișierul bijuterii.in conține numere naturale din intervalul [10,999]: pe prima linie două numere
nc și np, reprezentând numărul de cercei, respectiv de pandantive disponibile, pe a doua linie un șir de
nc numere, reprezentând etichetele cerceilor, iar pe a treia linie un șir de np numere, reprezentând
etichetele pandantivelor. Numerele aflate pe aceeași linie a fișierului sunt separate prin câte un spațiu. Se
cere să se afișeze pe ecran mesajul DA, dacă se poate forma cel puțin un set potrivit de bijuterii, sau
mesajul NU, în caz contrar. Proiectați un algoritm eficient din punctul de vedere al timpului de executare.
Exemplu: dacă fișierul conține numerele alăturate,
se afișează pe ecran mesajul DA
10 11
497 125 521 497 513 258 491 55 551 16
21 259 943 77 945 57 52 552 16 17 71
(două dintre cele 14 seturi potrivite se pot forma din cerceii cu eticheta 258 și fiecare dintre pandantivele cu
etichetele 259, respectiv 52, pentru toate aceste bijuterii pietrele de tipurile 2 și 5 fiind cele mai importante).
a. Descrieți în limbaj natural algoritmul proiectat, justificând eficiența acestuia. (2p.)
b. Scrieți programul C/C++ corespunzător algoritmului proiectat.
#include <iostream>
#include <fstream>
using namespace std;
// Funcție care extrage primele două pietre (cifre) din eticheta unei bijuterii
void extragePietre(int eticheta, int& primaPiatra, int& aDouaPiatra) {
primaPiatra = eticheta / 10; // Extragem prima cifră
aDouaPiatra = eticheta % 10; // Extragem a doua cifră
// Asigurăm ordinea descrescătoare a pietrelor
if (primaPiatra < aDouaPiatra) {
swap(primaPiatra, aDouaPiatra);
}
}
int main() {
//ifstream cin("bijuterii.in"); // Deschidem fișierul pentru citire
// if (!inFile) { // Verificăm dacă fișierul a fost deschis cu succes
// cout << "Nu s-a putut deschide fisierul bijuterii.in!" << endl;
// return 1; // Ieșim din program dacă nu putem deschide fișierul
// }
int nc, np;
cin >> nc >> np; // Citim numărul de cercei și pandantive
// Tablouri pentru etichetele cerceilor și pandantivelor
int cercei[nc];
int pandantive[np];
// Citirea etichetelor cerceilor
for (int i = 0; i < nc; i++) {
cin >> cercei[i];
}
// Citirea etichetelor pandantivelor
for (int i = 0; i < np; i++) {
cin >> pandantive[i];
}
// Comparație între cercei și pandantive
for (int i = 0; i < nc; i++) {
int primaPiatraCercei, aDouaPiatraCercei;
extragePietre(cercei[i], primaPiatraCercei, aDouaPiatraCercei);
for (int j = 0; j < np; j++) {
int primaPiatraPandantiv, aDouaPiatraPandantiv;
extragePietre(pandantive[j], primaPiatraPandantiv, aDouaPiatraPandantiv);
// Comparăm pietrele cele mai importante (fără a ține cont de ordine)
if (primaPiatraCercei == primaPiatraPandantiv && aDouaPiatraCercei == aDouaPiatraPandantiv) {
cout << "DA" << endl;
//cin.close(); // Închidem fișierul
return 0;
}
}
}
// Dacă nu s-a găsit niciun set potrivit
cout << "NU" << endl;
//cin.close(); // Închidem fișierul
return 0;
}