Cod sursa(job #2240015)

Utilizator LolkekzorChiorean Tudor Lolkekzor Data 12 septembrie 2018 10:14:40
Problema Progresie Scor 100
Compilator cpp Status done
Runda Arhiva ICPC Marime 1.35 kb
#include <fstream>
#include <cmath>
using namespace std;

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

int n, r, i, tc, group, crtGrp;
int64_t crtPos, m;
bool ok;

int crtGroup(int64_t x) {
    return (int64_t)sqrt(x - 1.0) + 1;
}

pair<int64_t, int64_t> grpLims(int grp) {
    return make_pair(1LL * grp * (grp - 1) + 1, 1LL * grp * grp);
}

int main()
{
    fin >> tc;

    while(tc--) {
        fin >> n >> r;

        group = 0;
        while(1) {
            group ++;
            crtPos = grpLims(group).first;
            crtGrp = group;
            m = group - 1;

            ok = true;
            for (i = 2 ; i <= n ; i++) {
                crtPos += r;
                crtGrp = crtGroup(crtPos);

                if (crtPos < grpLims(crtGrp).first) {
                    if (grpLims(crtGrp).first - crtPos <= m) {
                        m -= grpLims(crtGrp).first - crtPos;
                        crtPos = grpLims(crtGrp).first;
                    } else {
                        ok = false;
                        break;
                    }
                }

                m = min(m, grpLims(crtGrp).second - crtPos);
            }

            if (ok) {
                fout << crtPos - 1LL * (n - 1) * r << '\n';
                break;
            }
        }
    }

    return 0;
}