1240 - Ab3

Cerința

Să se determine pentru n numere a valoarea b maximă astfel încât b³ + b ≤ a.

Date de intrare

Datele de intrare conțin pe prima linie numărul n, iar pe următoarele n linii câte un număr a.

Date de ieșire

datele de ieșire vor 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 ≤ 10¹⁸

Exemple

Intrare

5
1 
9 
36
27
89

Ieșire

0
1
3
2
4

Explicație

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

Rezolvare

<syntaxhighlight lang="python"> def validate_input(n, values):

   if n < 1 or n > 100000:
       return False
   for value in values:
       if value < 0 or value > 10**18:
           return False
   return True

def solve_problem(n, values):

   st = 1 << 19
   results = []
   for i in range(n):
       a = values[i]
       b = 0
       for step in range(st, 0, -1):
           if (b + step) * (b + step) * (b + step) + (b + step) <= a:
               b += step
       results.append(str(b))
   return results

def main():

   n = int(input())
   values = []
   for i in range(n):
       values.append(int(input()))

   if validate_input(n, values):
       results = solve_problem(n, values)
       for result in results:
           print(result)

if __name__ == '__main__':

   main()

</syntaxhighlight>