Powtórzenie i podsumowanie
Materiały
Dla nauczyciela
Zadania
Zadanie 1. Cyfry 2356
Pan Integer znalazł w swoim pokoju pudełko z cyframi. W pudełku jest \(k_2\) cyfr \(2\), \(k_3\) cyfr \(3\), \(k_5\) cyfr \(5\) i \(k_6\) cyfr \(6\). Ulubionymi liczbami całkowitymi pana Integera są \(32\) i \(256\). Postanowił poskładać te liczby z cyfr znajdujących się w pudełku. Każda cyfra może być użyta nie więcej niż jeden raz, tzn. wszystkie liczby powinny zawierać nie więcej niż \(k_2\) cyfr \(2\), \(k_3\) cyfr \(3\) i tak dalej. Chce przy tym, aby suma uzyskanych liczb była jak największa. Cyfry nieużywane nie są doliczane do sumy. Pomóż mu rozwiązać to zadanie!
Wejście
Jedyna linia wejścia zawiera cztery liczby całkowite \(k_2\), \(k_3\), \(k_5\) i \(k_6\) - odpowiednio liczbę cyfr \(2\), \(3\), \(5\) i \(6\) (\(0 \leq k_2, k_3, k_5, k_6 \leq 5·10^6\)).
Wyjście
Wypisz jedną liczbę całkowitą - maksymalną możliwą sumę ulubionych liczb całkowitych pana Integera, które można uzyskać za pomocą cyfr z pudełka.
Przykład
| Wejście | Wyjście |
|---|---|
| 5 1 3 4 | 800 |
| 1 1 1 1 | 256 |
Wskazówka
Znaleźć najmniejszą liczebność cyfr \(2, 5\) i \(6\) (liczba liczb \(256\)). Pozostałe \(2\) i \(3\) to liczba liczb \(32\) (instrukcja jeżeli)
Zadanie 2. Podatki
Pan Longint zamieszkał w Bitolandii. Bardzo lubi tamtejsze widoki. Bitolandia to kraj o bardzo dziwnym systemie podatkowym. Kwota podatku, jaką musi zapłacić pan Longint od umowy opiewającej na \(n\) bitów (miejscowa waluta), jest równa maksymalnemu dzielnikowi właściwemu \(n\). Na przykład dla trzech umów odpowiednio na \(25\), \(6\) i \(2\) bity należy zapłacić \(9\) bitów (\(5\) bitów dla umowy na \(25\) bitów, \(3\) dla \(6\) i \(1\) dla \(2\) bitów). Pan Longint dostrzegł jednak pewną lukę w przepisach. Otóż może on podzielić umowę na kilka różnych (mniejszych) umów i (być może) zapłacić mniejszy podatek opodatkowując każdą umowę oddzielnie! Czy mu się to opłaca? Oblicz, jaki łączny (możliwie najmniejszy) podatek dla podanej kwoty zapłaci pan Longint!
Wejście
Pierwszy i jedyny wiersz wejścia zawiera jedną liczbę \(n\) (\(2 \leq n \leq 10^{10}\)) – kwota, na jaką opiewa umowa.
Wyjście
Wypisz jedną liczbę całkowitą – najniższy podatek, jaki może zapłacić Longint.
Przykład
| Wejście | Wyjście |
|---|---|
| 4 | 2 |
| 27 | 3 |
Wskazówka
Należy wykorzystać hipotezę Goldbacha. Wówczas łatwo zauważyć, że wynik to \(1, 2\) lub \(3\).
Zadanie 3. Pogotowie lotnicze
Bajtazar, król Bitolandii, chce podwyższyć poziom bezpieczeństwa w państwie. Postanowił powołać do życia lotnicze pogotowie ratunkowe. Ma nadzieję, że w ten sposób lekarze będą mogli śmigłowcami szybko dotrzeć do każdego mieszkańca. To na pewno podniesie poczucie bezpieczeństwa ludności. Bitolandia to ciekawy kraj. Całe państwo przecina jedna prosta droga, a wszystkie miasta położone są wzdłuż tej drogi. Król Bajtazar chciałby umieścić bazę lotniczego pogotowia w takim mieście, żeby w razie nagłej potrzeby można było śmigłowcem jak najszybciej dolecieć w dowolne miejsce w kraju. Pomóż mu i wskaż wszystkie miasta, które się do tego nadają!
Wejście
W pierwszym wierszu wejścia znajduje się liczba miast w Bitolandii \(n\) (\(1 \leq n \leq 10^6\)). W drugiej linii wejścia znajduje się \(n-1\) liczb całkowitych \(x_i\) \((1 \leq x_i \leq 10^6)\), gdzie \(x_i\) oznacza odległość między miastami o numerze \(i\) oraz \(i+1\).
Wyjście
W jednej linii wypisz w kolejności rosnącej wszystkie miasta, w których można umieścić bazę lotniczego pogotowia ratunkowego.
Przykład
| Wejście | Wyjście |
|---|---|
| 7 2 3 2 2 4 1 |
4 |
Wskazówka
Sumy prefiksowe. Wskazujemy jedno lub dwa środkowe miasta.
Zadanie 4. Kolorowe żaróweczki
W Bitocji mieszkańcy lubią ozdabiać domy kolorowymi żaróweczkami. Tworzą z nich różne wzory, ale zawsze dbają o to, by żarówki znajdowały się w jednej linii obok siebie. Czasem trzeba dokonywać napraw i wówczas ważne jest, by żarówki w tym samym kolorze znajdowały się blisko siebie. Każdy mieszkaniec chce więc wiedzieć, w jakiej odległości żarówki tego samego koloru są najbliżej oraz najdalej siebie.
Wejście
W pierwszym wierszu wejścia znajduje się liczba \(n\) (\(1 \leq n \leq 10^6\)). W drugiej linii znajduje się \(n\) liczb całkowitych \(k_i\) – kolory żaróweczek (\(1 \leq k_i \leq n\)).
Wyjście
Twój program powinien zapisać dwie liczby całkowite oznaczające odpowiednio najmniejszą odległość pomiędzy dwoma żaróweczkami dowolnego ale tego samego koloru oraz największą możliwą odległość pomiędzy dwoma żaróweczkami dowolnego, ale tego samego koloru. Jeżeli nie jest możliwe wyznaczenie którejś z odległości, wypisz \(0\).
Przykład
| Wejście | Wyjście |
|---|---|
| 7 1 2 3 3 1 1 3 |
1 5 |
Wskazówka
Jeden ze sposobów: Musimy pamiętać pierwsze, bieżące oraz ostatnie wystąpienie każdej z liczb oraz ostatnią minimalną odległość każdej z liczb do poprzedniego wystąpienia.