Pagini recente » Cod sursa (job #782290) | Cod sursa (job #1124156) | Cod sursa (job #2337272) | Cod sursa (job #1598973) | Cod sursa (job #2746323)
#include <fstream>
std::ifstream fin("planeta.in");
std::ofstream fout("planeta.out");
#include <vector>
#include <limits>
using u64 = std::uint64_t;
constexpr u64 NOTSET = std::numeric_limits<u64>::max();
class Factorial
{
public:
static u64 get(const u64 n)
{
if(n >= values.size())
{
values.resize(n + 1, NOTSET);
}
if(values[n] == NOTSET)
{
const u64 val = n * get(n - 1);
values[n] = val;
}
return values[n];
}
static std::vector<u64> values;
};
std::vector<u64> Factorial::values = {1, 1, 2};
u64 catalan(const u64 n)
{
u64 p1 = 1u;
for(u64 i = n + 2u; i <= 2u * n; ++i)
{
p1 *= i;
}
return p1 / Factorial::get(n);
}
u64 getpossible(const u64 left, const u64 rootlim, const u64 right)
{
u64 res = 0;
for(u64 i = left; i < rootlim; ++i)
{
res += catalan(i - left) * catalan(right - i);
}
return res;
}
u64 solve(const u64 left, const u64 right, const u64 target, const u64 sofar)
{
if(left > right)
{
return sofar;
}
if(left == right)
{
fout << left << ' ';
return sofar;
}
u64 start = left;
while(start <= right)
{
const u64 minidx = getpossible(left, start, right);
if(sofar + minidx >= target)
{
break;
}
++start;
}
const u64 found = start - 1;
fout << found << ' ';
const u64 l1 = solve(left, found - 1, target, sofar + getpossible(left, found, right));
solve(found + 1, right, target, l1);
return sofar + getpossible(left, found, right);
}
int main()
{
u64 N, K;
fin >> N >> K;
solve(1, N, K, 0);
fout << '\n';
}