Polish version    English version  
  O olimpiadzie -> Zadania


 Aktualności
 O olimpiadzie
O olimpiadzie
Zadania
I OI 1993/1994
II OI 1994/1995
III OI 1995/1996
IV OI 1996/1997
V OI 1997/1998
VI OI 1998/1999
VII OI 1999/2000
VIII OI 2000/2001
IX OI 2001/2002
X OI 2002/2003
XI OI 2003/2004
XII OI 2004/2005
XIII OI 2005/2006
XIV OI 2006/2007
XV OI 2007/2008
Archiwum zadań
Ankieta OI
 Komitety
 XVIII OI 2010/2011
 Historia OI
 Książeczki OI
 Reprezentacja
 Obozy Olimpiady
 Galeria zdjęć
 Ciekawe odsyłacze
 OIG LiveCD
 IV OIG 2009/2010
 Historia OIG
 SIO
 MAIN

Zadanie: Dwuszereg


W dwuszeregu stoi 2n ż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 18 żołnierzy. Strzałkami zaznaczono 3 operacje zamiany, po wykonaniu których żołnierze są ustawieni poprawnie.

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 n, 1 <= n <= 50 000. W każdym z dwóch szeregów stoi n żołnierzy. W każdym z dwóch kolejnych wierszy znajduje się po n dodatnich liczb całkowitych pooddzielanych pojedynczymi odstępami. W drugim wierszu znajdują się liczby x1, x2,..., xn, 1 <= xi <= 100 000; xi to wzrost i-go żołnierza w pierwszym szeregu. W trzecim wierszu znajdują się liczby y1, y2,..., yn, 1 <= y <= i100 000; yi to wzrost i-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.






Wersja do druku