Sortowanie (Część 2)
Materiały
Dla nauczyciela
Dla ucznia
Zadania
Zadanie 1. Wirgiliusz
Wszystkie dzieci Wirgiliusza postanowiły zamieszkać w Bajtomiu w pięknych domkach na nowo wybudowanej ulicy Bajtockiej. Razem z nimi zamieszka również Wirgiliusz. Ponieważ ojciec zamierza często odwiedzać wszystkie swoje dzieci, chciałby znaleźć taki dom jednego z nich, aby mieć możliwie blisko nich wszystkich. Ojciec Wirgiliusz chce zminimalizować sumaryczną odległość do wszystkich swoich dzieci i poprosił Ciebie, abyś napisał stosowny program.
Wejście
Pierwszy wiersz zawiera liczbę całkowitą \(r\) (\(1 \leq r \leq 10^6\) ) oznaczającą liczbę dzieci Wirgiliusza. Drugi wiersz zawiera \(r\) całkowitych numerów domów \(s_1 , s_2 , \dots, s_i , \dots, s_r\) , w których one mieszkają (\(1 \leq s_i \leq 1 000 000 000\)). Zauważ, że różne dzieci mogą mieszkać w tych samych domach.
Wyjście
W pierwszym i jedynym wierszu wyjścia Twój program musi wypisać minimalną sumę odległości optymalnie położonego domu Wirgiliusza od wszystkich dzieci. Odległość między dwoma domami o numerach \(s_i\) i \(s_j\) wynosi \(d_{i,j}\) = \(|s_i – s_j |\).
Przykład
| Wejście | Wyjście |
|---|---|
| 3 2 4 6 |
4 |
Wskazówka
Wybierz miejsce leżące najbliżej mediany wartości.
Zadanie 2. Układanie kart
Mały Bitek dostał od rodziców talię kart. Ze zdziwieniem jednak zauważył, że karty zamiast tradycyjnych oznaczeń typu król pik są oznaczone kolejnymi liczbami całkowitymi. Szybko jednak bardzo mu się to spodobało. Bitek grając w karty zawsze ustawia je od najmniejszej do największej. Stosuje przy tym popularną metodę:
- zakłada, że pierwsza karta jest już na swoim miejscu,
- każdą kolejną kartę przesuwa w lewo tak długo, aż znajdzie się ona na właściwej pozycji.
Bitek zauważył, że w trakcie porządkowania \(i\)-ta karta mija zawsze \(k_i\) innych kart. Bardzo go to zaintrygowało i teraz chciałby wiedzieć, ile łącznie takich „minięć” zostanie wykonanych dla całej potasowanej talii.
Wejście
W pierwszym wierszu znajduje się jedna liczba całkowita \(n\) – liczba kart (\(1 \leq n \leq 10^6\) ). W kolejnej linii znajduje się \(n\) różnych liczb całkowitych \(x_i\) – wartości kolejnych kart (\(1 \leq x_i \leq n\)).
Wyjście
Jedna liczba całkowita oznaczająca łączną liczbę miniętych w trakcie układania kart.
Przykład
| Wejście | Wyjście |
|---|---|
| 4 4 2 3 1 |
5 |
Wskazówka
Możesz zliczać minięcia podczas wywołania algorytmu sortowania przez scalanie.
Zadanie 3. Równoważne teksty
Dwa teksty a oraz b nazwiemy równoważnymi, jeżeli spełniają jeden z dwóch warunków:
- są identyczne,
- jeżeli tekst \(a\) podzielimy na dwie równej długości części \(a_1\) i \(a_2\) , a tekst \(b\) podzielimy podobnie na teksty \(b_1\) i \(b_2\) , to jeden z warunków będzie poprawny:
- \(a_1\) i \(b_1\) oraz \(a_2\) i \(b_2\) będą równoważne
- \(a_1\) i \(b_2\) oraz \(a_2\) i \(b_1\) będą równoważne.
Sprawdź, czy podane dwa teksty są równoważne według powyższej definicji!
Wejście
W dwóch wierszach wejścia znajduje się po jednym tekście. Teksty mają długość od \(1\) do \(2 \cdot 10^5\) znaków i składają się wyłącznie z małych liter alfabetu łacińskiego. Długości tekstów są równe.
Wyjście
Wypisz jedno słowo: TAK lub NIE, odpowiedź na pytanie, czy podane teksty są równoważne.
Przykład
| Wejście | Wyjście |
|---|---|
| abcd cdba |
TAK |
| abcd acbd |
NIE |
Wskazówka
Posortuj połówki słów i porównaj je ze sobą.