3401 - Spp

După o zi plină, trei băieți se joacă cu numere. În fiecare seară, unul dintre ei alege un număr x, iar altul un număr y mai mare sau egal cu x. Al treilea propune ceva mai interesant. Astfel, el alege să le spună aproape instantaneu suma pătratelor perfecte de la x și y. 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 x și y se definește SPP(x,y) = x2 + (x+1)2 +...+ y2 (suma pătratelor perfecte de la x la y).

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

Cerința

Să se calculeze pentru fiecare întrebare p minimum, pentru care relația este satisfăcută.

Date de intrare

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

Date de ieșire

Fișierul de ieșire output.txt va conține răspunsul la fiecare întrebare.

Restricții și precizări

• Q ≤ 100.000

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>