Mai intai trebuie sa te autentifici.

Cod sursa(job #2023054)

Utilizator amza23Amza A amza23 Data 18 septembrie 2017 09:46:48
Problema Algoritmul lui Euclid extins Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <fstream>
#include <iostream>
using namespace std;

ifstream f ("cmlsc.in");
ofstream g ("cmlsc.out");
int A[1025],B[1025],i,j,D[1025][1025],M,N,sir[1025],n;
int main()
{
    f>>M>>N;
    for(i=1;i<=M;i++)   //citire
        f>>A[i];
    for(i=1;i<=N;i++)
        f>>B[i];

    for(i=0;i<=M+1;i++)   //conturare cu 0
        D[i][0]=D[i][N+1]=0;
    for(i=0;i<=N+1;i++)
        D[0][i]=D[M+1][i]=0;

    for(i=1;i<=M;i++)                      //formare matrice
        for(j=1;j<=N;j++)
        if(A[i]==B[j]) D[i][j]=D[i-1][j-1]+1;
        else D[i][j]=max(D[i-1][j],D[i][j-1]);

    i=M;j=N;
    while(i)                            //formare sir
    {
        if(A[i]==B[j]) {n++;
                        sir[n]=A[i];
                        i--;j--;

                        }
        else if(D[i-1][j]<D[i][j-1]) j--;
              else i--;
    }

    g<<n<<'\n';

    for(i=n;i>=1;i--)                           //afisare sir
        g<<sir[i]<<" ";
    return 0;
}