ASK

30.10.2010
TrudnośćTrudność

ASK

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


Na zajęciach z Architektury Systemów Komputerowych, Paweł przygotował nowy model pamięci operacyjnej, który wspiera szybkie operacje bitowe wykonywane na całej zawartości pamięci. W modelu Pawła, bity stanowią pojedynczy ciąg zerojedynkowy. Zmiana zawartości pamięci realizowana jest poprzez użycie specjalnej elektrody. Jej działanie polega na wybraniu pojedynczego bitu oraz kierunku działania (lewo lub prawo), a następnie zanegowaniu każdej wartości bitu idąc w odpowiednią stronę, aż do końca lub początku pamięci. Przykładowo, jeżeli zawartość pamięci to 0010, to wybierając drugi bit i prawy kierunek elektroda zmieni ją na 0101 - drugi bit zmieniany jest z 0 na 1, trzeci bit z 1 na zero, czwarty bit z 0 na 1.

Paweł chce przetestować skuteczność swojego rozwiązania. W tym celu potrzebuje programu, który mając jako dane początkową i końcową zawartość pamięci, policzy minimalną liczbę operacji potrzebnych do przekształcenia jednej zawartości pamięci w drugą. Twoim zadaniem jest pomóc Pawłowi i napisać dla niego odpowiedni program.

Wejście:

W pierwszej linii znajduje się jedna liczba całkowita n (1<=n<=1000000). W drugiej linii znajduje się binarny, n-elementowy ciąg - jest to początkowa zawartość pamięci. W trzeciej linii znajduje się binarny, n-elementowy ciąg - jest to docelowa zawartość pamięci.

Wyjście:

W pierwszej i jedynej linii Twój program powinien wypisać jedną liczbę - minimalną liczbę operacji potrzebną do zamiany początkowej zawartości pamięci w docelową.

Przykład:

Dla danych wejściowych:
8
10010000
00100111

poprawną odpowiedzią jest:
4

 

Objaśnienie przykładu:

Możliwe 4 operacje to:
10010000 -> 01100000 -> 10100000 -> 00100000 -> 00100111

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

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com