fork download
  1. // accepted, originally intended solution
  2. module solution;
  3. // version = IO_FILES;
  4. import std.algorithm;
  5. import std.math;
  6. import std.stdio;
  7. import std.typecons;
  8.  
  9. immutable string PROBLEM_NAME = "caps-and-cakes";
  10.  
  11. auto triangleArea (long n)
  12. {
  13. return n * (n + 1) / 2;
  14. }
  15.  
  16. auto triangleIndex (long n)
  17. {
  18. long num = cast (long) (sqrt (n * 2.0L));
  19. return num - (triangleArea (num) > n);
  20. }
  21.  
  22. immutable int size = 6;
  23. immutable int limit = 1000;
  24.  
  25. auto solveTrianglesMitM (long n)
  26. {
  27. alias Entry = Tuple !(int, q{num}, long, q{prev});
  28. auto f = new Entry [limit];
  29.  
  30. foreach (cur; 1..limit)
  31. {
  32. f[cur].num = int.max;
  33. long tri = 1;
  34. while (triangleArea (tri) <= cur)
  35. {
  36. f[cur] = min (f[cur], Entry (f[cast (int)
  37. (cur - triangleArea (tri))].num + 1, tri));
  38. tri += 1;
  39. }
  40. }
  41.  
  42. long [size] res;
  43.  
  44. foreach (step; 0..size)
  45. {
  46. auto tri = (n < limit) ? f[cast (int) (n)].prev :
  47. triangleIndex (n);
  48. res[step] = tri + 1;
  49. n -= triangleArea (tri);
  50. }
  51.  
  52. return res;
  53. }
  54.  
  55. void main ()
  56. {
  57. version (IO_FILES)
  58. {
  59. stdin = File (PROBLEM_NAME ~ ".in", "rt");
  60. stdout = File (PROBLEM_NAME ~ ".out", "wt");
  61. }
  62.  
  63. long n;
  64. while (readf (" %s", &n) > 0)
  65. {
  66. auto ans = solveTrianglesMitM (n - 1);
  67. writefln ("%s\n%(%s %)", 6, ans[]);
  68. }
  69. }
  70.  
Success #stdin #stdout 0s 2756KB
stdin
64449908476890321
stdout
6
359026206 26796 231 3 14 17