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, pe lângă mesajul de validare a datelor introduse ("Date de intrare valide" pentru date valide, "Date de intrare invalide" în caz contrar).

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

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")

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".