Question

#1240 Ab3
// Rezolvare cu cautare binara
Cerința
Se se determine pentru n numere a valoarea b maximă astfel încât b3 + b ≤ a.

Date de intrare
Fișierul de intrare ab3.in conține pe prima linie numărul n, iar pe următoarele n linii câte un număr a.

Date de ieșire
Fișierul de ieșire ab3.out va conține n linii cu câte un număr fiecare, răspunsul la fiecare întrebare.

Restricții și precizări
1 ≤ n ≤ 100.000
0 ≤ a ≤ 1018
Pentru 40% din teste, se garantează că n * b ≤ 106
Atenție la limita de memorie!
Exemple:
ab3.in

5
1
9
36
27
89
ab3.out

0
1
3
2
4
Explicație
13 + 1 = 2
23 + 2 = 10
33 + 3 = 30
43 + 4 = 68
53 + 5 = 130

Answer 1

#include <bits/stdc++.h>

using namespace std ;

ifstream in ("ab3.in") ;

ofstream out ("ab3.out") ;

unsigned long long int Caut(unsigned long long int a, unsigned long long int st, unsigned long long int dr) {

   unsigned long long int mij = (st + dr) / 2 ;

   if (a == 1)

       return 0 ;

   if (mij * mij * mij + mij == a || (mij * mij * mij + mij < a && (mij + 1) * (mij + 1) * (mij + 1) + mij + 1 > a))

       return mij ;

   if (mij * mij * mij + mij < a)

       return Caut(a, mij + 1, dr) ;

   if (mij * mij * mij + mij > a)

       return Caut(a, st, mij - 1) ;

}

int main() {

   unsigned long long int n, a, ans, i ;

   in >> n ;

   for (i = 1 ; i <= n ; ++ i) {

       in >> a ;

       ans = Caut(a, 1, 1000000000) ;

       out << ans << '\n' ;

   }

   return 0 ; ///100p pe pbinfo

}