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
comments (?)
stdin 
64449908476890321
stdout 
6
359026206 26796 231 3 14 17
https://ideone.com/6N0fDt
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!