Cod sursa(job #119593)

Utilizator sealTudose Vlad seal Data 2 ianuarie 2008 10:50:47
Problema Hvrays Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.55 kb
#include<stdio.h>
#include<string.h>
#define Nm 5002
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
char S[Nm];

void read(int &a, int &b)
{
    int i;
    
    a=b=4000;
    for(i=1;i<=2500;++i)
        S[(i<<1)-1]='N', S[i<<1]='E';
}

int solve()
{
    register int i,a,b,ans,xmin,ymin,xmax,ymax,x,y,e;
    int X[Nm],Y[Nm],n,j,k;

    read(a,b);
    n=strlen(S+1);
    X[0]=Y[0]=0;
    for(k=1;k<=n;++k)
    {
        X[k]=X[k-1];
        Y[k]=Y[k-1];
        switch(S[k])
        {
            case 'N': ++Y[k]; break;
            case 'S': --Y[k]; break;
            case 'E': ++X[k]; break;
            case 'V': --X[k];
        }
        if(X[k]<0 || X[k]>a || Y[k]<0 || Y[k]>b)
            break;
    }

    if(k>n)
    {
        k=n;
        ans=a-X[n]+b-Y[n];
    }
    else
        ans=a+b;
        
    x=y=xmin=ymin=xmax=ymax=0;
    for(j=n;j;--j)
    {
        e=min(j,k);
        for(i=0;i<e;++i)
            if(xmin+X[i]>=0 && xmax+X[i]<=a
            && ymin+Y[i]>=0 && ymax+Y[i]<=b)
                ans=min(ans,a-x-X[i]+b-y-Y[i]);
        switch(S[j])
        {
            case 'N': ++y; ymin=min(ymin+1,0); ++ymax; break;
            case 'S': --y; --ymin; ymax=max(ymax-1,0); break;
            case 'E': ++x; xmin=min(xmin+1,0); ++xmax; break;
            case 'V': --x; --xmin; xmax=max(xmax-1,0);
        }
    }
    return ans;
}

void write(int ans)
{
    freopen("pasi.out","w",stdout);
    printf("%d\n",ans);
}

int main()
{
    write(solve());
    return 0;
}