Dwuszereg
Limit pamięci: 32 MB
W dwuszeregu stoi żołnierzy.
Trzeba przestawić żołnierzy tak, aby w tym samym szeregu nie było
dwóch żołnierzy tego samego wzrostu - wówczas powiemy, że żołnierze
są ustawieni poprawnie.
Pojedyncza operacja polega na zamianie miejscami dwóch żołnierzy,
którzy są na tej samej pozycji w obu szeregach.
Twoim zadaniem jest policzenie minimalnej liczby zamian, jakie
trzeba wykonać, aby żołnierze byli ustawieni poprawnie.
Przykład:
Na rysunku mamy dwuszereg złożony z żołnierzy.
Strzałkami zaznaczono 3 operacje zamiany, po wykonaniu których
żołnierze są ustawieni poprawnie.
Zadanie
Napisz program, który:
-
wczyta ze standardowego wejścia liczbę i wzrost żołnierzy,
tak jak są ustawieni na początku,
-
wyznaczy minimalną liczbę zamian miejscami (żołnierzy
stojących na tej samej pozycji w obu szeregach) potrzebnych
do poprawnego ustawienia żołnierzy,
-
wypisze wynik na standardowe wyjście.
Wejście
W pierwszym wierszu wejścia znajduje się jedna liczba całkowita
, .
W każdym z dwóch szeregów stoi żołnierzy.
W każdym z dwóch kolejnych wierszy znajduje się po dodatnich
liczb całkowitych pooddzielanych pojedynczymi odstępami.
W drugim wierszu znajdują się liczby ,
; to wzrost -go żołnierza w pierwszym
szeregu.
W trzecim wierszu znajdują się liczby ,
; to wzrost -go żołnierza w drugim
szeregu.
Możesz założyć, że dla danych testowych zawsze możliwe jest
poprawne ustawienie żołnierzy.
Wyjście
W pierwszym i jedynym wierszu wyjścia powinna znaleźć się
jedna nieujemna liczba całkowita -
minimalna liczba zamian jakie należy wykonać, aby żołnierze
byli poprawnie ustawieni.
Przykład
Dla danych wejściowych:
9
2 5 5 2 7 4 7 3 9
1 6 8 4 6 3 9 1 8
poprawną odpowiedzią jest:
3
Autor zadania: Wojciech Rytter.