Question

Salut!
Am rezolvat problema comun, #2668 de pe pbinfo


Se consideră trei șiruri de numere naturale a = (a1, a2, ..., an), b = (b1, b2, ..., bn) și c = (c1, c2, ..., cn). Toate cele trei șiruri sunt ordonate crescător.

Cerința
Să se determine un număr care apare în cele trei șiruri. Dacă există mai multe astfel de numere, să se determine cel mai mic. Dacă nu există un număr comun celor trei șiruri, afișați valoarea -1.

Date de intrare
Programul citește de la tastatură numărul n reprezentând lungimea celor trei șiruri. Apoi se citesc n numere naturale, separate prin spații, reprezentând elementele șirului a. Apoi se citesc alte n numere naturale, separate prin spații, reprezentând elementele șirului b. La final se citesc n numere naturale, separate prin spații, reprezentând elementele șirului c.

Date de ieșire
Programul va afișa pe ecran numărul x, reprezentând cel mai mic număr natural care apare în toate cele trei șiruri, sau va afișa -1, dacă șirurile nu au niciun element comun.

Restricții și precizări
1 ≤ n ≤ 100.000
numere din cele trei șiruri vor fi mai mici decât 100.000.000
cele trei șiruri sunt ordonate crescător

Exemplu
Intrare

5
3 6 6 8 10
8 8 8 10 10
1 1 8 10 30
Ieșire

8
Explicație
Numărul comun cel mai mic este 8. Mai există un număr comun celor trei șiruri, anume 10, dar este mai mare.

Am solutia asta:
#include

using namespace std;

int main()
{
int n,i,j,k,l=0,a[100005],b[100005],c[100005];
int gasit[100],minim;
cin >>n;
for (i=1; i<=n;i++)
cin >>a[i];
for (i=1; i<=n;i++)
cin >>b[i];
for (i=1; i<=n;i++)
cin >>c[i];
for (i=1; i<=n;i++)
for (j=1; j<=n;j++)
for (k=1; k<=n;k++)
if (a[i]==b[j]==c[k])
gasit[++l]=a[i];
minim=gasit[1];
for (i=1; i<=l;i++)
if (gasit[i] minim=gasit[i];
if (l==0)
cout <<"-1";
else
cout < return 0;
}
Functioneaza, dar la teste nu face prea bine, ca imi da limita de timp depasita si alte erori. M ati putea ajuta???

Answer 1

Partea aceasta:

for (i=1; i<=n;i++)

for (j=1; j<=n;j++)

for (k=1; k<=n;k++)

Are complexitate O($n^3$), adica se executa de $n^3$ ori, ceea ce nu este foarte eficient, asta ar fi cauza pentru limitele de timp depasite.

Partea aceasta:

if (a[i]==b[j]==c[k])

Nu face ceea ce pare sa faca.Compilatorul o va evalua ca "if((a[i] == b[j]) == c[k])" sau ca "if (a[i] == (b[j] == c[k]))"

O alta diferenta mica este declararea vectorilor in afara main-ului, astfel se vor initializa in alta parte a memoriei, pentru care sunt alocati cei 2MB din problema, spre deosebire de initializarea in stiva (pentru care este alocat doar 1MB), ceea ce poate duce la depasirea limitei de memorie.

O mica diferenta in pasii cautarii celui mai mic element comun pentru a nu  depasi limita de timp:

1.Incepe cu cei trei indici i,j si k de la 1.

2.Incepe o bucla cat timp, care se va executa cat timp a[i], b[j] si c[k] nu sunt egale, conditia fiind (a[i] != b[j] || b[j] != c[k])

3.Daca al i-lea element din a este mai mic decat al j-lea element din b sau al k-lea element din c, incrementeaza i

4.Daca al j-lea element din b este mai mic decat al i-lea element din a sau al k-lea element din c, incrementeaza j

5.Daca al k-lea element din c este mai mic decat al i-lea element din a sau al j-lea element din b, incrementeaza k

6. Daca i, j sau k a ajuns in afara vectorului(i > n, j > n sau k > n) atunci scrie -1 si opreste executia

7. Dupa executarea buclei de la 2, afiseaza elementul a[i], b[j] sau c[k]. Deoarece toate sunt egale, nu face nicio diferenta.

Codul cu toate aceste modificari este:

#include <iostream>

using namespace std;

int a[100005],b[100005],c[100005];

int main()

{

int n,i,j,k;

cin >>n;

for (i=1; i<=n;i++)

cin >>a[i];

for (i=1; i<=n;i++)

cin >>b[i];

for (i=1; i<=n;i++)

cin >>c[i];

i = j = k = 1;

while(a[i] != b[j] || b[j] != c[k]){

if(a[i] < b[j] || a[i] < c[k])

i++;

if(b[j] < a[i] || b[j] < c[k])

j++;

if(c[k] < a[i] || c[k] < b[j])

k++;

if(i > n || j > n || k > n){

cout<<-1;

return 0;

}

}

cout << a[i];

return 0;

}

Answer 2

e testat pe pbinfo acum, a luat 100, văd că se mai poate eficientiza dar îl postez în varianta care a tecut testarea şi am folosit interclasare

#include <iostream>

using namespace std;

int a[100001], b[100001], c[100001], d[100001], n, i, j, p, gasit, comun;

int main()

{

   cin >> n;

   for (i=0; i<n; ++i)

       cin >> a[i];

   for (i=0; i<n; ++i)

      cin >> b[i];

   for (i=0; i<n; ++i)

       cin >> c[i];

   i = 0 , j = 0;

   p = 0;

   while(i < n && j < n)

       if(a[i] < b[j])

           { ++i;}

       else

           { if (a[i]==b[j]) { ++j; d[p++]=a[i++]; }

             else ++j;

           }

   while(i < n)

       d[p ++] = a[i ++];

   while (j < n)

       d[p ++] = b[j ++];

   i=0; j=0; gasit=0;

   while (i<n && j<p && gasit==0)

       {

           if (c[i]<d[j])

           {   ++i;  }

           else

           {

               if (c[i]==d[j]) { gasit=1; comun=c[i]; break;}

               else { ++j; }

           }

       }

   if (gasit) cout << comun;

   else cout << -1;

}