比赛 20120710 评测结果 ATTTTTTTTT
题目名称 快餐问题 最终得分 10
用户昵称 IMSL77 运行时间 9.027 s
代码语言 Pascal 内存使用 0.17 MiB
提交时间 2012-07-10 11:59:21
显示代码纯文本
program meal;
type
  integer=longint;
var
  n:integer;
  a,b,c,pa,pb,pc,sa,sb,sc:integer;
  d:array[1..11] of integer;

  procedure Fopen;
  begin
    assign(input,'meal.in'); reset(input);
    assign(output,'meal.out'); rewrite(output);
  end;

  procedure Fclose;
  begin
    close(input); close(output);
  end;

  procedure Init;
  var
    i:integer;
  begin
    readln(a,b,c); readln(pa,pb,pc);
    readln(n);
    for i:=1 to n do read(d[i]);
  end;

  function DFS(k,na,nb,nc:integer):boolean;
  var
    ia,ib,ic:integer;
  begin
    if (na>=sa) and (nb>=sb) and (nc>=sc) then exit(true);
    if k>n then exit(false);
    for ia:=0 to d[k] div pa do
    for ib:=0 to (d[k]-pa*ia) div pb do
    begin
      ic:=(d[k]-pa*ia-pb*ib) div pc;
      if DFS(k+1,na+ia,nb+ib,nc+ic) then exit(true);
    end;
    exit(false);
  end;

  function check(m:integer):boolean;
  begin
    sa:=m*a; sb:=m*b; sc:=m*c;
    exit(DFS(1,0,0,0));
  end;

  procedure Solve;
  var
    l,r,mid:integer;
  begin
    if n=0 then begin writeln(0); exit; end;
    l:=0; r:=40000;
    repeat
      mid:=(l+r) shr 1;
      if check(mid) then l:=mid+1 else r:=mid-1;
    until l>r;
    writeln(r);
  end;

begin
  Fopen;
  Init;
  Solve;
  Fclose;
end.