Un spărgător care doreşte să golească un seif are nevoie de codul acestuia şi pentru aceasta are deja o secvenţă de K numere naturale care reprezintă în mod cert o parte din cod, care din păcate nu este obligatoriu complet. El primeşte de la doi asociaţi câte o secvenţă de M respectiv N numere naturale, care, spune fiecare din ei, este codul corect şi complet. Pentru că cele două coduri nu coincid, spărgătorul, pentru a-şi maximiza şansele, încearcă să determine un cod cât mai lung, format dintr-un şir de numere care este comun celor două şiruri primite de la asociaţi şi, în plus, să conţină ca subşir codul său.
Cerința
Dat un şir de numere naturale c[1],c[2],...,c[K] ce reprezintă codul spărgătorului, precum şi alte două şiruri de numere naturale x[1],x[2],...,x[M] şi y[1],y[2],...,y[N], ce reprezintă codurile celor doi asociaţi, să se determine lungimea maximă a unui şir de numere care este cod comun celor două coduri ale asociaţilor şi conţine, în plus, ca subşir codul spărgătorului.
Date de intrare
Fișierul de intrare cod2.in conţine pe prima linie trei numere naturale K, M şi N separate prin câte un spaţiu, care reprezintă lungimile celor trei coduri, pe linia a doua se găsesc K numere naturale separate prin câte un spaţiu reprezentând codul spărgătorului. Pe linia a treia se găsesc M numere naturale separate prin câte un spaţiu reprezentând codul primului asociat, iar pe linia a patra se găsesc N numere naturale separate prin câte un spaţiu reprezentând codul celui de-al doilea asociat.
Date de ieșire
Fișierul de ieșire cod2.out conţine pe prima linie un număr natural, care reprezintă lungimea maximă a unui cod ce respectă cerinţele.
Restricții și precizări
1 ≤ K ≤ M,N ≤ 255- codurile conţin numere naturale din intervalul
1..255 - un subşir se obţine dintr-un şir prin eliminarea a zero, unul sau mai multe elemente, nu neapărat situate pe poziţii consecutive
- Pentru datele de intrare va exista întotdeauna o soluţie de lungime cel puţin
K
Exemplu
cod2.in
2 8 9 5 2 2 5 6 2 9 5 9 6 5 6 5 9 2 6 2 9 7
cod2.out
4
Explicație
Codul spărgătorului are lungimea K=2 şi este şirul 5,2. Cele două coduri ale asociaţilor sunt de lungimi M=8 şi respectiv N=9 şi sunt date de şirurile de pe liniile 3 şi 4. 4 este lungimea maximă a codului comun celor două coduri ale asociaţilor şi care conţine ca subşir codul spărgătorului. Acesta este 5,6,2,6. Există un cod de lungime 5 comun celor două coduri ale asociaţilor, anume 5 6 5 9 6, dar nu conţine ca subşir codul 5 2.
Cum e corect?
cout < "As la info";
cout << "As la info";
cout >> "As la info";
Felicitări! Poți mai mult?
Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.
Greșit, dar nu-i bai!
Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.
Rezolvare
Iată rezolvarea de 100 de puncte pentru problema cod2:
/*
Implementare: Dan Pracsiu
Complexitate timp: O(k*m*n)
Memorie O(m*n)
*/
#include<bits/stdc++.h>
#define InFile "cod2.in"
#define OutFile "cod2.out"
#define nmax 260
using namespace std;
int c[nmax],x[nmax],y[nmax],k,m,n;
int A[nmax][nmax],B[nmax][nmax];
void ReadData()
{
int i;
freopen(InFile,"r",stdin);
scanf("%d %d %d",&k,&m,&n);
for (i=1;i<=k;i++) scanf("%d",c+i);
for (i=1;i<=m;i++) scanf("%d",x+i);
for (i=1;i<=n;i++) scanf("%d",y+i);
}
void Init()
{
int i,j,max;
for (i=1;i<=n;i++)
if (x[1]==y[i]) B[1][i]=1;
else B[1][i]=B[1][i-1];
for (i=1;i<=m;i++)
if (x[i]==y[1]) B[i][1]=1;
else B[i][1]=B[i-1][1];
for (i=2;i<=m;i++)
for (j=2;j<=n;j++)
{
if (x[i]==y[j]) B[i][j] = 1+B[i-1][j-1];
else
{
max = B[i-1][j];
if (max < B[i][j-1]) max = B[i][j-1];
B[i][j] = max;
}
}
}
int Solve()
{
int i,j,p,maxim,lin,col;
Init();
lin = 1;
col = 1;
for (p=1;p<=k;p++)
{
/* Transfer B in A */
for (i=1;i<=m;i++)
for (j=1;j<=n;j++) A[i][j]=B[i][j];
/* Calculez B(p,i,j) */
for ( ;x[lin] != c[p];lin++) ;
for ( ;y[col] != c[p];col++) ;
for (i=1;i<lin;i++)
for (j=1;j<=n;j++) B[i][j] = 0;
for (i=1;i<col;i++)
for (j=1;j<=m;j++) B[j][i] = 0;
for (i=lin;i<=m;i++)
for (j=col;j<=n;j++)
if ((c[p]==x[i]) && (x[i]==y[j])) B[i][j] = 1+A[i-1][j-1];
else if ((c[p]!=x[i]) && (x[i]==y[j])) B[i][j]=1+B[i-1][j-1];
else
{
maxim = B[i-1][j];
if (maxim < B[i][j-1]) maxim = B[i][j-1];
B[i][j] = maxim;
}
}
return B[m][n];
}
void PrintSol(int sol)
{
freopen(OutFile,"w",stdout);
printf("%d\n",sol);
}
int main()
{
int sol;
ReadData();
sol = Solve();
PrintSol(sol);
return 0;
}
Atenție
Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa 
.
Rezolvarea problemei #2065 cod2
Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2065 cod2 de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.
Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!