ac1158.pas

来自「这是在网络上搜集到的在东京大学的ACM上面解决的一些题目的源码」· PAS 代码 · 共 38 行

program tju1158;
const
  maxn=100000;
var
  count:array[0..maxn]of byte;
  last:array[1..maxn]of word;
  n,i:longint;
procedure back(x:longint);
  begin
    if count[x]=1 then
      write(last[x])
    else begin
      back(x-sqr(last[x]));
      write(' ',last[x]);
    end;
  end;
begin
  fillchar(count,sizeof(count),255);count[0]:=0;
  for n:=1 to maxn do begin
    for i:=1 to trunc(sqrt(n)) do
      if count[n-i*i]<count[n] then begin
        count[n]:=count[n-i*i];
        last[n]:=i;
      end;
    inc(count[n]);
  end;

  repeat
    read(n);
    writeln(count[n]);
    repeat
      write(last[n]);
      dec(n,sqr(last[n]));
      if n=0 then writeln else write(' ');
    until n=0;
  until seekeof;
end.