fork download
  1. // accepted
  2. module solution;
  3. // version = IO_FILES;
  4. import std.math;
  5. import std.stdio;
  6.  
  7. immutable string PROBLEM_NAME = "caps-and-cakes";
  8.  
  9. auto triangleArea (long n)
  10. {
  11. return n * (n + 1) / 2;
  12. }
  13.  
  14. auto triangleIndex (long n)
  15. {
  16. long num = cast (long) (sqrt (n * 2.0L));
  17. return num - (triangleArea (num) > n);
  18. }
  19.  
  20. immutable int size = 6;
  21.  
  22. auto solveTrianglesRecurFast (long n)
  23. {
  24. long [size] res;
  25. debug {long calls = 0;}
  26.  
  27. bool recur (int pos, long rem)
  28. {
  29. debug {calls += 1;}
  30. if (pos == size)
  31. {
  32. return rem == 0;
  33. }
  34.  
  35. auto cur = triangleIndex (rem);
  36. foreach_reverse (temp; 0..cur + 1)
  37. {
  38. res[pos] = temp + 1;
  39. if (recur (pos + 1, rem - triangleArea (temp)))
  40. {
  41. return true;
  42. }
  43. if (pos == size - 1)
  44. {
  45. break;
  46. }
  47. }
  48. return false;
  49. }
  50.  
  51. if (!recur (0, n))
  52. {
  53. assert (false);
  54. }
  55. debug {writeln ("n = ", n + 1, ", recur calls: ", calls);}
  56. return res;
  57. }
  58.  
  59. void main ()
  60. {
  61. version (IO_FILES)
  62. {
  63. stdin = File (PROBLEM_NAME ~ ".in", "rt");
  64. stdout = File (PROBLEM_NAME ~ ".out", "wt");
  65. }
  66.  
  67. long n;
  68. while (readf (" %s", &n) > 0)
  69. {
  70. auto ans = solveTrianglesRecurFast (n - 1);
  71. writefln ("%s\n%(%s %)", 6, ans[]);
  72. }
  73. }
  74.  
Success #stdin #stdout 0s 2724KB
stdin
64449908476890321
stdout
6
359026206 26796 231 21 5 5