Cod sursa(job #353561)

Utilizator PavelRazvanPavel Razvan PavelRazvan Data 5 octombrie 2009 16:28:06
Problema Elimin 2 Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include<stdio.h>
#include<string.h>
#define DIM 2005
char a[DIM],b[DIM],sol[DIM];
int n,v[DIM][DIM];
int max (int x,int y)
{
    if(x<y)
        return y;
    return x;
}
int main ()
{
    freopen("elimin2.in","r",stdin);
    freopen("elimin2.out","w",stdout);
    int i,j,q=0;
    while(scanf("%c",&a[++n])!=EOF);
    n-=2;
    for(i=1;i<=n;++i)
        b[n-i+1]=a[i];
    for(i=1;i<=n;++i)
        for(j=1;j<=n;++j)
            if(a[i]==b[j])
                v[i][j]=v[i-1][j-1]+1;
            else
                v[i][j]=max(v[i-1][j],v[i][j-1]);
    for(i=j=n;i && j;)
    {
        if(a[i]==b[j])
        {
            sol[++q]=a[i];
            --i;
            --j;
        }
        else if(v[i-1][j]<v[i][j-1])
            --j;
        else
            --i;
    }
    j=0;
    if(sol[1]=='0')
        j=1;
    for(i=j+1;i<=q-j;++i)
        printf("%c",sol[i]);
    return 0;
}