14785. Zerówka [AL_06_07]

Zadanie:
https://pl.spoj.com/problems/AL_06_07

Skrócony opis problemu:

Dla podanej funkcji kwadratowej $f(x) = ax^2+bx+c$ oraz przedziału argumentów $\left<A;B\right>$ podaj ile jest wartości całkowitych funkcji w tym przedziale.

Rozwiązanie:

Wzory na współczynniki z zadania to:

$$a = \frac{l}{4} \\ b = -3l \\ c = l \cdot (n+4)$$

Aby zliczyć wartości będące liczbami całkowitymi musimy wiedzieć, w jakim są one przedziale. Wyliczamy zatem minimum i maksimum lokalne naszego trójmianu kwadratowego w danym przedziale. Wystarczy sprawdzić 3 punkty: krańce przedziału ($A$ i $B$) oraz wierzchołek paraboli (jeśli należy do sprawdzanego przez nas przedziału). Obliczamy zatem $f(A)$, $f(B)$ oraz $f(x_w) = y_w = \frac{-\Delta}{4a}$ i wybieramy z tych wartości najmniejszą i największą.

Mając niż zbiór wartości funkcji w interesującym nas przedziale musimy jeszcze tylko wyznaczyć, ile znajduje się w nim liczb całkowitych. Aby to osiągnąć wystarczy zaokrąglić minimum w górę, a maksimum w dół (bo ułamki i tak nas nie interesują, więc zawężamy przedział usuwając ułamki z krańców). Może się zdarzyć (np. dla $min = 4.5$, $max = 4.6$), że po zaokrągleniach min będzie większy od maxa. Wypisujemy wtedy 0. W przeciwnym wypadku wypisujemy $max-min+1$.

Jak widzimy, powyższy wzór działa także, gdy po zaokrągleniu $min > max$. Chciałem tylko zwrócić uwagę, żeby być czujnym i próbować przewidzieć wszystkie przypadki.

Złożoność dla każdego zapytania o przedział $\left<A;B\right>$ ma złożoność $O(1)$. W zadaniu mamy jednak $q$ zapytań, więc końcowa złożoność to: $O(q)$.

Ostateczny algorytm:

int main()
{
    double l, a, b, c, min, max;
    int x, y, n, q;
    
    get(n, l, q);
    a = l/4; b = -3*l; c = (4+n)*l;
    while(q--)
    {
        get(x, y);
        min = a*x*x+b*x+c; max = a*y*y+b*y+c;
        if(min > max)
            l = min, min = max, max = l;
        if(-b/(2*a) >= x && -b/(2*a) <= y)
        {
            l = (-b*b+4*a*c)/(4*a);
            if(l < min)min = l;
            if(l > max)max = l;
        }
        print(floor(max)-ceil(min)+1);
    }
}