Cod sursa(job #1245442)

Utilizator OwlreeRobert Badea Owlree Data 19 octombrie 2014 11:37:09
Problema Progresie Scor 100
Compilator cpp Status done
Runda Arhiva ICPC Marime 2.16 kb
#include <bits/stdc++.h>

using namespace std;

long long solve(int N, int R) {

    for (int k = 1;; ++k) {
        long long start = k * k - k + 1;
        long long margin = k - 1;

        bool isGood = true;
        for (int i = 1; i < N; ++i) {
            long long here = start + R * i;

            int floorSqrt = (int)sqrt(here);
            int ceilSqrt  = floorSqrt + 1;
            if (floorSqrt * floorSqrt == here) {
                ceilSqrt = floorSqrt;
            }

            long long upperBound = ceilSqrt * ceilSqrt;
            long long lowerBound = upperBound - ceilSqrt + 1;

            if (here + margin < lowerBound) {
                isGood = false;
                break;
            }

            if (here < lowerBound) {
                start += (lowerBound - here);
                margin -= (lowerBound - here);
            } else if (here + margin > upperBound) {
                margin -= here + margin - upperBound;
            }
        }
        if (isGood) {
            return start;
        }
    }

}

long long solve2(int N, int R) {
    for (int i = 0; ; ++ i) {
        long long start = 1LL * i * (i + 1) + 1;
        long long margin = i;
        int isOK = 1;

        for (int it = 1; it < N; ++ it) {
            long long low = start + 1LL * it * R;
            long long high = low + margin;
            int j = (int)sqrt(low - 1);
            long long lowi = 1LL * j * (j + 1) + 1;
            long long highi = 1LL * (j + 1) * (j + 1);

            if (high < lowi) {
                isOK = 0;
                break ;
            }

            if (low < lowi) {
                start += lowi - low;
                margin -= lowi - low;
            }
            else if (high > highi)
                margin -= high - highi;
        }

        if (isOK)
            return start;
    }
}

int main() {

    FILE* readFile = fopen("progresie.in", "r");
    FILE* writeFile = fopen("progresie.out", "w");

    int T = 0;
    fscanf(readFile, "%d", &T);
    int N, R;
    for (int i = 0; i < T; ++i) {
        fscanf(readFile, "%d", &N);
        fscanf(readFile, "%d", &R);
        fprintf(writeFile, "%lld\n", solve2(N, R));
    }

    return 0;
}