Długi input w pythonie

pytanie zadane 11 listopada w Python przez MichaelM Bywalec (2,850 p.)

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())?

komentarz 11 listopada przez reaktywny Nałogowiec (44,780 p.)

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

komentarz 11 listopada przez MichaelM Bywalec (2,850 p.)

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.

komentarz 11 listopada przez reaktywny Nałogowiec (44,780 p.)

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

komentarz 11 listopada przez adrian17 Mentor (351,140 p.)

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?

komentarz 11 listopada przez reaktywny Nałogowiec (44,780 p.)

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

komentarz 11 listopada przez MichaelM Bywalec (2,850 p.)

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