Tekstowe

04.11.2010
TrudnośćTrudnośćTrudnośćTrudność

Tekstowe

Limit czasowy: 1000 milisekund
Limit pamięciowy: 16000 kilobajtów


Każdego roku Władek zapraszany jest na obóz naukowy dla licealistów, żeby wygłosić szereg wykładów o programowaniu. Jego ulubionym tematem są oczywiście algorytmy tekstowe. Po każdym wykładzie słuchacze muszą rozwiazać zadanie, które w mniejszym lub większym stopniu nawiązuje do treści wykładu. Tym razem Władek przygotował problem, w którym jego zdaniem tylko najlepsi zawodnicy dopatrzą się "tekstowych". Jego treść jest następująca:

Dana jest prostokątna plansza złożona z pojedynczych kwadratów. Każda kolumna i każdy wiersz ma swój kolor. Na skrajnie prawym, dolnym polu stoi pionek. Gracz może w pojedynczym ruchu przesuwać pionek o jedno pole w lewo, do góry lub po lewej górnej przekątnej. Ruch w lewo i do góry ma zawsze koszt 1. Jeżeli wiersz i kolumna, w których aktualnie stoi pionek mają taki sam kolor, to ruch po przekątnej jest darmowy. W przeciwnym przypadku, tj. kiedy kolory wiersza i kolumny są różne, ruch ma koszt 1. Jaki jest najmniejszy możliwy koszt przesunięcia pionka z pozycji startowej na skrajnie lewe, górne pole?

Wejście:

W pierwszym wierszu znajdują dwie liczby naturalne n, m (1<=n,m<=100000, n*m<=10000000). W następnych n liniach znajdują się opisy kolorów kolejnych wierszy na planszy (od góry do dołu). W i-tej z nich znajduje się pojedyncza liczba naturalna niewiększa od 1000000 będąca kolorem i-tego wiersza. W kolejnych mi liniach znajdują się opisy kolorów kolejnych kolumn na planszy (od lewej do prawej). W i-tej z nich znajdują się dwie liczby di, ki (1<=di,ki<=1000000) oddzielone pojedynczym odstępem. Mówią one, że kolejne di kolumn ma kolor ki. Sumaryczna liczba kolumn wynosi co najwyżej 2*10^9. Szczegóły ilustruje rysunek dla przykładowego wejścia.

Wyjście:

W pierwszej i jedynej linii Twój program powinien wypisać jedną liczbę - najmniejszy możliwy koszt przesunięcia pionka z dolnego prawego pola na pola znajdujące się w górnym lewym rogu planszy.

Przykład:

Dla danych wejściowych:
10 5
1
2
2
1
3
3
2
3
3
3
2 3
2 2
2 1
1 2
1 1

poprawną odpowiedzią jest:
6

 

 

Plansza przykładowego wejścia. Literą P oznaczona jest początkowa pozycja pionka.
Liczby tworzące ścieżkę to aktualny sumaryczny koszt wykonanych ruchów.

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.
5
Twoja ocena: Brak Ocena: 5 (1 ocena)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com