Łańcuchy znaków
Dla nauczyciela
Dla ucznia
Zadania
Zadanie 1. Brakująca cyfra
Mamusia ciągle powtarzała Jankowi: ‘Odrabiając pracę domową z matematyki nie pij nad zeszytem mleka!’. Janek oczywiście nie słuchał mamy i mleko nad zeszytem pił. Aż do czasu, kiedy mleko rozlało się na zadanie domowe! Całe szczęście, że rozmyła się tylko jedna cyfra w całej liczbie! Janek pamięta, że każda liczba na kartce była podzielna przez \(9\). Twoim zadaniem jest odnalezienie brakującej cyfry. Jeśli warunek spełnia kilka cyfr, pomóż odnaleźć Jankowi najmniejszą z nich.
Wejście
Pierwszy wiersz wejścia zawiera jedną liczbę \(k\) z pracy domowej (\(1 \leq k \leq 10^{1000}\)). Zagubiona cyfra zastąpiona jest znakiem X. Możesz przyjąć, że dla \(40%\) testów zachodzi warunek \(k \leq 10^{18}\).
Wyjście
Na wyjściu wypisz brakującą cyfrę.
Przykład
| Wejście | Wyjście |
|---|---|
| 23X54 | 4 |
Wskazówka
Przypomnij sobie zasadę podzielności przez \(9\).
Zadanie 2. Ciąg monotoniczny
Ciąg liczbowy nazywamy monotonicznym jeżeli jest rosnący, albo malejący, albo stały. W naszym zadaniu dany jest ciąg liter. Jakie litery należy w nim zmienić, aby nasz ciąg był stały, zastępując przy tym jak najmniej znaków? Jeżeli jest kilka takich znaków, które można pozostawić, nie zmieniaj alfabetycznie największej z nich. Możesz założyć, że zawsze będzie co najmniej jedna litera do zmiany.
Wejście
W pierwszej linii wejścia znajduje się ciąg co najmniej dwóch liter (wyłącznie małe litery alfabetu łacińskiego) nie dłuższy niż \(10^6\) elementów.
Wyjście
Na wyjściu w pierwszym wierszu wypisz alfabetycznie wszystkie litery do zmiany.
Przykład
| Wejście | Wyjście |
|---|---|
| kajak | aaj |
Wyjaśnienie: Należy pozostawić litery ‘k’.
Wskazówka
Zlicz wystąpienia liter w słowie.
Zadanie 3. System 36
Bitek sprawdza przydatność obliczeń w różnych systemach obliczeń. Stwierdził, że korzystając z cyfr i dużych liter alfabetu łacińskiego może korzystać nawet z systemu trzydziestoszóstkowego! Próbuje teraz napisać program, który szybko przeliczałby wartości pomiędzy dowolnymi systemami liczbowymi.
Wejście
Pierwszy wiersz zawiera trzy liczby: \(X\), \(Y\) i \(Z\), gdzie \(X\) jest liczbą zapisaną w systemie o podstawie \(Y\) (wartość \(X\) nie przekracza \(10^{15}\) w systemie dziesiętnym). \(Z\) jest podstawą systemu, na który należy zamienić liczbę \(X\) (\(1 < Y, Z < 37\)).
Wyjście
Jedna liczba całkowita - zapis \(X\) w systemie o podstawie \(Z\).
Przykład
| Wejście | Wyjście |
|---|---|
| 37826876 10 36 | MIREK |
Wskazówka
Skorzystaj ze schematu Hornera.
Zadanie 4. James i potęgi dwójki
To był już prawie koniec misji. James Blond rozejrzał się uważnie po pokoju. Pomiędzy porozrzucanymi kartkami znajdowała się TA JEDNA, poszukiwana przez wszystkich. „Jak mogli jej nie zauważyć?”- zapytał sam siebie. Schylił się i wszystko zrozumiał. Na przedartej stronie widać było krótkie ciągi liczb. Ich końcowe cyfry musiały znajdować się na brakującej większej części. W panice zaczął przegarniać papiery. „Nie ma! Nie ma!” – krzyczał do siebie bezgłośnie. Usiadł bezsilnie wpatrując się ciągi znaków. I wtedy... przypomniał sobie ostatnie słowa Profesora: „Tylko potęgi dwójki!”. A więc o to mu chodziło! Każda z liczb to potęga dwójki! Wystarczy znaleźć najmniejszą potęgę dwójki, której początkowe cyfry widział na kartce! James wyjął swój smartphone, włączył aplikację kalkulatora w widoku programisty i... Nie mógł uwierzyć! Android się zawiesił! Czy coś mu jeszcze może pomóc?
Napisz program, który dla zadanej dodatniej liczby całkowitej \(n\) wyznaczy najmniejszy wykładnik \(X\) taki, że pierwsze cyfry liczby \(2^X\) zgadzają się z zadaną liczbą. Pamiętaj, że oderwano większą część kartki, więc na pewno brakuje ponad połowy cyfr.
Wejście
W pierwszym wierszu wejścia znajduje się jedna liczba całkowita bez znaku \(n\) (\(1 \leq n \leq 10^{50}\)).
Wyjście
Dla podanej n wyznacz wykładnik \(X\) taki, że pierwsze cyfry liczby \(2^X\) zgadzają się z zadaną liczbą. Możesz założyć, że wynik zawsze będzie istniał i \(2^X ≤ 10^{100}\). Możesz założyć, że dla \(40%\) testów zachodzi warunek \(2^X < 10^{18}\).
Przykład
| Wejście | Wyjście |
|---|---|
| 1 | 7 |
| 5 | 9 |
| 16 | 14 |
Wskazówka
Rozwiązanie zadania wymaga zaimplementowania własnej arytmetyki dużych liczb.