Rezolvare completă PbInfo #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 spp.in 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 spp.out va conține răspunsul la fiecare întrebare.

Restricții și precizări

  • Q ≤ 100.000
  • 1 ≤ x ≤ 100.000
  • 1 ≤ p ≤ 1.000.000.000
  • Pentru 30% din teste, Q ≤ 100 sau p ≤ 1000

Exemplu

spp.in

2
1 5
10 19

spp.out

4
12

Explicație

12 + 22 + 32 + 42 = 30 ≥ 52.
102 + 112 + 122 = 365 ≥ 192.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema spp:

#include <fstream>
#include <iostream>
using namespace std;
ifstream f("spp.in");
ofstream g("spp.out");
int q, x, p;

int binarys(int x, int st, int dr, long long pp)
{
   int sol  = 0;

   long long px = (1LL * x * (x + 1) * (2 * x + 1)) / 6;
   while (st <= dr) {
       int mid = (st + dr) >> 1;
       long long py = (1LL * mid * (mid + 1) * (2 * mid + 1)) / 6;

       if (py - px >= pp)
           sol = mid, dr = mid - 1;
       else
           st = mid + 1;
   }
   return sol;
}
int main()
{
   int i;
   f >> q;
   for (i = 1; i <= q; i++) {
       f >> x >> p;
       int y = binarys(x - 1, x, x + 1500000, 1LL * p * p);
       g << y << '\n';
   }
   return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email.

Rezolvarea problemei #3401 spp

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #3401 spp de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!