View source for 3401 - Spp

După o zi plină, trei băieți se joacă cu numere. În fiecare seară, unul dintre ei alege un număr <code>x</code>, iar altul un număr <code>y</code> mai mare sau egal cu <code>x</code>. Al treilea propune ceva mai interesant. Astfel, el alege să le spună aproape instantaneu suma pătratelor perfecte de la <code>x</code> și <code>y</code>. Voi trebuie să rezolvați ceva asemănător, doar că știți numai ce zice primul și ultimul băiat. Pentru a-i verifica dacă greșesc la calcule, în schimb, trebuie să găsiți numărul pe care l-ar putea spune al doilea.

Formal, pentru două numere <code>x</code> și <code>y</code> se definește <code>SPP(x,y) = x2</code> <code>+ (x+1)2</code> <code>+...+ y2</code> (suma pătratelor perfecte de la <code>x</code> la <code>y</code>).

Se dau <code>Q</code> întrebări de tipul <code>x p</code> și se cere cel mai mic <code>y</code> mai mare sau egal ca <code>x</code> pentru care <code>SPP(x,y) ≥ p2</code>.

= Cerința =
Să se calculeze pentru fiecare întrebare <code>p</code> minimum, pentru care relația este satisfăcută.

= Date de intrare =
Fișierul de intrare <code>input.txt</code> conține pe prima linie un număr natural <code>Q</code>. Pe liniile <code>2</code>, <code>3</code>, …, <code>Q+1</code> se află câte o pereche <code>x p</code> care satisface restricțiile.

= Date de ieșire =
Fișierul de ieșire <code>output.txt</code> va conține răspunsul la fiecare întrebare.

= Restricții și precizări =

* <code>Q ≤ 100.000</code>

== Exemplul 1 ==
input.txt:

2

1 5

10 19

output.txt:

4

12

Explicație:

1^2 + 2^2 + 3^2 + 4^2 = 30 >= 5^2

10^2 + 11^2 + 12^2  = 365 >= 19^2

== Exemplul 2 ==
input.txt:

9999999999999

1 5

10 19

Output:

Error: Q is not within the valid range (1 <= Q <= 100,000)

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
import sys

def verify_constraints(Q):
    if not (1 <= Q <= 100000):
        sys.exit("Error: Q is not within the valid range (1 <= Q <= 100,000)")

with open("input.txt", "r") as f, open("output.txt", "w") as g:
    Q = int(f.readline())
    verify_constraints(Q)
    queries = [tuple(map(int, f.readline().split())) for _ in range(Q)]

    for x, p in queries:
        def binarys(x, st, dr, pp):
            sol = 0
            px = (1 * x * (x + 1) * (2 * x + 1)) // 6
            while st <= dr:
                mid = (st + dr) // 2
                py = (1 * mid * (mid + 1) * (2 * mid + 1)) // 6

                if py - px >= pp:
                    sol = mid
                    dr = mid - 1
                else:
                    st = mid + 1
            return sol

        y = binarys(x - 1, x, x + 1500000, 1 * p * p)
        g.write(str(y) + '\n')

</syntaxhighlight>