比赛 NOIP2008集训模拟5 评测结果 WWWWWWWWWA
题目名称 越狱 最终得分 10
用户昵称 苏轼 运行时间 0.000 s
代码语言 Pascal 内存使用 0.00 MiB
提交时间 2008-11-14 10:14:43
显示代码纯文本
program cch(input,output);
type
 code=record
       d:longint;
       p:longint;
       k:longint;
       station:longint;
      end;
var
 i,n,head,tail,l,oil:longint;
 a:array[1..100000] of code;
 d,p:array[1..10000] of longint;

procedure qsort(l,r:longint);
var
 tmp,x,i,j:longint;
begin
 i:=l; j:=r;
 x:=d[(l+r) div 2];
 repeat
  while d[i]<x do inc(i);
  while d[j]>x do dec(j);
  if i<=j then
   begin
    tmp:=d[i]; d[i]:=d[j]; d[j]:=tmp;
    tmp:=p[i]; p[i]:=p[j]; p[j]:=tmp;
    inc(i); dec(j);
   end;
 until i>j;
 if i<r then qsort(i,r);
 if l>j then qsort(j,l);
end;

begin
 assign(input,'prisonbreak.in');
 assign(output,'prisonbreak.out');
 reset(input);
 rewrite(output);
 readln(n);
 for i:=1 to n do readln(d[i],p[i]);
 qsort(1,n);
 readln(l,oil);
 head:=1; tail:=1;
 a[1].d:=l; a[1].p:=oil; a[1].k:=0; a[1].station:=n+1;
 repeat
   for i:=1 to a[head].station-1 do
    if a[head].d-a[head].p<=d[i] then
      begin
       inc(tail);
       a[tail].d:=d[i]; a[tail].p:=a[head].p-(a[head].d-d[i])+p[i];
       a[tail].k:=a[head].k+1; a[tail].station:=i;
       if a[tail].d-a[tail].p<=0 then
        begin
         write(a[tail].k);
         close(input); close(output);
         halt;
        end;
      end;
   inc(head);
 until head>tail;
 write(-1);
 close(input);
 close(output);
end.