2463 - Inequation

Cerința

Această problemă nu are o descriere plicticoasă, menită să vă încurce.Trebuie doar să aflați cel mai mare număr natural n, astfel încât b^0+b^1+...+b^n≤y, unde b și y sunt valori cunoscute.

Date de intrare

Fișierul de intrare inequationin.txt va conține pe prima linie numărul t, reprezentând numărul de teste ale problemei.Apoi urmează 3*t rânduri, pentru fiecare test fiind precizată baza b, numărul de cifre ale lui y, precum și cifrele numărului y, aflate fiecare pe un rând separat.

Date de ieșire

Fișierul de ieșire inequationout.txt va conține pe linia i numărul maxim de termeni pentru care se respectă condiția pentru testul cu numărul de ordine t.

Restricții și precizări

• 1 ⩽ b ⩽ 100
• numărul de cifre ale lui y ⩽ 25.000

Exemplul 1

Intrare

inequationin.txt

1

2

2

16

Ieșire

Datele de intrare corespund restricțiilor impuse

inequationout.txt

4

Explicație

2^0+2^1+2^2+2^3=15≤16, deci în total patru termeni.

Exemplul 2

Intrare

inequationin.txt

1

101

2

16

Ieșire

Datele de intrare NU corespund restricțiilor impuse

Rezolvare

#2463 - Inequation

def validare_date(b, y):
    if not (1 <= b <= 100):
        return False
    if not (1 <= len(y) <= 25000):
        return False
    if not all(0 <= int(cifra) <= 9 for cifra in y):
        return False
    return True


def calculeaza_numar_maxim_termeni(b, y):
    suma = 0
    numar_termeni = 0
    i = 0
    while suma + b ** i <= int(y):
        suma += b ** i
        numar_termeni += 1
        i += 1
    return numar_termeni


def main():
    with open("inequationin.txt", "r") as file_input:
        t = int(file_input.readline().strip())
        for _ in range(t):
            b = int(file_input.readline().strip())
            lungime_y = int(file_input.readline().strip())
            y = file_input.readline().strip()

            if validare_date(b, y):
                print("Datele de intrare corespund restricțiilor impuse")

                rezultat = calculeaza_numar_maxim_termeni(b, y)

                with open("inequationout.txt", "w") as file_output:
                    file_output.write(str(rezultat) + "\n")
            else:
                print("Datele de intrare NU corespund restricțiilor impuse")


if __name__ == "__main__":
    main()