Cod sursa(job #2632073)

Utilizator mihai50000Mihai-Cristian Popescu mihai50000 Data 2 iulie 2020 10:51:18
Problema Progresie Scor 100
Compilator cpp-64 Status done
Runda Arhiva ICPC Marime 1.1 kb
#include <bits/stdc++.h>

using namespace std;

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

#define int long long

int getPos(long long x)
{
    return sqrt(x - 1) + 1;
}

void solve()
{
    int n, r;
    fin >> n >> r;

    for(int i = 1; ; ++i)
    {
        long long act = i * 1LL * (i - 1) + 1;
        int rest = i - 1;
        bool ok = true;

        for(int it = 1; it < n && ok; ++it)
        {
            act += r;
            int pos = getPos(act);
            long long l = pos * 1LL * (pos - 1) + 1;
            long long r = pos * pos;

            if(act < l)
            {
                if(l - act > rest)
                {
                    ok = false;
                    break;
                }

                rest -= (l - act);
                act = l;
            }

            rest = min(rest * 1LL, r - act);
        }

        if(ok == true)
        {
            fout << act - (n - 1LL) * r << '\n';
            return ;
        }
    }
}

main()
{
    int t;
    fin >> t;

    for(; t; --t)
        solve();
}