frac1.pas

来自「Magio牛的usaco源代码」· PAS 代码 · 共 69 行

{
ID:maigoak1
PROG:frac1
}

program frac1;
const
  maxn=160;
type
  frac=record
    a,b:integer;
  end;
var
  fin,fout:text;
  heap:array[1..maxn*2+1]of frac;
  n,i,p:integer;
  t:frac;
function gcd(x,y:integer):integer;
  var
    r:integer;
  begin
    while x mod y>0 do begin
      r:=x mod y;
      x:=y;
      y:=r;
    end;
    gcd:=y;
  end;
function smaller(x,y:frac):boolean;
  begin
    if x.a*y.b<x.b*y.a then smaller:=true else smaller:=false;
  end;
begin
  assign(fin,'frac1.in');
  reset(fin);
  readln(fin,n);
  close(fin);
  assign(fout,'frac1.out');
  rewrite(fout);
  writeln(fout,'0/1');
  for i:=1 to n do
    with heap[i] do begin
      a:=1;
      b:=n+1-i;
    end;
  for i:=n+1 to maxn*2+1 do
    with heap[i] do begin
      a:=1;
      b:=0;
    end;

  repeat
    writeln(fout,heap[1].a,'/',heap[1].b);
    if heap[1].b=1 then break;
    repeat
      inc(heap[1].a);
    until gcd(heap[1].a,heap[1].b)=1;
    p:=1;
    repeat
      if smaller(heap[p*2],heap[p*2+1]) then begin
        t:=heap[p];heap[p]:=heap[p*2];heap[p*2]:=t;p:=p*2;end
      else begin
        t:=heap[p];heap[p]:=heap[p*2+1];heap[p*2+1]:=t;p:=p*2+1;end;
    until smaller(heap[p],heap[p*2]) and smaller(heap[p],heap[p*2+1]);
  until false;

  close(fout);
end.