Przejdź do treści

Sortowanie (Część 2)

Materiały

Dla nauczyciela

Materiał dla nauczyciela

Dla ucznia

Sortowanie (MAIN2)

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.

Sprawdź kod na Szkopule

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.

Sprawdź kod na Szkopule

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:

  1. są identyczne,
  2. 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:
  3. \(a_1\) i \(b_1\) oraz \(a_2\) i \(b_2\) będą równoważne
  4. \(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ą.

Sprawdź kod na Szkopule