Pagini recente » Cod sursa (job #445686) | Cod sursa (job #992982) | Cod sursa (job #599151) | Cod sursa (job #1867596) | Cod sursa (job #119593)
Cod sursa(job #119593)
#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;
}