|
{
TASK: camelot
LANG: PASCAL
ID: awesome5
}
//没有编译开关优化，还算不太ws。
//for tripley
//by phoeagon
//enumerate
const
tt:array[0..7,1..2]of longint=((1,2),(2,1),(1,-2),(2,-1),(-1,-2),(-2,-1),
(-1,2),(-2,1));
ta:Array[1..9,1..2]of longint=((1,0),(0,1),(0,-1),(-1,0),(1,1),(-1,-1),
(-1,1),(1,-1),(0,0)
);
tava:Array[1..9]of longint=(1,1,1,1,1,1,1,1,0);
INFINITY=1000;
var
dp:array[0..31,0..31,0..31,0..31]of integer;
n,m,min,kingi,kingj,count:longint;
knight:array[0..1000,1..2]of longint;
procedure init;
var i,J:longint;
x,a,b:char;
begin
fillchar(dp,sizeof(dp),255);
readln(n,m);
read(x);readln(i);
kingi:=i;
kingj:=ord(x)-ord('A')+1;
while not eof do
begin
inc(count);
read(x);read(i);read(a);
if eoln then readln;
knight[count,1]:=i;knight[count,2]:=ord(x)-ord('A')+1;
end;
FOR I:=1 TO N DO
FOR J:=1 TO M DO
DP[I,J,I,J]:=0;
end;
function okay(a,b:longint):boolean;
begin
if a>0 then
if a<=n then
if b>0 then
if b<=m then
exit(true);
exit(false);
end;
PROCEDURE mindis(a,b:longint);
var
i,hd,tl,x,y,t,SUM:longint;
DONE:BOOLEAN;
QUE:ARRAY[0..1100,1..3]OF LONGINT;
MK:ARRAY[0..30,0..30]OF BOOLEAN;
begin
// WRITELN(A,' ',B,' ',C,' ',D);
fillchar(mk,sizeof(mk),0);
tl:=1;hd:=0;que[1,1]:=a;que[1,2]:=b;que[1,3]:=0;
mk[a,b]:=true;SUM:=MAXLONGINT;//DP[A,B,A,B]:=0;
repeat
inc(hd);
x:=que[hd,1];y:=que[hd,2];t:=que[hd,3];
if (dp[a,b,x,y]<=0)or(dp[a,b,x,y]>t)then
begin
DP[A,B,X,Y]:=T;
dp[x,y,a,b]:=t;
end;
//DONE:=FALSE;
for i:=0 to 7 do
if okay(x+tt[i,1],y+tt[i,2])then
if not mk[x+tt[i,1],y+tt[i,2]]then
begin
mk[x+tt[i,1],y+tt[i,2]]:=true;
inc(tl);
que[tl,1]:=x+tt[i,1];
que[tl,2]:=y+tt[i,2];
que[tl,3]:=t+1;
end;
until hd>=tl;
end;
FUNCTION Max(A,B:LONGINT):LONGINT;
BEGIN
IF A<B THEN EXIT(a)ELSE EXIT(B);
END;
procedure work;
var
i,j,a,b,c,d,x,now,sum,routmax:longint;
poss:boolean;
tmp:Array[0..1100]of integer;
begin
now:=maxlongint;min:=maxlongint;
if count=0 then begin min:=0;exit;end;
for i:=1 to n do
for j:=1 to m do
//enumerate the final point (i,j)
begin
now:=0;poss:=true;
fillchar(tmp,sizeof(tmp),0);
MINDIS(I,J);
sum:=0;routmax:=0;
for c:=1 to count do
begin
tmp[c]:=DP[knight[c,1],knight[c,2]
,i,j];
if tmp[c]<0 then
begin poss:=false;break;end;
inc(sum,tmp[c]);
if routmax<tmp[c]then
routmax:=tmp[c];
end;
if not poss then
continue;
if sum-routmax>min then
continue;
now:=abs(i-kingi)+abs(j-kingj);
//if king goes there on his own
if now+sum<min then begin
min:=now+sum;
//writeln(' ',i,' ',j,' ','***',' ',min);
end;
for x:=1 to 9 do//enumerate the picking up point
begin
a:=kingi+ta[x,1];
b:=kingj+ta[x,2];
if not okay(a,b)then continue;
//(a,b)is the picking up point
for c:=1 to count do
begin
now:=DP[knight[c][1],knight[c][2],
a,b];
IF NOW<0 THEN CONTINUE;
D:=DP[a,b,i,j];
IF D<0 THEN CONTINUE;
//NOW:=NOW+D;
//if sum-tmp[c]+now+tava[x]<min then begin
if sum-tmp[c]+now+d+tava[x]<min then begin
min:=sum-tmp[c]+d+now+tava[x];
//writeln(' ',i,' ',j,' ',a,' ',b,' ',min);
end;
end;
end;
end;
end;
begin
assign(input,'camelot.in');reset(input);
assign(output,'camelot.out');rewrite(output);
init;
work;
writeln(min);
close(input);close(output);
end.
|
{
TASK: prime3
LANG: PASCAL
ID: awesome5
}
{$A+,B-,D-,E-,F-,G+,I-,L-,N+,O-,P+,Q-,R-,S-,T-,V-,X+,Y-}
//for tripley
type
yy=array[1..5,1..5]of longint;
var
compo:array[0..99999]of boolean;
sum,bg:longint;
found:boolean;
tmp:yy;
count:longint;
ans:array[0..200]of yy;
function smaller(const a,b:yy):boolean;inline;
var
i,j:longint;
begin
for i:=1 to 5 do
for j:=1 to 5 do
if (a[i,j]<>b[i,j])then
exit(a[i,j]>b[i,j]);
exit(false);
end;
procedure solution(const rt:yy);inline;
var
i,j:longint;
begin //writeln(sum);
if not found then
found:=true
else writeln;
for i:=1 to 5 do
begin
//write(rt[i,1]);
for j:=1 to 5 do
write(rt[i,j]);
writeln;
end;
//writeln;flush(output);
//halt;
end;
procedure srt; inline;
var
i,j,x:longint;
tmp:yy;
begin
for i:=1 to count-1 do
begin
x:=i;
for j:=i+1 to count do
if smaller(ans[j],ans[x])then
x:=j;
tmp:=ans[x];ans[x]:=ans[i];ans[i]:=tmp;
end;
for i:=count downto 1 do
solution(ans[i]);
end;
procedure init;inline;
var
i,j:longint;
begin
compo[0]:=true;compo[1]:=true;
for i:=2 to 99999 do
if not compo[i]then
for j:=(99999 div i) downto 2 do
compo[j*I]:=true;
//writeln(compo[8210]);
//halt;
{for i:=10000 to 99999 do
if not compo[i]then
write(i,' ');
writeln;halt;}
end;
procedure search_box(var rt:yy);inline;
var
a,b,c,d,x,y,z:longint;
begin
// ab
// cd
// solution(rt);
{for a:=0 to 9 do
begin}
x:=sum-rt[5,1]-rt[5,2]-rt[5,3];
y:=sum-rt[1,4]-rt[2,4]-rt[3,4];
z:=sum-rt[1,1]-rt[2,2]-rt[3,3];
//if z+(y-x)<20 then writeln(z+(y-x));
if odd(z+(y-x))then exit
else a:=(z+(y-x))div 2;
if (a<0)or(a>9)then exit;
b:=sum-rt[4,1]-rt[4,2]-rt[4,3]-a;
c:=sum-rt[1,4]-rt[2,4]-rt[3,4]-a;
if(b<0)or(b>9)then exit;
if(c<0)or(c>9)then exit;
if compo[rt[4,1]*10000+rt[4,2]*1000+
rt[4,3]*100+a*10+b]then
exit;
if compo[rt[1,4]*10000+rt[2,4]*1000+
rt[3,4]*100+a*10+c]then
exit;//continue;
rt[4,4]:=a;rt[4,5]:=b;rt[5,4]:=c;
d:=sum-rt[5,1]-rt[5,2]-rt[5,3]-rt[5,4];
if(d<0)or(d>9)then exit;//continue;
{if rt[1,1]+rt[2,2]+rt[3,3]+rt[4,4]+d<>sum then
exit;//continue;}
if d<>sum-rt[1,5]-rt[2,5]-rt[3,5]-rt[4,5] then
exit;//continue;
if compo[rt[1,5]*10000+rt[2,5]*1000+
rt[3,5]*100+rt[4,5]*10+d]then
exit;//continue;
if compo[rt[5,1]*10000+rt[5,2]*1000+
rt[5,3]*100+rt[5,4]*10+d]then
exit;//continue;
if compo[rt[1,1]*10000+Rt[2,2]*1000+
rt[3,3]*100+Rt[4,4]*10+d]then
exit;//continue;
rt[5,5]:=d;
//solution(rt); //halt;
inc(count);
ans[count]:=rt;
//end;
end;
procedure search_layer3(var rt:yy);inline;
var
a,b,c,d,e,f,g,h,i,j:longint;
begin
//the third line is XYcde
// solution(rt);
a:=rt[3,1];
b:=rt[3,2];
//for c:=0 to 9 do if (sum-a-b-c)div 2<10 then
c:=sum-rt[1,5]-rt[2,4]-rt[4,2]-rt[5,1];
if (c<0)or(c>9)then exit
else rt[3,3]:=c;
if compo[rt[5,1]*10000+rt[4,2]*1000+rt[3,3]*100
+rt[2,4]*10+rt[1,5]] then
exit;//exit;
if rt[5,1]+rt[4,2]+rt[3,3]+rt[2,4]+rt[1,5]<>sum then
exit;
for e:=0 to 4 do //e=1-9 odds
begin
d:=sum-rt[3,1]-rt[3,2]-c-e*2-1;
if (d<0)or(d>9)then continue;
if compo[rt[3,1]*10000+rt[3,2]*1000+c*100+d*10+(e*2+1)] then
continue;
rt[3,3]:=c;rt[3,4]:=d;rt[3,5]:=e*2+1;
a:=rt[1,3];f:=rt[2,3];
//for g:=0 to 9 do if (sum-a-f-g)div 2<10 then
g:=c;
for i:=0 to 4 do//i=1-9 odds
begin
h:=sum-rt[1,3]-rt[2,3]-g-i*2-1;
if(h<0)or(h>9)then continue;
if compo[rt[1,3]*10000+rt[2,3]*1000+g*100+
h*10+(2*i+1)]then
continue;
rt[3,3]:=g;
rt[4,3]:=h;rt[5,3]:=i*2+1;
search_box(rt);
end;
end;
end;
procedure search_layer4(var rt:yy);inline;
var
a,b,c,d,e,f,g,h,i,j:longint;
begin
//the second line is Xbcde
// solution(rt);
a:=rt[2,1];
for b:=0 to 9 do if (sum-rt[2,1]-b)div 3<10 then
for c:=0 to 9 do if (sum-rt[2,1]-b-c)div 2<10 then
for e:=0 to 4 do //e=1-9 odds
begin
d:=sum-rt[2,1]-b-c-e*2-1;
if (d<0)or(d>9)then continue;
if compo[rt[2,1]*10000+b*1000+c*100+d*10+(e*2+1)] then
continue;
rt[2,2]:=b;rt[2,3]:=c;rt[2,4]:=d;rt[2,5]:=e*2+1;
a:=rt[1,2];
//for f:=0 to 9 do if (sum-a-f)div 3<10 then
f:=b;
for g:=0 to 9 do if (sum-a-f-g)div 2<10 then
for i:=0 to 4 do//i=1-9 odds
begin
h:=sum-rt[1,2]-f-g-i*2-1;
if (h<0)or(h>9)then continue;
if compo[rt[1,2]*10000+f*1000+g*100+
h*10+(2*i+1)]then
continue;
rt[2,2]:=f;rt[3,2]:=g;
rt[4,2]:=h;rt[5,2]:=i*2+1;
search_layer3(rt);
end;
end;
end;
procedure search_layer5(var rt:yy); inline;
var
a,b,c,d,e,f,g,h,i,j:longint;
begin
//solution(rt);
a:=bg;//the first line is abcde
for b:=1 to 9 do if (sum-a-b)div 3<10 then
for c:=1 to 9 do if (sum-a-b-c)div 2<10 then
for e:=0 to 4 do //e=1-9 odds
begin
d:=sum-a-b-c-e*2-1;
if (d<=0)or(d>9)then continue;
if compo[a*10000+b*1000+c*100+d*10+(e*2+1)] then
continue;
rt[1,1]:=a;rt[1,2]:=b;rt[1,3]:=c;rt[1,4]:=d;rt[1,5]:=2*e+1;
for f:=1 to 9 do if (sum-a-f)div 3<10 then
for g:=1 to 9 do if (sum-a-f-g)div 2<10 then
for i:=0 to 4 do//i=1-9 odds
begin
h:=sum-a-f-g-i*2-1;
if (h<=0)or(h>9)then continue;
if compo[a*10000+f*1000+g*100+
h*10+(2*i+1)]then
continue;
rt[2,1]:=f;rt[3,1]:=g;
rt[4,1]:=h;rt[5,1]:=i*2+1;
search_layer4(rt);
end;
end;
end;
begin
assign(input,'prime3.in');reset(input);
assign(output,'prime3.out');rewrite(output);
read(sum,bg);init;
search_layer5(tmp);
//writeln;
srt;
if not found then
writeln('NONE');
close(output);//close(input);
end.
|
