fork download
copy 
  1. // accepted
  2. module solution;
  3. // version = IO_FILES;
  4. import std.math;
  5. import std.random;
  6. import std.stdio;
  7.  
  8. immutable string PROBLEM_NAME = "caps-and-cakes";
  9.  
  10. auto triangleArea (long n)
  11. {
  12. 	return n * (n + 1) / 2;
  13. }
  14.  
  15. auto triangleIndex (long n)
  16. {
  17. 	long num = cast (long) (sqrt (n * 2.0L));
  18. 	return num - (triangleArea (num) > n);
  19. }
  20.  
  21. immutable int size = 6;
  22.  
  23. auto solveTrianglesRandom (long n)
  24. {
  25. 	long [size] res;
  26. 	debug {long steps = 0;}
  27.  
  28. 	while (true)
  29. 	{
  30. 		debug {steps += 1;}
  31. 		long rem = n;
  32. 		foreach (pos; 0..size)
  33. 		{
  34. 			auto cur = triangleIndex (rem);
  35. 			if (pos < size - 1)
  36. 			{
  37. 				cur -= uniform (0, 1 + uniform (0, 1 +
  38. 				    uniform (0, 1 + cur)));
  39. 			}
  40. 			res[pos] = cur + 1;
  41. 			rem -= triangleArea (cur);
  42. 		}
  43. 		if (rem == 0)
  44. 		{
  45. 			debug {writeln ("n = ", n + 1, ", steps ", steps);}
  46. 			return res;
  47. 		}
  48. 	}
  49. }
  50.  
  51. void main ()
  52. {
  53. 	version (IO_FILES)
  54. 	{
  55. 		stdin  = File (PROBLEM_NAME ~ ".in",  "rt");
  56. 		stdout = File (PROBLEM_NAME ~ ".out", "wt");
  57. 	}
  58.  
  59. 	long n;
  60. 	while (readf (" %s", &n) > 0)
  61. 	{
  62. 		auto ans = solveTrianglesRandom (n - 1);
  63. 		writefln ("%s\n%(%s %)", 6, ans[]);
  64. 		stdout.flush ();
  65. 	}
  66. }
  67.  
Success #stdin #stdout 0.06s 2752KB
comments (?)
stdin
copy 
64449908476890321
stdout
copy 
6
356199944 44950963 909805 20222 4636 276
https://ideone.com/GZ5n1y
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!