fork download
copy 
  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
comments (?)
stdin
copy 
64449908476890321
stdout
copy 
6
359026206 26796 231 21 5 5
https://ideone.com/OlI4Su
language:
D (dmd 2.085.0)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!