// accepted, originally intended solution
module solution;
// version = IO_FILES;
import std.algorithm;
import std.math;
import std.stdio;
import std.typecons;
immutable string PROBLEM_NAME = "caps-and-cakes";
auto triangleArea (long n)
{
return n * (n + 1) / 2;
}
auto triangleIndex (long n)
{
long num = cast (long) (sqrt (n * 2.0L));
return num - (triangleArea (num) > n);
}
immutable int size = 6;
immutable int limit = 1000;
auto solveTrianglesMitM (long n)
{
alias Entry = Tuple !(int, q{num}, long, q{prev});
auto f = new Entry [limit];
foreach (cur; 1..limit)
{
f[cur].num = int.max;
long tri = 1;
while (triangleArea (tri) <= cur)
{
f[cur] = min (f[cur], Entry (f[cast (int)
(cur - triangleArea (tri))].num + 1, tri));
tri += 1;
}
}
long [size] res;
foreach (step; 0..size)
{
auto tri = (n < limit) ? f[cast (int) (n)].prev :
triangleIndex (n);
res[step] = tri + 1;
n -= triangleArea (tri);
}
return res;
}
void main ()
{
version (IO_FILES)
{
stdin = File (PROBLEM_NAME ~ ".in", "rt");
stdout = File (PROBLEM_NAME ~ ".out", "wt");
}
long n;
while (readf (" %s", &n) > 0)
{
auto ans = solveTrianglesMitM (n - 1);
writefln ("%s\n%(%s %)", 6, ans[]);
}
}
Ly8gYWNjZXB0ZWQsIG9yaWdpbmFsbHkgaW50ZW5kZWQgc29sdXRpb24KbW9kdWxlIHNvbHV0aW9uOwovLyB2ZXJzaW9uID0gSU9fRklMRVM7CmltcG9ydCBzdGQuYWxnb3JpdGhtOwppbXBvcnQgc3RkLm1hdGg7CmltcG9ydCBzdGQuc3RkaW87CmltcG9ydCBzdGQudHlwZWNvbnM7CgppbW11dGFibGUgc3RyaW5nIFBST0JMRU1fTkFNRSA9ICJjYXBzLWFuZC1jYWtlcyI7CgphdXRvIHRyaWFuZ2xlQXJlYSAobG9uZyBuKQp7CglyZXR1cm4gbiAqIChuICsgMSkgLyAyOwp9CgphdXRvIHRyaWFuZ2xlSW5kZXggKGxvbmcgbikKewoJbG9uZyBudW0gPSBjYXN0IChsb25nKSAoc3FydCAobiAqIDIuMEwpKTsKCXJldHVybiBudW0gLSAodHJpYW5nbGVBcmVhIChudW0pID4gbik7Cn0KCmltbXV0YWJsZSBpbnQgc2l6ZSA9IDY7CmltbXV0YWJsZSBpbnQgbGltaXQgPSAxMDAwOwoKYXV0byBzb2x2ZVRyaWFuZ2xlc01pdE0gKGxvbmcgbikKewoJYWxpYXMgRW50cnkgPSBUdXBsZSAhKGludCwgcXtudW19LCBsb25nLCBxe3ByZXZ9KTsKCWF1dG8gZiA9IG5ldyBFbnRyeSBbbGltaXRdOwoKCWZvcmVhY2ggKGN1cjsgMS4ubGltaXQpCgl7CgkJZltjdXJdLm51bSA9IGludC5tYXg7CgkJbG9uZyB0cmkgPSAxOwoJCXdoaWxlICh0cmlhbmdsZUFyZWEgKHRyaSkgPD0gY3VyKQoJCXsKCQkJZltjdXJdID0gbWluIChmW2N1cl0sIEVudHJ5IChmW2Nhc3QgKGludCkKCQkJICAgIChjdXIgLSB0cmlhbmdsZUFyZWEgKHRyaSkpXS5udW0gKyAxLCB0cmkpKTsKCQkJdHJpICs9IDE7CgkJfQoJfQoKCWxvbmcgW3NpemVdIHJlczsKCglmb3JlYWNoIChzdGVwOyAwLi5zaXplKQoJewoJCWF1dG8gdHJpID0gKG4gPCBsaW1pdCkgPyBmW2Nhc3QgKGludCkgKG4pXS5wcmV2IDoKCQkgICAgdHJpYW5nbGVJbmRleCAobik7CgkJcmVzW3N0ZXBdID0gdHJpICsgMTsKCQluIC09IHRyaWFuZ2xlQXJlYSAodHJpKTsKCX0KCglyZXR1cm4gcmVzOwp9Cgp2b2lkIG1haW4gKCkKewoJdmVyc2lvbiAoSU9fRklMRVMpCgl7CgkJc3RkaW4gID0gRmlsZSAoUFJPQkxFTV9OQU1FIH4gIi5pbiIsICAicnQiKTsKCQlzdGRvdXQgPSBGaWxlIChQUk9CTEVNX05BTUUgfiAiLm91dCIsICJ3dCIpOwoJfQoKCWxvbmcgbjsKCXdoaWxlIChyZWFkZiAoIiAlcyIsICZuKSA+IDApCgl7CgkJYXV0byBhbnMgPSBzb2x2ZVRyaWFuZ2xlc01pdE0gKG4gLSAxKTsKCQl3cml0ZWZsbiAoIiVzXG4lKCVzICUpIiwgNiwgYW5zW10pOwoJfQp9Cg==