milk4.pas

Magio牛的usaco源代码

{
ID:maigoak1
PROG:milk4
}

program milk4;
const
  maxq=20000;
  maxp=100;
var
  fin,fout:text;
  pail,s:array[1..maxp]of integer;
  q:integer;
  p,i,j,t,choose:byte;
function gcd(a,b:integer):integer;
  var
    t:integer;
  begin
    if a<b then begin t:=a;a:=b;b:=t;end;
    repeat
      t:=a mod b;a:=b;b:=t;
    until b=0;
    gcd:=a;
  end;
procedure out;
  var
    i:byte;
  begin
    assign(fout,'milk4.out');
    rewrite(fout);
    write(fout,choose);
    for i:=1 to choose do
      write(fout,' ',s[i]);
    writeln(fout);
    close(fout);
    halt;
  end;
procedure judge;
  var
    t:array[1..maxp]of integer;
    ok:array[0..maxq]of boolean;
    g,target,serial:integer;
    i,j:integer;
  begin
    g:=s[1];
    for i:=2 to choose do begin
      g:=gcd(g,s[i]);
      if g=1 then break;
    end;
    if q mod g>0 then exit;
    for i:=1 to choose do
      t[i]:=s[i] div g;
    target:=q div g;

    fillchar(ok,sizeof(ok),0);
    ok[0]:=true;
    serial:=0;
    for i:=0 to target do begin
      if not ok[i] then begin
        serial:=0;
        continue;
      end;
      inc(serial);
      if serial=t[1] then
        out;
      for j:=1 to choose do
        if i+t[j]<=target then
          ok[i+t[j]]:=true
        else
          break;
    end;
    if ok[target] then out;
  end;
procedure search(l,st:byte);
  var
    i:byte;
  begin
    for i:=st to p-choose+l do begin
      s[l]:=pail[i];
      if l<choose then search(l+1,i+1) else judge;
    end;
  end;
begin
  assign(fin,'milk4.in');
  reset(fin);
  readln(fin,q);
  readln(fin,p);
  for i:=1 to p do
    readln(fin,pail[i]);
  close(fin);

  for i:=1 to p-1 do
    for j:=i+1 to p do
      if pail[i]>pail[j] then begin
        t:=pail[i];pail[i]:=pail[j];pail[j]:=t;
      end;

  for choose:=1 to p do
    search(1,1);
end.