Cod sursa(job #3197983)

Utilizator andu9andu nita andu9 Data 27 ianuarie 2024 20:48:04
Problema Elementul majoritar Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.29 kb
#include <fstream>
#include <vector>
using namespace std;

ifstream fin ("elmaj.in");
ofstream fout("elmaj.out");

const int Max = 50000;

vector <int> a(Max);

int n, c, h, l;

void inaltime()
{
    while (l + 2 * h + 3 <= n)
    {
        l += 2 * h + 3;
        ++h;
    }
    l = n - l;
}

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

void impartire(int x)
{
    unsigned int r = 0;
    for (int i = a[0] ; i>= 1 ; --i)
    {
        r  = r * 10 + a[i];
        a[i] = r / x;
        r %= x;
    }
    while (!a[a[0]] && a[0] > 1)
        --a[0];
}

void solve()
{
    a[0] = a[1] = 1;

    for (int i = 2 * h + 2 ; i <= n ; ++i)
        inmultire(i);

    for (int i = 2 ; i <= l ; ++i)
        impartire(i);

    for (int i = 1 ; i < h ; ++i)
        for (int j = 2 ; j <= 2 * i + 1 ; ++j)
            impartire(j);

    for (int i = a[0] ; i >= 1 ; --i)
        fout << a[i];
}

int main()
{
    fin >> c >> n;
    inaltime();

    if (c == 1)
        fout << h;
    else
        solve();

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