记录编号	98188	评测结果	AAAAAAAAAA
题目名称	导弹拦截	最终得分	100
用户昵称	◆半城烟沙灬為你打天下	是否通过	通过
代码语言	Pascal	运行时间	0.047 s
提交时间	2014-04-21 21:01:45	内存使用	4.80 MiB

Type
     sky=record
	 ff,tt,next:longint;
end;
Var
    c:array[0..300000]of sky;
	r:array[0..300000]of longint;
	f:array[0..3000]of longint;
	x,y,z:array[0..3000]of longint;
	father:array[0..3000]of longint;
	v:array[0..3000]of boolean;
	n,i,j,ans,tot:longint;
procedure swap(var a,b:longint);
var
    t:longint;
begin
      t:=a;a:=b;b:=t;
end;
procedure add(x,y:longint);
begin
      inc(tot);
	  c[tot].ff:=x;
	  c[tot].tt:=y;
	  c[tot].next:=r[x];
	  r[x]:=tot;
end;
procedure pa(l,r:longint);
var
    i,j,miv1,miv2,miv3:longint;
begin
	i:=l;j:=r;
	miv1:=x[(l+r) shr 1];
	miv2:=y[(l+r) shr 1];
	miv3:=z[(l+r) shr 1];
	repeat
	 while (x[i]<miv1) or ((x[i]=miv1) and (y[i]<miv2)) or ((x[i]=miv1) and (y[i]=miv2) and (z[i]<miv3)) do inc(i);
     while (x[j]>miv1) or ((x[j]=miv1) and (y[j]>miv2)) or ((x[j]=miv1) and (y[j]=miv2) and (z[j]>miv3)) do dec(j);
     if i<=j then
	  begin
	   swap(x[i],x[j]);
	   swap(y[i],y[j]);
	   swap(z[i],z[j]);
	   inc(i);
	   dec(j);
	  end;
	until i>j;
	if i<r then pa(i,r);
	if l<j then pa(l,j);
end;
function dfs(x:longint):boolean;
var
    j:longint;
begin
      j:=r[x];
	  while j<>0 do
	   begin
	    if not v[c[j].tt] then
		 begin
		  v[c[j].tt]:=true;
		  if (father[c[j].tt]=0) or dfs(father[c[j].tt]) then
		   begin
		    father[c[j].tt]:=x;
			exit(true);
		   end;
		 end;
		j:=c[j].next;
	   end;
	  exit(false);
end;
Begin
assign(input,'bomba.in');
assign(output,'bomba.out');
reset(input);
rewrite(output);
	  readln(n);
	  for i:=1 to n do read(x[i],y[i],z[i]);
	  pa(1,n);
	  for i:=1 to n do f[i]:=1;
	  for i:=2 to n do
	   for j:=i-1 downto 1 do
	    if (x[i]>x[j]) and (y[i]>y[j]) and (z[i]>z[j]) and (f[i]<f[j]+1) then f[i]:=f[j]+1;
	  ans:=0;
	  for i:=1 to n do if ans<f[i] then ans:=f[i];
	  writeln(ans);
	  for i:=1 to n do
	   for j:=1 to n do
	    if (x[i]>x[j]) and (y[i]>y[j]) and (z[i]>z[j]) then add(i,j);
	  ans:=0;
	  for i:=1 to n do
	   begin
	    fillchar(v,sizeof(v),0);
		if dfs(i) then inc(ans);
	   end;
	  writeln(n-ans);
close(input);
close(output);
end.