Cod sursa(job #608567)

Utilizator darrenRares Buhai darren Data 17 august 2011 13:08:03
Problema Planeta Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.57 kb
#include <fstream>

using namespace std;

typedef long long i64;
const int _sum = 31;

int N;
i64 P, bin[32][32];
int ans[32], now;
i64 st[32], dr[32], add[32];

int main()
{
    ifstream fin("planeta.in");
    ofstream fout("planeta.out");

    fin >> N >> P;
    --P;

    bin[0][_sum] = 1;
    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= i; ++j)
        {
            bin[i][j] = bin[j - 1][_sum] * bin[i - j][_sum];
            bin[i][_sum] += bin[i][j];
        }

    st[++st[0]] = N;
    add[++add[0]] = 0;
    dr[++dr[0]] = 1;

    while (now < N)
    {
        if (st[st[0]] == 0)
        {
            --st[0];
            --add[0];
            --dr[0];

            continue;
        }

        int inow;
        for (inow = 1; inow <= st[st[0]]; ++inow)
            if (P >= bin[st[st[0]]][inow] * dr[dr[0]])
                P -= bin[st[st[0]]][inow] * dr[dr[0]];
            else break;

        if (inow == st[st[0]] + 1)
        {
            --inow;
            P += bin[st[st[0]]][inow] * dr[dr[0]];
        }

        ++now;
        ans[now] = inow + add[add[0]];

        i64 aux = st[st[0]--], auxadd = add[add[0]--], auxdr = dr[dr[0]--];

        // dreapta
        st[++st[0]] = aux - inow;
        add[++add[0]] = ans[now];
        dr[++dr[0]] = auxdr;
        // stanga
        st[++st[0]] = inow - 1;
        add[++add[0]] = auxadd;
        dr[++dr[0]] = auxdr * bin[aux - inow][_sum];
    }

    for (int i = 1; i <= N; ++i)
        fout << ans[i] << ' ';

    fin.close();
    fout.close();
}