zju1937-2.pas 1.0 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445
  1. program zju1937;
  2. var num,ans :array[0..500] of integer;
  3. n,min,ok:integer;
  4. procedure out(t:integer);
  5. var i:integer;
  6. begin
  7. for i:=0 to t do
  8. begin
  9. write(ans[i]);
  10. if i<>t then write(' ');
  11. end;
  12. writeln;
  13. end;
  14. procedure dfs(i:integer);
  15. var k1,k2 :integer;
  16. begin
  17. for k1:=i-1 downto 0 do
  18. for k2:=k1 downto 0 do
  19. begin
  20. if num[k1]+num[k2]<=num[i-1] then exit;
  21. if num[k1]+num[k2]<=n then
  22. begin
  23. num[i]:=num[k1]+num[k2];
  24. if (num[i]<n) and ((i<min) or (min=0)) then dfs(i+1);
  25. if (num[i]=n) and ((i<min) or (min=0)) then begin
  26. ans:=num;
  27. min:=i;
  28. end;
  29. end;
  30. end;
  31. end;
  32. begin
  33. assign(input,'in.txt');
  34. assign(output,'out.txt');
  35. reset(input);
  36. rewrite(output);
  37. readln(n);
  38. num[0]:=1;
  39. min:=0;
  40. ans:=num;
  41. if n>1 then dfs(1);
  42. out(min);
  43. close(input);
  44. close(output);
  45. end.