Условие

на английски с картинки

В Декартова координатна система решетъчна точка е точка в която абсцисата и ординатата са цели числа (пр: (3,4), но не и (4.5,-10)). За условието на задачата ще наричаме многоъгълник решетъчен, ако всичките му върхове са решетъчни точки. Ортогонален ще е ако страните му са успоредни на оста х или оста у. Изпъкнал многоъгълник има всичките отсечки с краища от многоъгълника изцяло във вътрешността си. Ограждаща кутия на такъв многоъгълник е най-малкият изотетичен (страни успоредни на координатните оси) правоъгълник, който съдържа цялата фигура.

Интересува ни растежа на ортогонален изпъкнал решетъчен многоъгълник (ОИРМ). Не знаем координати на върхове. Разполагаме единствено с лицето на ОИРМ в началото (A0), след n стъпки (An) и размера на ограждащата кутия в началото (B0). При "порастване" на всяка стъпка многоъгълникът се разширява с по 1 квадратче в 4те посоки. Търсим възможните стойности за броя стъпки (n).

Вход

До 50000 реда с по 3 числа - A0 (0 < A0 <= 10000), An (A0 <= An <= 10^18), B0 (0 < B0 < 20000), като Аn трябва да е от тип long long.

Изход

Изведете на отделен ред стойността на n. Всеки ред трябва да е отделен с по един нов ред. Ако има по повече от един отговор за n, те трябва да се изпечатват в нарастващ ред. При невъзможни (но не и некоректни, такива няма да има) входни данни изведете -1.

Решение

Трябва да се забележи връзката между лицата при нарастване на многоъгълника. Важното е, че се запазва формата на фигурата, а тя само се zoom-ва, т.е. ограждащият правоъгълник нараства с по 1 квадратче в 4-те посоки. Броят липсващи квадратчета си остава същият:

математическо решение

От двата корена взимаме само по-големия и проверяваме дали е неотрицателен.

Заради размера на входа се налага мемоизация - предварително изчисляване на някои данни, които ще се ползват по-често и запаметяването им. В масив от списъци за всяко число от 1 до 20000 (всевъзможните B0) записваме делителите му в нарастващ ред:

vector <int> v[MAXB0];
for (int i = 1; i < MAXB0; ++ i)
    for (int j = i; j < MAXB0; j += i)
        v[j].push_back(i);

В случай на повече от едно решение трябва да извеждаме стойностите в нарастващ ред. Започваме от тези с голяма разлика и стигаме до тези, които са близки по стойност (корен от B0).

Код на C++

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
using std::vector;

#define MAXB0 20001

typedef long long ll;
typedef long double lld;

ll A0, B0, An;

vector <int> v[MAXB0];                //all divisors of the numbers < MAXB0, increasingly

int main() {

    for (int i = 1; i < MAXB0; ++ i)
        for (int j = i; j < MAXB0; j += i)
            v[j].push_back(i);


    while (scanf("%lld%lld%lld", &A0, &An, &B0) == 3 && A0 + An + B0 > 0) {
        bool fl = false;

        vector <int>::iterator it, root;
        it = v[B0].begin();
        root = std::upper_bound(v[B0].begin(), v[B0].end(), sqrt(B0));
        ll D, sq, t, n;
        int s;
        while (it != root) {
            s = *it + B0 / *it;
            D = s * s + 4 * (An - A0);
            sq = (ll) sqrt((lld)D);
            t = sq - s;
            n = t / 4;
            ++ it;

            if (sq * sq != D || 4 * n != t || sq < s)
                continue;

            fl = true;
            printf("%lld\n\n", n);    //blank line in between
        }

        if (!fl)
            printf("-1\n\n");         //blank line in between
    }
    return 0;
}