Ma ajuta cineva cu problema asta va rog?
Curios să afli mai multe despre cauzele pentru care viteza ta la internet nu e constantă, ai început să citești despre diferite protocoale de transmitere a datelor în rețea. Printre altele, ai aflat că protocolul UDP nu oferă garanția că pachetele vor ajunge la destinație în totalitate. Asta explică problema pe care o ai uneori când vorbești cu mama ta pe Skype și unele propoziții nu mai ajung până la tine.
Totuși, ai aflat un alt lucru interesant: UDP nu garantează nici că pachetele ajung la destinație în ordinea în care au fost trimise. Oare din cauza asta simți uneori că discuția se îndreaptă în prea multe direcții simultan?
Cerință
Ți se dă un șir de n numere întregi, reprezentând pachetele trimise și un alt șir cu n - 1 numere întregi, reprezentând pachetele care au ajuns cu succes până la tine. Elementele din cel de-al doilea șir NU vor fi în aceeași ordine ca și cele din primul, dar toate valorile din al doilea șir se găsesc și în primul. Identifică elementul care se găsește în primul șir, dar lipsește din al doilea.
Date de intrare
Pe prima linie se va găsi numărul n, iar pe următoarele două linii elementele celor două șiruri.
Date de ieșire
Programul va afișa pe ecran numărul x, care reprezintă elementul lipsă din cel de-al doilea șir.
Precizări și restricții
1 ≤ n ≤ 1 000
elementele din șir nu vor avea valori mai mari de 100 000, respectiv mai mici de -100 000
Exemple
Date de intrare Date de ieșire
10
32 34 89 -67 45 21 34 5 9 7
34 32 45 89 34 21 5 7 9 -67
Răspunsuri la întrebare
Salut!
Ai rezolvarea in C++ mai jos
#include <iostream>
using namespace std;
int main()
{
int n, a[1001], b[1001];
cin >> n;
for (int i = 1; i <= n; ++i)
{
cin >> a[i];
}
for (int i = 1; i <= n - 1; ++i)
{
cin >> b[i];
}
bool ok;
for (int i = 1; i <= n; ++i)
{
ok = false;
for (int j = i; j <= n; ++j)
{
if (a[i] == b[j])
{
ok = true;
}
}
if (!ok)
{
cout << a[i];
break;
}
}
return 0;
}
- Ti-am atasat si fisierul mai jos
► Perspectiva STL, recomandata :
#include <iostream>
#include <unordered_set>
#include <vector>
using namespace std;
int main() {
int pachet;
int n; //Numar de pachete trimise
vector<int> trimise; //Vector de pachete trimise
unordered_set<int> primite; //Multime de pachete primite
//Citire numar elemente
cin >> n;
//Rezervare spatiu pentru vector de pachete trimise si multime de pachete primite
trimise.reserve(n);
primite.reserve(n - 1);
//Citire pachete trimise
for (int i = 0; i < n; i++) {
cin >> pachet;
trimise.push_back(pachet);
}
//Citire pachete primite
for (int i = 0; i < n-1; i++) {
cin >> pachet;
primite.insert(pachet);
}
bool gasit = 0;
//Pentru fiecare pachet trimis verifica daca se gaseste in multimea de pachete primite
for (int i = 0; i < n && !gasit; i++) {
if (primite.find(trimise[i]) == primite.end()) {
//Daca pachetul nu a fost gasit afiseaza-l si opreste programul
cout << trimise[i];
gasit = 0;
}
}
return 0;
}
► Explicatie :
Pentru a verifica daca un element se afla intr-o multime avem mai multe variante :
- Comparam elementul cautat fata de toate elementele din multime/vector - complexitate foarte proasta - O(n), resursele computerului sunt folosite in mod ineficient.
- Daca elementele sunt sortate crescator putem folosi cautare binara - complexitate foarte buna - O(logn). Dar daca vectorul nu e sortat va trebui sa il sortam, ceea ce inseamna o complexitate de cel putin O(nlogn). Foarte bine in caz ca citim o singura data si apoi facem multe cautari, dar nu ne avantajeaza in cazul de fata. Eventual putem folosi arbori binari pentru a pastra complexitatea cat de cat ok la modificarea multimii dar tot nu ne avantajeaza
- Putem folosi vectori caracteristici daca multimea valorilor care pot fi luate e finita si e destul de mica. Complexitate O(1) de timp dar O(m), unde m e multimea valorilor posibile pentru elemente ca spatiu de memorie ocupat. Noi am avea vreo 200 000 de elemente in problema asta, e cam mult sa folosim un vector caracteristic.
- Folosim unordered_set din STL - complexitate apropiata de O(1) la cautare si nu ocupa foarte multa memorie suplimentara. Unordered_set extinde ideea folosita de vectorii caracteristici si pentru multimi cu numar infinit de elemente folosind functii hash.
Am ales varianta 4 pentru ca in conditiile date este cea mai potrivita. metodele principale folosite pe unordered_set sunt :
- insert(x) - adauga elementul x in multime.
- find(x) - cauta elementul x in multime. Daca acesta e gasit returneaza iterator catre elementul catutat, daca nu gaseste returneaza iterator end. Un iterator e asemanator cu un pointer, cu acesta se pot parcurge structurile din STL element cu element.
- end() - returneaza iterator catre end - locatie de memorie aflata in afara unordered_set
