Informatyczny Kalendarz Adwentowy

Seniorzy 2020

Lista zadań

Zadanie z dnia 2020-11-29

Elfy wykorzystują w swojej pracy specjalne karty zamówień prezentów, z których każde jest identyfikowane przez maksymalnie $9$-cyfrową liczbę. Do tej pory do zapisywania identyfikatorów zamówień wykorzystywano liczby dziesiętne (zbudowane z cyfr $0, 1, \dots, 9$), jednak ze względu na rosnącą liczbę grzecznych dzieci, Gwiazdor zdecydował, że od bieżącego roku zamówienia będą identyfikowane przez liczby dwunastkowe (zbudowane z cyfr $0, 1, \dots, 9, \text{A}, \text{B}$). O ile zwiększyła się liczba zamówień, które można dzięki temu zidentyfikować?

Najedź kursorem na poniższe pole, żeby zobaczyć odpowiedź do zadania.

4159780352

Najedź kursorem na poniższe pole, żeby zobaczyć wyjaśnienie do odpowiedzi.

Mając do dyspozycji $9$ cyfr, możemy w systemie dwunastkowym zapisać maksymalnie $12^9$ różnych wartości, a w systemie dziesiętnym $10^9$. Różnica wynosi więc $4159780352$.

Zadanie z dnia 2020-11-30

Na budynku siedziby Gwiazdora znajduje się binarny licznik dzieci, które zostały obdarowane prezentami. Składa się on z $32$ metalowych tabliczek powieszonych jedna obok drugiej, z których każda ma po jednej stronie namalowaną jedynkę, a po drugiej zero. Na początku grudnia ten analogowy licznik prezentuje $32$ zera. Za każdym razem, gdy jakieś dziecko otrzyma prezent, wartość prezentowaną na liczniku należy zwiększyć o $1$. W tym celu specjalnie wyznaczony elf obraca niektóre tabliczki. Na przykład, gdyby wartość licznika była równa

00000000000000000000100011011011

to jej zwiększenie o $1$ do wartości

00000000000000000000100011011100

pociąga za sobą konieczność obrócenia trzech ostatnich tabliczek.

Ile razy elf będzie musiał obrócić piątą od prawej tabliczkę, jeśli wiadomo, że prezenty otrzyma $2020202020$ dzieci?

Najedź kursorem na poniższe pole, żeby zobaczyć odpowiedź do zadania.

126262626

Najedź kursorem na poniższe pole, żeby zobaczyć wyjaśnienie do odpowiedzi.

Piąta od prawej tabliczka zostanie obrócona, gry prezent otrzyma $16.$, $32.$, $48.$ itd. dziecko. W związku z tym zostanie ona obrócona $\lfloor 2020202020/16 \rfloor = 126262626$ razy.

Zadanie z dnia 2020-12-01

W pliku punkty.in znajdują się współrzędne kartezjańskie $2500$ punktów. W każdym wierszu znajduje się opis jednego punktu: odpowiednio jego współrzędna $x$ i $y$, obie będące liczbami całkowitymi z przedziału $\langle -200, 200\rangle$, oddzielonymi znakiem tabulatora. Jaka jest współrzędna $x$ punktu, który należałoby wybrać spośród wszystkich opisanych w pliku punkty.in, aby koło o promieniu równym $30$ i o środku w tym punkcie pokrywało jednocześnie największą możliwą liczbę punktów opisanych w pliku?

Uwaga. Niektóre pary współrzędnych mogą się powtarzać. Należy wówczas traktować je jak opisy różnych punktów.

Najedź kursorem na poniższe pole, żeby zobaczyć odpowiedź do zadania.

104

Najedź kursorem na poniższe pole, żeby zobaczyć wyjaśnienie do odpowiedzi.

Najprostsza metoda polega na rozważeniu wszystkich punktów jako potencjalnych środków poszukiwanego koła. Dla każdego takiego przypadku należy zliczyć punkty, które zawierają się w odpowiednim kole o promieniu równym $30$. Jeśli przez $(a_0, a_1)$ oznaczymy środek koła, a przez $(b_0, b_1)$ punkt, który mógłby znajdować się w tym kole, to jest tak wtedy i tylko wtedy, gdy $$(a_0 - b_0)^2 + (a_1 - b_1)^2 \leq 30^2.$$ Poszukiwanym środkiem jest punkt o współrzednych $(104, -15)$. Koło o promieniu $30$ i środku w tym punkcie pokrywa $73$ punkty opisane w pliku.

Zadanie z dnia 2020-12-02

Rozważmy dosyć nietypowy sposób porządkowania dwóch liczb naturalnych, $a$ i $b$. Większą z liczb $a$ i $b$ jest ta, dla której suma cyfr w zapisie dziesiętnym jest większa. Jeśli sumy te są równe, to rozważamy zapis dziewiątkowy. Wówczas większą z liczb $a$ i $b$ jest ta, dla której suma cyfr w zapisie dziewiątkowym jest większa. Jeśli sumy te są równe, to rozważamy zapis ósemkowy. Postępujemy tak aż do do zapisu dwójkowego. Jeśli liczby $a$ i $b$ mają takie same sumy cyfr we wszystkich zapisach, od dziesiętnego do dwójkowego, to są w naszym porządku równe.

Plik porzadek.in zawiera $10000$ liczb naturalnych z przedziału $\langle 1000, 2000000 \rangle$. Gdybyśmy rozważali opisany wyżej porządek, to jaka byłaby największa liczba w tym pliku? Jeśli jest więcej takich liczb, podaj tę, która pojawiła się w pliku jako pierwsza.

Najedź kursorem na poniższe pole, żeby zobaczyć odpowiedź do zadania.

897999

Najedź kursorem na poniższe pole, żeby zobaczyć wyjaśnienie do odpowiedzi.

Niech $s(n, p)$ będzie sumą cyfr w zapisie przy podstawie $p$ liczby $n$. Największa suma cyfr w zapisie dziesiętnym liczb z pliku porzadek.in to $51$. Są przy tym tylko dwie wartości, które osiągają tę sumę: $899799$ oraz $897999$. Poszukiwana liczba musi być więc jedną z nich. Zachodzi $s(897999, 9) = 31$ oraz $s(899799, 9) = 23$, a zatem większą, w naszym rozumieniu, jest liczba $897999$.

Zadanie z dnia 2020-12-03

Jak wiadomo, elfy produkują prezenty dla dzieci z całego świata. Gdy do fabryki wpływa nowe zamówienie na prezent, a któryś elf nie wykonuje w danej chwili żadnego innego prezentu, to może bez zwłoki rozpocząć realizację tego zamówienia. Elf nie może przerwać wykonywania prezentu, który zaczął już produkować. Może jednak rozpocząć produkcję nowego prezentu natychmiast gdy ukończy produkcję poprzedniego, bez dodatkowej przerwy.

Gwiazdorowi zależy na tym, aby realizacja każdego zamówienia rozpoczęła się natychmiast, gdy ono wpłynie, dlatego poprosił Cię o pomoc. W pliku zamowienia.in znajduje się $10000$ liczb naturalnych, reprezentujących chwile, w których wpłyną zamówienia na prezenty. Ile co najmniej elfów musi zatrudnić Gwiazdor, aby każde wpływające zamówienie mogło być natychmiast zrealizowane? Przyjmij, że wykonanie jednego prezentu zajmuje dokładnie jedną jednostkę czasu.

Najedź kursorem na poniższe pole, żeby zobaczyć odpowiedź do zadania.

37

Najedź kursorem na poniższe pole, żeby zobaczyć wyjaśnienie do odpowiedzi.

Skoro wykonanie prezentu zajmuje dokładnie jedną jednostkę czasu, to trzeba znaleźć chwilę, w której wpłynie najwięcej zamówień. Gwiazdor powinien zatrudnić przynajmniej tyle elfów, ile będzie wówczas prezentów do wykonania. Najwięcej zamówień, $37$, wpłynie w chwili $487$.

Zadanie z dnia 2020-12-04

Hipoteza Goldbacha mówi, że każda liczba parzysta większa od $2$ da się przedstawić w postaci sumy dwóch liczb pierwszych. Chociaż jest to jedynie hipoteza, wiemy, że jest prawdziwa dla liczb parzystych mniejszych niż $4\cdot 10^{17}$.

Ile liczb nieparzystych z przedziału $\langle 5, 20202021\rangle$ można przedstawić w postaci sumy trzech liczb pierwszych?

Najedź kursorem na poniższe pole, żeby zobaczyć odpowiedź do zadania.

10101008

Najedź kursorem na poniższe pole, żeby zobaczyć wyjaśnienie do odpowiedzi.

Zauważmy, że liczby $5$ nie da się zapisać w postaci sumy trzech liczb pierwszych. Każdą liczbę nieparzystą większą lub równą $7$ da się zapisać w postaci $3 + a$ dla $a$ będącego liczbą parzystą większą od $2$. Korzystając z hipotezy Goldbacha wnioskujemy, że każdą liczbę nieparzystą większą od $5$ można zapisać w postaci sumy trzech liczb pierwszych. Takich liczb w przedziale $\langle 5, 20202021\rangle$ jest więc $$\frac{20202021 - 5}{2} = 10101008.$$

Zadanie z dnia 2020-12-05

Z pewną maszyną można zagrać w następującą grę. Maszyna losuje i zapamiętuje liczbę naturalną z przedziału $\langle 1, 2020\rangle$, a celem gry jest odgadnięcie tej liczby. Każda próba kosztuje $2$ złote. Gdy uczestnik zgadnie wylosowaną liczbę, natychmiast otrzyma nagrodę w wysokości $x$ złotych i gra zakończy się. Gdy uczestnik zaproponuje zbyt dużą liczbę, maszyna zwróci komunikat ,,mniej''. Podobnie, gdy zaproponowana liczba będzie zbyt mała, maszyna zwróci komunikat ,,więcej''. Wiedzę tę można wykorzystać przy kolejnej próbie odgadnięcia wylosowanej liczby.

Jaka jest najmniejsza — wyrażona w pełnych złotych — kwota wygranej $x$, dla której istnieje strategia gwarantująca zysk z każdej rozegranej gry? Gracz osiąga zysk z gry, gdy kwota wygranej przekracza łączny koszt podjętych prób.

Najedź kursorem na poniższe pole, żeby zobaczyć odpowiedź do zadania.

23

Najedź kursorem na poniższe pole, żeby zobaczyć wyjaśnienie do odpowiedzi.

Stosując algorytm wyszukiwania binarnego, jesteśmy w stanie zawsze odgadnąć wylosowaną liczbę w maksymalnie $\lfloor \log_2 2020 \rfloor + 1 = 11$ próbach. Skoro każda próba kosztuje $2$ złote, to niezależnie od tego, jaką liczbę wylosuje maszyna, nigdy nie wydamy więcej niż $22$ złote, aby ją odgadnąć. A zatem najmniejsza kwota wygranej gwarantująca każdorazowy zysk przy wykorzystaniu wyszukiwania binarnego to $22,01$ złotego. Najmniejsza wyrażona w pełnych złotych kwota to zaś $23$ złote.

Zadanie z dnia 2020-12-06

Elfy dysponują jedną maszyną produkcyjną, na której realizują wszystkie swoje zlecenia na wykonanie prezentów. Każdego dnia, przed rozpoczęciem pracy maszyny, określana jest lista prezentów, które należy wykonać tego dnia. Oznaczmy je przez $Z_1, Z_2, \dots, Z_n$. Każdy prezent $Z_i$ opisany jest czasem $t_i$ (w minutach), jaki maszyna poświęci na jego produkcję i dodatnim priorytetem $w_i$, który określa, jak ważne jest szybkie wykonanie tego prezentu. Przyjmujemy, że w czas produkcji prezentu wliczono czas potrzebny na przygotowanie maszyny i że maszyna może produkować tylko jeden prezent na raz. Prezenty są więc produkowane jeden po drugim, bez przerw, a dla każdego prezentu $Z_i$ można jednoznacznie określić czas $c_i$ (w minutach), który upłynie od rozpoczęcia pracy maszyny do ukończenia prezentu $Z_i$.

Gdy kolejność produkcji prezentów zostanie ustalona, jakość planu można ocenić obliczając ważony czas oczekiwania na realizację prezentów, tzn. $$c_1w_1 + c_2w_2 + \dots + c_nw_n.$$

Przykład: Rozważmy listę złożoną jedynie z dwóch prezentów, $Z_1$ i $Z_2$. Niech $t_1 = 5$, $w_1 = 2$ i niech $t_2 = 3$, $w_2 = 6$. Jeśli najpierw wyprodukujemy prezent $Z_1$, a potem $Z_2$, to wówczas $$c_1w_1 + c_2w_2 = 5\cdot 2 + (5 + 3)\cdot 6 = 10 + 48 = 58.$$ Jeśli natomiast zdecydujemy się najpierw wyprodukować prezent $Z_2$, a potem $Z_1$, to okaże się, że $$c_1w_1 + c_2w_2 = (3 + 5)\cdot 2 + 3\cdot 6 = 16 + 18 = 34.$$

W pliku prezenty.in znajduje się opis $100$ prezentów, które należy dziś wykonać. W każdym wierszu znajdują się dwie liczby naturalne, odpowiednio czas potrzebny na wyprodukowanie prezentu (w minutach) i jego priorytet, oddzielone znakiem odstępu. Jaki jest najmniejszy możliwy do osiągnięcia ważony czas oczekiwania na realizację prezentów z tej listy?

Najedź kursorem na poniższe pole, żeby zobaczyć odpowiedź do zadania.

5570461

Najedź kursorem na poniższe pole, żeby zobaczyć wyjaśnienie do odpowiedzi.

Niech dane będą dwa prezenty, $Z_i$ i $Z_j$, wykonywane jeden po drugim. Jeśli $t_i/w_i < t_j/w_j$, to prezent $Z_i$ należy wykonać przed prezentem $Z_j$. Aby to uzasadnić, załóżmy, że zachodzi $t_i/w_i < t_j/w_j$, a prezent $Z_j$ wykonano przed prezentem $Z_i$. Wtedy $$c_jw_j + c_iw_i = (C + t_j)\cdot w_j + (C + t_j + t_i)\cdot w_i$$ dla jednoznacznie określonej wartości $C$, równej łącznemu czasowi wykonywania wszystkich prezentów zrealizowanych przed prezentami $Z_i$ i $Z_j$. Jeśli zamienimy ze sobą miejscami prezenty $Z_i$ i $Z_j$, to $$c_jw_j + c_iw_i = (C + t_i + t_j)\cdot w_j + (C + t_i)\cdot w_i.$$ Pokażemy teraz, że $$(C + t_i + t_j)\cdot w_j + (C + t_i)\cdot w_i < (C + t_j)\cdot w_j + (C + t_j + t_i)\cdot w_i,$$ a więc że wykonanie prezentu $Z_i$ przed $Z_j$ zmniejszy ważony czas oczekiwania na realizację prezentu. Rzeczywiście, po przekształceniu otrzymujemy $$t_iw_j + t_jw_j + t_iw_i < t_jw_j + t_jw_i + t_iw_i,$$ $$t_iw_j < t_jw_i.$$ Ostatnia nierówność musi zachodzić, ponieważ $t_i/w_i < t_j/w_j$.

Z powyższego wnioskujemy, że prezenty należy produkować w rosnącej kolejności względem stosunku czasu wykonywania do priorytetu.

Zadanie z dnia 2020-12-07

Jeden z elfów poprosił Cię o pomoc w otwarciu sejfu z zamkiem elektronicznym. Otwarcie drzwiczek następuje po wprowadzeniu konkretnego 4-cyfrowego kodu, a otwierający ma aż 5 szans zanim zamek zablokuje się na zawsze. Niestety, elf był bardzo niecierpliwy i wykorzystał już cztery z pięciu prób. Na szczęście elektroniczny zamek poinformował go o tym, ile z cyfr wprowadzonych w każdej z czterech prób było prawidłowych i znajdowało się na odpowiednich pozycjach (X), a ile było prawidłowych, ale umieszczonych w złym miejscu (Y). Poniżej znajdziesz notatki, które sporządził Twój kolega.

1853 XXX
8530 YY
1852 XXY
1253 XXY

Jaki kod otwiera zamek?

Najedź kursorem na poniższe pole, żeby zobaczyć odpowiedź do zadania.

1823

Najedź kursorem na poniższe pole, żeby zobaczyć wyjaśnienie do odpowiedzi.

Skoro trzy cyfry w kodzie $1853$ są na swoich miejscach, to jedna z nich nie może na nim być. Gdyby kod był postaci $185?$, to trzecia próba dałaby w wyniku XXX lub XXXX. Trójka musi być więc na swoim miejscu. Gdyby kod był postaci $1?53$, to ostatnia próba dałaby w wyniku XXX lub XXXX. Ósemka musi być więc na swoim miejscu, z czego wnioskujemy, że kod musi być postaci $?8?3$. Skoro próba $8530$ daje w wyniku YY, a w prawidłowym kodzie występuje i ósemka, i trójka, to w kodzie nie może być ani piątki, ani zera. Oznacza to, że prawidłowy kod jest postaci $18?3$. Z ostatniej próby wnioskujemy już wprost, że w kodzie musi występować cyfra $2$. Ostatecznie, kod to $1823$.

Zadanie z dnia 2020-12-08

W ogólnym szyfrze podstawieniowym kluczem szyfrującym jest permutacja liter alfabetu. Na przykład, jeśli alfabet zdefiniujemy jako zbiór $\{a, b, c, d\}$, a kluczem szyfrującym będzie permutacja $$\begin{pmatrix}a&b&c&d\\b&d&c&a\end{pmatrix},$$ to w czasie generowania szyfrogramu wszystkie wystąpienia litery $a$ w tekście szyfrowanym zostaną zastapione literą $b$, wszystkie wystąpienia litery $b$ zostaną zastąpione literą $d$, wszystkie wystąpienia litery $c$ pozostaną nienaruszone, a wszystkie wystąpienia litery $d$ zostaną zastąpione literą $a$. Umawiamy się, że w czasie szyfrowania tekstu pozostawia się bez zmian wszystkie symbole spoza alfabetu. Tym samym tekst "ab dc - adca" zaszyfrowany permutacją $$\begin{pmatrix}a&b&c&d\\b&d&c&a\end{pmatrix}$$ to "bd ac - bacb".

W pliku szyfrogram.in znajduje się szyfrogram pewnego tekstu napisanego w języku polskim, opartego o zbudowany z wielkich liter alfabet polski (A, Ą, B, C, Ć, D, ..., Z, Ź, Ż). Do wygenerowania szyfrogramu użyto pewnej permutacji tych liter, a plik zakodowano z wykorzystaniem kodowania UTF-8. Odszyfruj oryginalny tekst. W odpowiedzi podaj, ile razy w oryginalnym tekście wystąpiły łącznie litery A, C, F, G, J, L, O, U, W, oraz Z.

Najedź kursorem na poniższe pole, żeby zobaczyć odpowiedź do zadania.

32906

Najedź kursorem na poniższe pole, żeby zobaczyć wyjaśnienie do odpowiedzi.

Do zaszyfrowania użyto permutacji (OŚĄIJFGAHĘÓSXŃWRBCNYPŁETŹKLZDQVUMŻĆ), tzn. litera A została zamieniona na O, litera Ą na Ś, litera B na Ą itd. Aby złamać szyfr, można utworzyć potencjalny klucz bazując na tym, jak często w języku polskim występują poszczególne litery (por. https://sjp.pwn.pl/poradnia/haslo/frekwencja-liter-w-polskich-tekstach;7072.html) w porównaniu z częstością występowania liter w szyfrogramie, a następnie odnaleźć prawidłowy klucz wprowadzając do bazowego klucza niewielkie zmiany, metodą prób i błędów. Ta metoda jest skuteczna, ponieważ szyfrogram jest bardzo długi, a rozkład częstości występowania liter w języku polskim nie jest jednostajny (niektóre litery występują wyraźnie częściej niż inne).

Zadanie z dnia 2020-12-09

W pliku podciag.in znajduje się $10000$ liczb naturalnych mniejszych od miliarda, po jednej liczbie w wierszu. Liczby te tworzą pewien ciąg liczbowy, w którym występuje dokładnie jeden najdłuższy spójny podciąg rosnący (tzn. taki co najmniej dwuelementowy podciąg $a_i, a_{i+1}, \dots, a_j$, że $a_i < a_{i+1} < \dots < a_j$). Jaka liczba rozpoczyna ten podciąg?

Najedź kursorem na poniższe pole, żeby zobaczyć odpowiedź do zadania.

42362791

Najedź kursorem na poniższe pole, żeby zobaczyć wyjaśnienie do odpowiedzi.

Najdłuższy spójny podciąg rosnący rozpoczyna się w wierszu $9993$ i składa się z ośmiu liczb, a więc kończy się wraz z końcem zawartości pliku.

Zadanie z dnia 2020-12-10

Załóżmy, że jedyną dozwoloną operacją arytmetyczną jest operacja mnożenia. Jaka jest najmniejsza możliwa liczba mnożeń, które musimy wykonać, aby poznać wartość wyrażenia $x^{43}$, dla pewnej wartości $x$?

Najedź kursorem na poniższe pole, żeby zobaczyć odpowiedź do zadania.

7

Najedź kursorem na poniższe pole, żeby zobaczyć wyjaśnienie do odpowiedzi.

Stosując algorytm potęgowania binarnego, wynik otrzymamy wykonując $8$ mnożeń ($x\cdot x, x^2\cdot x^2, x^4\cdot x^4, x^8\cdot x^8, x^{16}\cdot x^{16}, x^{32}\cdot x^8\cdot x^2\cdot x$). Można go jednak uzyskać w $7$ mnożeniach, wykonując następującą sekwencję obliczeń: $$x^2 = x\cdot x,$$ $$x^{3} = x^2\cdot x,$$ $$x^{5} = x^3\cdot x^2,$$ $$x^{10} = x^5\cdot x^5,$$ $$x^{20} = x^{10}\cdot x^{10},$$ $$x^{40} = x^{20}\cdot x^{20},$$ $$x^{43} = x^{40}\cdot x^{3}.$$

Zadanie z dnia 2020-12-11

To zadanie jest uogólnieniem zadania z dnia 30 listopada.

Na budynku siedziby Gwiazdora znajduje się binarny licznik dzieci, które zostały obdarowane prezentami. Składa się on z $32$ metalowych tabliczek powieszonych jedna obok drugiej, z których każda ma po jednej stronie namalowaną jedynkę, a po drugiej zero. Na początku grudnia ten analogowy licznik prezentuje $32$ zera. Elfy szybko się zorientowały, że zwiększanie wartości licznika o $1$ za każdym razem, gdy jakieś dziecko otrzyma prezent, nie jest zbyt wydajne. Zdecydowały więc, że licznik będzie aktualizowany co godzinę. Wówczas wartość prezentowaną na liczniku należy zwiększyć o liczbę dzieci, które otrzymały prezenty w ciągu minionej godziny. W tym celu specjalnie wyznaczony elf obraca niektóre tabliczki. Na przykład, gdyby wartość licznika była równa

00000000000000000000100011011011

to jej zwiększenie o $14$ do wartości

00000000000000000000100011101001

pociąga za sobą konieczność obrócenia tabliczki drugiej, piątej i szóstej od końca.

W pliku licznik.in znajduje się $288$ liczb całkowitych dodatnich, które reprezentują liczby dzieci obdarowanych prezentami w ciągu $288$ godzin pracy Gwiazdora. Ile razy elf będzie musiał wykonać operację obrócenia tabliczki, aktualizując licznik zgodnie z opisanymi wyżej zasadami?

Najedź kursorem na poniższe pole, żeby zobaczyć odpowiedź do zadania.

3645

Najedź kursorem na poniższe pole, żeby zobaczyć wyjaśnienie do odpowiedzi.

Rozważmy pierwsze dwa wiersze pliku licznik.in. Liczba $0$ zapisana binarnie to

00000000000000000000000000000000

a liczba $6506782$ to

00000000011000110100100100011110

Po pierwszej godzinie elf obróci więc $11$ tabliczek. W drugiej godzinie obdarowanych zostanie $12108716$ dzieci, licznik będzie trzeba zwiększyć do wartości $6506782+12108716 = 18615498$, czyli

00000001000111000000110011001010

obracając $15$ tabliczek. Wynik można uzyskując wykonując podobne działania dla każdego wiersza z pliku.

Zadanie z dnia 2020-12-12

Rozważmy algorytm kryptograficzny z kluczem publicznym — RSA. Klucz publiczny służy do szyfrowania wiadomości, a klucz prywatny pozwala odszyfrować zaszyfrowaną wiadomość. W praktyce, przez wiadomość rozumie się sekwencję liczb (o długości w bitach ograniczonej przez algorytm kryptograficzny).

Procedura generowania kluczy na potrzeby algorytmu RSA jest następująca:

  • Wybieramy losowo dwie liczby pierwsze, $p$ i $q$ i obliczamy wartości $n = p\cdot q$ oraz $\varphi(n) = (p-1)\cdot(q-1)$.
  • Wybieramy liczbę całkowitą $e$, taką że $1 < e < \varphi(n)$. Liczba $e$ musi być względnie pierwsza z $\varphi(n)$.
  • Znajdujemy taką liczbę $d$, że $(d\cdot e) \text{ mod $\varphi(n)$} = 1$.

Klucz publiczny jest definiowany jako para $(n, e)$, a klucz prywatny jako para $(n, d)$.

Niech $m$ będzie wiadomością (lub fragmentem wiadomości) do zaszyfrowania. Przyjmujemy, że $m$ jest liczbą naturalną mniejszą niż $n$. Szyfrogram $c$ otrzymujemy, obliczając $$c = m^e \text{ mod $n$}.$$ Aby, mając dany szyfrogram $c$ i klucz prywatny $(n, d)$, odzyskać wiadomość $m$, obliczamy $$m = c^d \text{ mod $n$}.$$ Jeśli wartości $p$ i $q$ są duże, to odzyskanie zaszyfrowanej wiadomości bez znajomości klucza prywatnego jest na tyle obciążające czasowo, że wręcz nieopłacalne.

Rozważ następującą sytuację. Do wygenerowania pary kluczy $(n, e)$ oraz $(n, d)$ wykorzystano niewielkie liczby pierwsze $p$ i $q$ ($1 < p,q < 1000000$). Znany jest klucz publiczny $(n, e)$ oraz szyfrogram $c$: $$(n, e) = (235890082423, 65537)$$ $$c = 97303533918$$ Jaką wiadomość (liczbę) zaszyfrowano?

Najedź kursorem na poniższe pole, żeby zobaczyć odpowiedź do zadania.

1827361233

Najedź kursorem na poniższe pole, żeby zobaczyć wyjaśnienie do odpowiedzi.

Jednym ze sposobów rozwiązania tego zadania jest rozłożenie liczby $n$ na czynniki pierwsze. Znając wartości $p$ i $q$ (odpowiednio $974837$ i $241979$), można wyznaczyć wartość $\varphi(n)$. Z kolei mając daną wartość $\varphi(n) = 235888865608$, można znaleźć wartość $d$ taką, że $(d\cdot 65537) \text{ mod 235888865608} = 1$ (por. https://eduinf.waw.pl/inf/alg/001_search/0009.php). Ta wartość to $d = 235039425257$. Stąd już tylko krok do znalezienia oryginalnej wiadomości. Niestety, podniesienie liczby $97303533918$ do potęgi $235039425257$ jest dosyć czasochłonne. Można tu jednak skorzystać z algorytmu potęgowania binarnego oraz z faktu, że $$(a\cdot b) \text{ mod $c$} = ((a \text{ mod $c$})\cdot(b \text{ mod $c$})) \text{ mod $c$}.$$

Zadanie z dnia 2020-12-13

Niech $1234_{x}$ będzie reprezentacją liczby zapisaną w systemie pozycyjno-wagowym o podstawie równej $x$ ($x$ jest liczbą naturalną oraz $x > 4$). Ile wynosi wartość wyrażenia: $$1234_{5} + 1234_{6} + 1234_{7} + \dots + 1234_{2020}?$$

Najedź kursorem na poniższe pole, żeby zobaczyć odpowiedź do zadania.

4172043415344

Zadanie z dnia 2020-12-14

Funkcję $F(n)$, która zwraca $n$-ty wyraz ciągu Fibonacciego, dla dodatniego $n$, można zdefiniować rekurencyjnie jako: $$F(n) = \begin{cases} 1 &\text{jeżeli } n = 1 \text{ lub } n = 2,\\ F(n-2) + F(n-1) & \mbox{jeżeli } n > 2.\end{cases}$$ Jakie są cztery ostatnie (najmniej znaczące) cyfry w szóstkowym zapisie liczby będącej wartością wyrażenia $F(1234567890)$?

Przykład: Liczba dziesiętna $12345$ zapisana w systemie szóstkowym to $133053_6$. Oznacza to, że cztery ostatnie cyfry w szóstkowym zapisie liczby $12345$ to $3053$.

Najedź kursorem na poniższe pole, żeby zobaczyć odpowiedź do zadania.

5544

Najedź kursorem na poniższe pole, żeby zobaczyć wyjaśnienie do odpowiedzi.

Stosowanie rekurencyjnego algorytmu jest w tym zadaniu zbyt kosztowne czasowo (i pamięciowo). Z kolei zastosowanie iteracyjnego algorytmu poszukiwania $n$-tego wyrazu ciągu Fibonacciego może być kłopotliwe, ponieważ $1234567890$-ty wyraz tego ciągu ma bardzo dużo cyfr. Można go jednak polepszyć, zauważając, że $$(a + b) \text{ mod $c$} = ((a \text{ mod $c$}) + (b \text{ mod $c$})) \text{ mod $c$}.$$ Żeby wyznaczyć cztery ostatnie cyfry w szóstkowym zapisie $1234567890$-tego wyrazu ciągu Fibonacciego, wystarczy pamiętać kolejne wartości tego ciągu modulo $6^4$. Uzyskany wynik ($1288$) należy przedstawić w systemie szóstkowym.

Zadanie z dnia 2020-12-15

To zadanie jest uogólnieniem zadania z dnia 1 grudnia.

W pliku punkty.in znajdują się współrzędne kartezjańskie $2500$ punktów. W każdym wierszu znajduje się opis jednego punktu: odpowiednio jego współrzędna $x$ i $y$, obie będące liczbami całkowitymi z przedziału $\langle -200, 200\rangle$, oddzielonymi znakiem tabulatora. Jaka jest największa liczba punktów opisanych w pliku punkty.in, które można jednocześnie przykryć kołem o promieniu równym $30$? Uwaga. Środek tego koła nie musi być żadnym z opisanych punktów, a jego współrzędne nie muszą być liczbami całkowitymi.

Najedź kursorem na poniższe pole, żeby zobaczyć odpowiedź do zadania.

82

Najedź kursorem na poniższe pole, żeby zobaczyć wyjaśnienie do odpowiedzi.

Z zadania z dnia 1 grudnia wiemy, że istnieje koło pokrywające $73$ punkty, o środku w punkcie $(104, -15)$. Nie wszystkie te punkty są identyczne, więc możemy założyć, że poszukiwane przez nas koło musi pokrywać przynajmniej dwa różne punkty. Można przy tym zauważyć, że możemy ograniczyć się do kół spełniających następujący warunek: na okręgu koła znajdują się przynajmniej dwa różne punkty. Jeśli by tak nie było, to przesuwając nieznacznie optymalne koło moglibyśmy znaleźć takie, które pokrywa tyle samo punktów, ale spełnia ten warunek. To nas prowadzi do następującego rozwiązania.

Dla każdej pary różnych punktów należy wyznaczyć zero, jeden lub dwa środki potencjalnych kół takich, że oba rozważane punkty leżą na ich krawędzi (na okręgu). Jeśli rozważane punkty są oddalone o więcej niż $60$ jednostek (dwa promienie), to nie istnieje żadne takie koło. Jeśli są oddalone o dokładnie $60$ jednostek, to istnieje dokładnie jedno takie koło. W końcu, jeśli są oddalone o mniej niż $60$ jednostek, to istnieją dwa takie koła. Ich środki można wyznaczyć korzystając z aparatu geometrii analitycznej. Niezależnie od wariantu, dla każdego wyznaczonego środka należy postępować podobnie jak w przypadku rozwiązania zadania z dnia 1 grudnia. Ostatecznie okazuje się, że istnieje 6 wyznaczonych tą metodą kół, które pokrywają $82$ punkty. Środek przykładowego z nich ma współrzędne $(100.97373476413985, -16.920908748217357)$.

Gdybyśmy ograniczyli się do współrzędnych całkowitych, to najlepszym wyborem byłoby na przykład koło o środku we współrzędnych $(102, -16)$. Niestety, pokrywa ono jedynie $80$ punktów.

Zadanie z dnia 2020-12-16

W Laponii funkcjonuje nietypowa waluta pieniężna. Otóż jedynymi dostępnymi monetami są te o wartościach $12345$ oraz $1234567$. Rozważmy dwóch mieszkańców Laponii: osobę A oraz osobę B. Osoba A posiada nieograniczoną liczbę monet o wartości $12345$, ale nie posiada żadnej monety o wartości $1234567$. Z kolei osoba B posiada nieograniczoną liczbę monet o wartości $1234567$, ale nie posiada żadnej monety o wartości $12345$. Osoba A planuje kupić od osoby B przedmiot o wartości $1$. W tym celu planuje dostarczyć osobie B określoną liczbę monet o wartości $12345$, aby osoba B mogła jej wydać --- jako resztę --- pewną liczbę monet o wartości $1234567$. Jaka jest najmniejsza liczba monet, jakie powinna przygotować osoba A, aby mogła sfinalizować zakup?

Najedź kursorem na poniższe pole, żeby zobaczyć odpowiedź do zadania.

73704

Najedź kursorem na poniższe pole, żeby zobaczyć wyjaśnienie do odpowiedzi.

Stosując rozszerzony algorytm Euklidesa odkrywamy, że $$1 = 73704\cdot 12345 - 737\cdot 1234567,$$ przy czym współczynniki $73704$ oraz $-737$ są najmniejsze możliwe. Jeśli więc osoba A dostarczy $73704$ monety, to otrzyma $737$ monet reszty.

Zadanie z dnia 2020-12-17

Jedną z metod generowania pseudolosowych liczb naturalnych z przedziału $\langle 0, m)$ jest wykorzystanie liniowych generatorów kongruentnych. Oznaczmy przez $X_0$ tzw. ziarno generatora. Liczby pseudolosowe uzyskujemy opierając się na zależności rekurencyjnej $$X_{n+1} = (aX_n + c) \text{ mod } m$$ dla pewnych wartości $a, c$ oraz ustalonej z góry wartości $m$, przy czym $c < m$.

Przykład: Jeśli $a = 14$, $c = 7$, $m = 13$, a za ziarno przyjmiemy $X_0 = 2$, to kolejno wygenerowane trzy pseudolosowe wartości będą równe $$X_1 = (14\cdot 2 + 7) \text{ mod } 13 = 35 \text{ mod } 13 = 9,$$ $$X_2 = (14\cdot 9 + 7) \text{ mod } 13 = 133 \text{ mod } 13 = 3,$$ $$X_3 = (14\cdot 3 + 7) \text{ mod } 13 = 49 \text{ mod } 13 = 10.$$

Wiadomo, że Janek korzysta z liniowego generatora kongruentnego, aby generować pseudolosowe liczby z przedziału $\langle 0, 928377461)$. Udało Ci się dowiedzieć, że trzy kolejne, wygenerowane przez Janka liczby są równe: $$X_k = 21380413$$ $$X_{k+1} = 32564732$$ $$X_{k+2} = 803330610$$ dla pewnej nieznanej wartości $k$. Jaka będzie kolejna wartość ($X_{k+3}$)?

Najedź kursorem na poniższe pole, żeby zobaczyć odpowiedź do zadania.

476923125

Najedź kursorem na poniższe pole, żeby zobaczyć wyjaśnienie do odpowiedzi.

Zauważmy najpierw, że wartość $m$ jest znana i wynosi $928377461$. Aby znaleźć pozostałe parametry generatora, musimy rozwiązać układ równań $$\begin{cases} X_{k+1} = (aX_k + c) \text{ mod } m\\ X_{k+2} = (aX_{k+1} + c) \text{ mod } m\\ \end{cases}$$ Wpierw zauważmy, że $$X_{k+2} - X_{k+1} \equiv (aX_{k+1} - aX_k) \text{ mod } m = a(X_{k+1} - X_k) \text{ mod } m.$$ Podstawiając znane wartości otrzymujemy równanie $$770765878 = (a\cdot 11184319) \text{ mod } 928377461.$$ Wartość $a = 253193854$ można znaleźć z wykorzystaniem rozszerzonego algorytmu Euklidesa (por. zadanie z szyfrem RSA). Brakuje nam jedynie wartości $c$. Wiemy, że $$X_{k+1} = (aX_k + c) \text{ mod } m,$$ ale to oznacza, że $$32564732 = (253193854\cdot 21380413 + c) \text{ mod } 928377461.$$ Stąd łatwo wywnioskować, że $c = 264378172.$ Ostatecznie $$X_{k+3} = (253193854\cdot 803330610 + 264378172) \text{ mod } 928377461 = 476923125.$$

Zadanie z dnia 2020-12-18

W Laponii, poza walutą, którą prezentowaliśmy w jednym z poprzednich zadań, za nabywane towary i usługi płaci się kartkami pocztowymi przesłanymi przez dzieci z całego świata. Rozróżnia się $5$ rodzajów kartek: kartki zrobione ręcznie (najcenniejsze, niezależnie od rozmiaru), kartki duże, kartki średnie, kartki małe oraz kartki elektroniczne (te są najmniej cenne). Wiadomo, że:

  • 5 kartek elektronicznych jest wartych dokładnie tyle samo co 1 kartka mała,
  • 6 kartek małych jest wartych tyle samo co 5 kartek średnich,
  • 1 kartka duża jest warta dokładnie tyle co zestaw dwóch kartek: małej i średniej,
  • 1 kartka zrobiona ręcznie jest warta tyle, co dwie kartki średnie.

Jaka jest minimalna liczba kartek (papierowych i elektronicznych), które mogą mieć tę samą wartość co $2020$ kartek elektronicznych?

Najedź kursorem na poniższe pole, żeby zobaczyć odpowiedź do zadania.

169

Najedź kursorem na poniższe pole, żeby zobaczyć wyjaśnienie do odpowiedzi.

Przyjmijmy, że kartka elektroniczna jest warta $1$ jednostkę. Z treści zadania wynika, że:

  • kartka mała jest warta $5$ jednostek,
  • kartka średnia jest warta $6$ jednostek,
  • kartka duża jest warta $11$ jednostek,
  • kartka robiona ręcznie jest warta $12$ jednostek.

Aby znaleźć odpowiedź na pytanie z zadania, należy rozwiązać problem wydawania reszty. Podejście zachłanne prowadzi nas do odpowiedzi, że $2020$ jednostek można uzyskać jako sumę $168$ kartek zrobionych ręcznie oraz $4$ kartek elektronicznych. Zastosowanie metody programowania dynamicznego uświadamia nas jednak, że tę samą liczbę jednostek można wyrazić z użyciem $8$ kartek dużych oraz $161$ kartek zrobionych ręcznie. Jako że metoda programowania dynamicznego prowadzi nas do optymalnego rozwiązania, jest to poszukiwana liczba.

Zadanie z dnia 2020-12-19

To zadanie jest uogólnieniem zadania z dnia 3 grudnia.

Jak wiadomo, elfy produkują prezenty dla dzieci z całego świata. Gdy do fabryki wpływa nowe zamówienie na prezent, a któryś elf nie wykonuje w danej chwili żadnego innego prezentu, to może bez zwłoki rozpocząć realizację tego zamówienia. Elf nie może przerwać wykonywania prezentu, który zaczął już produkować. Może jednak rozpocząć produkcję nowego prezentu natychmiast gdy ukończy produkcję poprzedniego, bez dodatkowej przerwy.

Gwiazdorowi zależy na tym, aby realizacja każdego zamówienia rozpoczęła się natychmiast, gdy ono wpłynie, dlatego poprosił Cię o pomoc. W pliku zamowienia.in znajduje się $10000$ liczb naturalnych, reprezentujących chwile, w których wpłyną zamówienia na prezenty. Ile co najmniej elfów musi zatrudnić Gwiazdor, aby każde wpływające zamówienie mogło być natychmiast zrealizowane? Przyjmij, że wykonanie jednego prezentu zajmuje dokładnie trzy jednostki czasu.

Najedź kursorem na poniższe pole, żeby zobaczyć odpowiedź do zadania.

82

Najedź kursorem na poniższe pole, żeby zobaczyć wyjaśnienie do odpowiedzi.

W idealnym harmonogramie, w przedziale czasu $\langle i, i+1 )$ elfy wykonują trzecią tercję każdego zlecenia, które wpłynęło w chwili $i-2$, drugą tercję każdego zlecenia, które wpłynęło w chwili $i-1$ oraz pierwszą tercję każdego zlecenia, które wpłynęło w chwili $i$. Aby to było możliwe, należy znaleźć maksymalną liczbę wykonywanych jednocześnie prezentów. W przedziale $\langle 121, 122 )$ będzie wykonywanych $30$ prezentów rozpoczętych w chwili $119$, $24$ prezenty rozpoczęte w chwili $120$ oraz $28$ prezentów rozpoczętych w chwili $121$.

Zadanie z dnia 2020-12-20

Dana jest kwadratowa plansza o wymiarach $n \times n$. Pole znajdujące się w lewym górnym rogu planszy ma współrzędne $(0, 0)$, a pole znajdujące się w prawym dolnym rogu planszy ma współrzędne $(n-1, n-1)$. Gracz wykonuje sekwencję ruchów pionka, rozpoczynając od pola o współrzędnych $(0, 0)$. Pojedynczy ruch gracza polega na przesunięciu pionka --- w obrębie planszy --- o jedno pole w górę, w dół, w lewo lub w prawo. Z każdym polem planszy jest jednak związana nieujemna liczba całkowita mniejsza niż $10$ --- liczba punktów karnych, które otrzyma gracz, gdy pionek stanie na tym polu. Ruchy kończące się na polach $(0, 0)$ oraz $(n-1, n-1)$ nie zwiększają liczby punktów karnych. Celem gry jest przemieszczenie pionka z pola o współrzędnych $(0, 0)$ na pole o współrzędnych $(n-1, n-1)$, jak najmniejszym kosztem.

Przykład: Rozważmy planszę o rozmiarach $4 \times 4$:

0 6 7 2
4 2 3 2
7 0 1 3
5 4 2 0

Gracz rozpoczyna na polu $(0, 0)$ i wykonuje następującą sekwencję ruchów: w dół ($4$ punkty karne), w prawo ($2$ p.k.), w dół ($0$ p.k.), w prawo ($1$ p.k.), w dół ($2$ p.k.) i w prawo ($0$ p.k.). Tym samym przechodzi od pola $(0, 0)$ do pola $(3, 3)$ otrzymując $9$ punktów karnych.

W pliku plansza.in znajduje się opis planszy o wymiarach $100 \times 100$, tzn. oddzielone znakami odstępu liczby punktów karnych, które otrzyma gracz, gdy stanie na określonych polach. Pierwsza liczba w pierwszym wierszu to liczba punktów karnych związanych z polem $(0, 0)$, a ostatnia liczba w setnym wierszu to liczba punktów karnych związanych z polem $(99, 99)$ (w obu przypadkach jest to $0$). Jaka jest najmniejsza możliwa liczba punktów karnych, jakie może uzyskać gracz przemieszczając pionek z pola $(0, 0)$ na pole $(99, 99)$?

Najedź kursorem na poniższe pole, żeby zobaczyć odpowiedź do zadania.

431

Najedź kursorem na poniższe pole, żeby zobaczyć wyjaśnienie do odpowiedzi.

Aby znaleźć odpowiedź na tak postawione pytanie, można skorzystać z algorytmu Dijkstry poszukiwania najkrótszej ścieżki pomiędzy dwoma wierzchołkami grafu.

Zadanie z dnia 2020-12-21

To zadanie jest uogólnieniem zadania z dnia 4 grudnia.

Hipoteza Goldbacha mówi, że każda liczba parzysta większa od $2$ da się przedstawić w postaci sumy dwóch liczb pierwszych. Chociaż jest to jedynie hipoteza, wiemy, że jest prawdziwa dla liczb parzystych mniejszych niż $4\cdot 10^{17}$. Z zadania z dnia 4 grudnia wiemy, że każdą liczbę nieparzystą z przedziału $\langle 7, 20202021\rangle$ da się zapisać w postaci sumy trzech liczb pierwszych.

Okazuje się, że niektóre liczby można zapisać w postaci sumy uporządkowanych niemalejąco trzech liczb pierwszych na kilka sposobów. Na przykład, $$17 = 2 + 2 + 13 = 3 + 3 + 11 = 3 + 7 + 7 = 5 + 5 + 7.$$

Na ile różnych sposobów można zapisać łącznie, w postaci sumy trzech uporządkowanych niemalejąco liczb pierwszych, wszystkie liczby nieparzyste z przedziału $\langle 7, 2020\rangle$? Dla ułatwienia prezentujemy wszystkich $17$ sposobów, na jakie można zapisać liczby nieparzyste z przedziału $\langle 7, 20\rangle$: $$\begin{array}{rl} 7 & = 2 + 2 + 3\\ 9 & = 2 + 2 + 5 = 3 + 3 + 3\\ 11 & = 2 + 2 + 7 = 3 + 3 + 5\\ 13 & = 3 + 3 + 7 = 3 + 5 + 5\\ 15 & = 2 + 2 + 11 = 3 + 5 + 7 = 5 + 5 + 5\\ 17 & = 2 + 2 + 13 = 3 + 3 + 11 = 3 + 7 + 7 = 5 + 5 + 7\\ 19 & = 3 + 3 + 13 = 3 + 5 + 11 = 5 + 7 + 7\\ \end{array}$$

Najedź kursorem na poniższe pole, żeby zobaczyć odpowiedź do zadania.

1156113

Zadanie z dnia 2020-12-22

Dzielnikami właściwymi liczby naturalnej $n$ nazywamy wszystkie jej dzielniki naturalne z przedziału $\langle 1, n)$ (liczba $n$ nie jest dzielnikiem właściwym liczby $n$). Ile jest liczb naturalnych większych od $1$ i mniejszych lub równych $200000000$ (dwieście milionów) takich, że suma ich dzielników właściwych jest liczbą podzielną przez $8$?

Przykład. Suma dzielników właściwych liczby $20$ wynosi $1+2+4+5+10=22$ i nie jest podzielna przez $8$.

Najedź kursorem na poniższe pole, żeby zobaczyć odpowiedź do zadania.

24542168

Najedź kursorem na poniższe pole, żeby zobaczyć wyjaśnienie do odpowiedzi.

Wyznaczanie poszukiwanej wartości wprost może być bardzo czasochłonne. Znalezienie sumy dzielników właściwych kolejnych liczb wymagałoby sprawdzenia wszystkich potencjalnych dzielników właściwych tych liczb, a przynajmniej rozłożenia jej na czynniki pierwsze. Liczbę sprawdzeń można jednak znacząco zredukować, adaptując algorytm sita Eratostenesa. Dla każdego potencjalnego dzielnika $d$ z przedziału od $2$ do $100000000$ dodajemy wartość $d$ do co $d$-tego elementu wewnątrz tablicy o rozmiarze $200000000$ i redukujemy ją modulo $8$, począwszy od elementu $2d$ (dla liczby $d$ dzielnik $d$ nie jest właściwy). Już dla dzielnika równego $2$ wymaga to połowy czasu potrzebnego na sprawdzenie parzystości każdej liczby z osobna, a liczba wykonanych operacji spada bardzo szybko wraz ze wzrostem badanego dzielnika. Na końcu wystarczy sprawdzić, które sumy zapisane w tablicy spełniają kryterium zadania. Wyznaczenie odpowiedzi do tego zadania z użyciem takiego --- skądinąd niezbyt wydajnego algorytmu --- zajmuje, na przeciętnym komputerze, niecały kwadrans.

Zadanie z dnia 2020-12-23

Zapoznaj się z informacją dostępną na stronie https://obywatel.gov.pl/pl/dokumenty-i-dane-osobowe/czym-jest-numer-pesel. Wyjaśniono na niej, jak tworzone są numery PESEL, którymi posługują się obywatele Polski.

W pliku pesele.in znajduje się $500$ początkowych fragmentów losowo wygenerowanych numerów PESEL. Niestety, brakuje im ostatniej cyfry (cyfry kontrolnej). W ilu przypadkach brakująca cyfra kontrolna jest równa $5$?

Najedź kursorem na poniższe pole, żeby zobaczyć odpowiedź do zadania.

59