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

Date de intrare valide

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

if __name__ == '__main__':

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

   if validate_input(n, values):
       print("Date de intrare valide")
       results = solve_problem(n, values)
       for result in results:
           print(result)
   else:
       print("Date de intrare invalide")

</syntaxhighlight>

Explicație cod

Această bucată de cod are două funcții principale:

1. Funcția `validate_input(n, values)`: Această funcție primește doi parametri: un număr întreg `n` și o listă de numere întregi `values`. Funcția verifică dacă `n` este în intervalul [1, 100000] și dacă fiecare valoare din lista `values` este în intervalul [0, 10^18]. Dacă oricare dintre aceste condiții nu este îndeplinită, funcția returnează `False`. În caz contrar, returnează `True`.

2. Funcția `solve_problem(n, values)`: Această funcție primește doi parametri: un număr întreg `n` și o listă de numere întregi `values`. Funcția rezolvă o problemă specifică și returnează o listă de șiruri de caractere. Pentru fiecare valoare `a` din lista `values`, funcția calculează cel mai mare număr întreg `b` pentru care `(b + step) ^ 3 + (b + step) <= a` pentru un anumit interval de `step`. Rezultatul final este o listă de șiruri de caractere, care reprezintă valorile pentru fiecare `b` calculat pentru fiecare valoare `a`.

În funcția principală, se citește întâi numărul `n` și valorile asociate. Dacă valorile sunt valide (verificate prin apelul funcției `validate_input(n, values)`), atunci se afișează "Date de intrare valide". Apoi, se calculează rezultatele prin apelul funcției `solve_problem(n, values)` și se afișează. În caz contrar, se afișează "Date de intrare invalide".