记录编号 7772 评测结果 AWAWWEWWEE
题目名称 美酒节赛羊 最终得分 20
用户昵称 Gravatarzhai 是否通过 未通过
代码语言 Pascal 运行时间 0.914 s
提交时间 2008-11-11 17:02:23 内存使用 15.37 MiB
显示代码纯文本
program goat;
  const
    max=1000000;
  type
    fa=record
      ss:longint;
      pp:integer;
      t:longint;
      fb:longint;
    end;
    sz=array[1..max]of fa;
  const
    f:array[1..3]of fa=((ss:-1;pp:1),(ss:-5;pp:-2),(ss:-10;pp:-5));
  var
    f1,f2:text;
    s:longint;
    p:integer;
    a:sz;
    h,t:longint;
    procedure ini;
      var
        i:longint;
      begin
        assign(f1,'goat.in');reset(f1);
        assign(f2,'goat.out');rewrite(f2);
        read(f1,s,p);
        close(f1);
        for i:=1 to max do begin a[i].ss:=-1;a[i].pp:=-1;a[i].t:=0;a[i].fb:=0;end;
        a[1].ss:=s;
        a[1].pp:=p;
        h:=0;t:=1;
      end;
    function pan(s:longint;p:integer;t:longint):boolean;
      var
        i:longint;
        k:boolean;
      begin
        k:=false;
        i:=h;
        if p<0 then k:=true;
        while (k=false)and(i<t)do begin
         if (s=a[i].ss)and(p=a[i].pp)and(t=a[i].t)then k:=true;
         inc(i);
        end;
        pan:=k;
      end;
    procedure dfs;
      var
        i:integer;
      begin
        repeat
          inc(h);
          if a[h].ss<=0 then exit
          else begin
            if a[h].pp >0 then begin
              for i:=1 to 3 do begin
                inc(t);
                a[t].ss:=a[h].ss+f[i].ss;
                if a[h].pp+f[i].pp<=p then a[t].pp:=a[h].pp+f[i].pp
                else a[t].pp:=a[h].pp;
                a[t].t:=a[h].t+1;
                a[t].fb:=h;
                if pan(a[t].ss,a[t].pp,a[t].t) then dec(t);
              end;
            end;
          end;
        until t=max;
      end;
    begin
      ini;
      dfs;
      write(f2,a[h].t);
      close(f2);
    end.