Długi input w pythonie

Question

Cześć, potrzebuje pomocy z zadaniem. Sam algorytm działa mi bezbłędnie, niestety jeden z testów zakłada na wejściu liczbę n<=9*10^999999. Python nie obsługuje konwersji liczby string na int dla tak dużych wartości. Jak inaczej mogę to przekonwertować na int niż poprzez int(input())?

Comments

Poszukaj biblioteki do dużych liczb, są takie które powinny to obsłużyć, chociaż ~milion cyfr to sporo :)

Co chcesz zrobić z tymi liczbami, jakie operacje?

Bo jeśli chcesz np. mnożyć to możesz operować na stringach bez konwersji - zastosuj Algorytm Karatsuba.

Dodawanie i odejmowanie też nie jest trudne.

Dzielenie może trochę kłopotów przysporzyć.

---

Bibliotek żadnych nie mogę niestety używać. O stringach myślałem jako tych mniej optymalnych, poczytam o tym algorytmie szczerze nigdy o nim nie słyszałem.

---

Musisz sam opracować własny algorytm dodawania, odejmowania, a do mnożenia polecam algorytm Karatsuba. Wtedy możesz działać na stringach.

---

Poszukaj biblioteki do dużych liczb, są takie które powinny to obsłużyć, chociaż ~milion cyfr to sporo :)

Python ma wbudowaną obsługę liczb całkowitych dowolnego rozmiaru (i rzeczywistych z `decimal`).

 a do mnożenia polecam algorytm Karatsuba

Karatsuba też już wewnętrznie używa do mnożenia.

No i co najważniejsze:

Python nie obsługuje konwersji liczby string na int dla tak dużych wartości

...u mnie działa bez problemu?

Mam plik z liczbą z 999999 cyframi, wczytuję go (zarówno z read() na pliku jak i input() na strumieniu) i int(tekst) działa - tylko trwa z 2-3s.

Możesz pokazać, co się u Ciebie dzieje?

---

Sądziłem że jest limit co do liczby cyfr.

---

@adrian17, po wklejeniu inputa otrzymuje:
Traceback (most recent call last):
  File "C:\Users\malec\Pulpit\Projekty\Olimpiada Informatyczna\2024\ZAM\zam.py", line 16, in <module>
    n = int(input())
        ^^^^^^^^^^^^
ValueError: Exceeds the limit (4300 digits) for integer string conversion: value has 1000000 digits; use sys.set_int_max_str_digits() to increase the limit

niestety nie mogę korzystać z biblioteki sys ani innych. Jednak lokalnie po zmianie limitu algorytm działa zwracając poprawny wynik, niestety przekracza limit czasu (3 sekundy) działając około minute.

---

To może musisz przemyśleć zadanie, bo z limitu czasu wynika że w ogóle nie powinieneś robić tego co próbujesz robić.