Cod sursa(job #3328753)

Utilizator unomMirel Costel unom Data 10 decembrie 2025 09:41:15
Problema Nunta Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.65 kb
#include <fstream>

using namespace std;

#define int long long

ifstream in("nunta.in");
ofstream out("nunta.out");
int n;
int ans[1005];
int factori[1005];
int rez[1005];

void inmultire(int v[], int x)
{
    int t = 0;
    for(int i = 1; i<=v[0]; i++)
    {
        t += v[i] * x;
        v[i] = t % 10;
        t /= 10;
    }

    while(t != 0)
    {
        v[0]++;
        v[v[0]] = t % 10;
        t /= 10;
    }
}

void adunare(int a[], int b[])
{
    a[0] = max(a[0], b[0]);
    int t = 0;

    for(int i = 1; i<=a[0]; i++)
    {
        t += a[i];
        if(i <= b[0])
        {
            t += b[i];
        }

        a[i] = t % 10;
        t /= 10;
    }

    while(t != 0)
    {
        a[0]++;
        a[a[0]] = t % 10;
        t /= 10;
    }
}

void comb(int n, int k)
{
    for(int i = 1; i<=n; i++)
    {
        factori[i] = 0;
    }

    for(int i = 2; i<=n; i++)
    {
        int x = i;

        for(int d = 2; d*d<=x; d++)
        {
            while(x % d == 0)
            {
                factori[d]++;
                x /= d;
            }
        }

        if(x > 1)
        {
            factori[x]++;
        }
    }

    for(int i = 2; i<=k; i++)
    {
        int x = i;

        for(int d = 2; d*d<=x; d++)
        {
            while(x % d == 0)
            {
                factori[d]--;
                x /= d;
            }
        }

        if(x > 1)
        {
            factori[x]--;
        }
    }

    for(int i = 2; i<=n - k; i++)
    {
        int x = i;

        for(int d = 2; d*d<=x; d++)
        {
            while(x % d == 0)
            {
                factori[d]--;
                x /= d;
            }
        }

        if(x > 1)
        {
            factori[x]--;
        }
    }

    ans[0] = ans[1] = 1;
    for(int i = 2; i<=n; i++)
    {
        for(int j = 1; j<=factori[i]; j++)
        {
            inmultire(ans, i);

//            out<<i<<" ";
        }
    }
//    out<<'\n';

//    for(int i = ans[0]; i>=1; i--)
//    {
//        out<<ans[i];
//    }
//    out<<'\n';

    adunare(rez, ans);
}

void starsandbars(int cutii, int obiecte)
{
    comb(cutii + obiecte - 1, cutii - 1);
}

signed main()
{
    in>>n;

    int start;
    if(n % 2 == 0)
    {
        start = 0;
    }
    else
    {
        start = 1;
    }

    for(int i = start; i<=n; i += 2)
    {
        int cutii = i + 1;
        int obiecte = (n - i) / 2;

        starsandbars(cutii, obiecte);
    }

    for(int i = rez[0]; i>=1; i--)
    {
        out<<rez[i];
    }

    return 0;
}