10118. Сумасшедший ученый

Фермер Джон упорядочил n своих коров, каждая из которых имеет одну из двух пород Holsteins или Guernseys. Он зафиксировал этот порядок в виде строки из n символов, каждый из которых либо H, либо G соответственно. К несчастью, когда коровы прибыли на ферму и он снова их выстроил, они образовали строку, отличную от исходной.

Назовём эти две строки a и b, где a – исходная строка, которую он хотел увидеть, b – строка которая получилась по прибытию коров. Фермер Джон попросил помощи у кузена Бена.

После нескольких месяцев работы Бен создал замечательную машину MCBF-3000, которая способна взять любую подстроку и поменять в ней все G на H, а все H на G. Теперь Фермер Джон хочет узнать минимальное количество применений этой машины, которые позволят превратить строку b в строку a. Помогите Фермеру Джону.

Вход. Первая строка содержит n (1 ≤ n ≤ 1000), следующие две строки содержат строки a и b. Каждая из строк состоит только из символов H и G.

Выход. Выведите минимальное количество раз применения машины MCBF-3000 для трансформации строки b в строку a.

Пример входа	Пример выхода
7 GHHHGHH HHGGGHH	2

РЕШЕНИЕ

жадность

Анализ алгоритма

Проходим по строкам слева направо и подсчитываем количество таких подстрок максимального размера [i; j], к которым следует применить машину MCBF-3000. Это такие интервалы, что для каждого k (i ≤ k ≤ j) имеет место a_k ≠ b_k.

Как только встречается такое i что a_i ≠ b_i, фиксируем начало интервала. И движемся вперед пока не встретим такой индекс j что a_j+1 = b_j+1. Подсчитываем количество таких интервалов [i; j].

Пример

Для заданного примера имеется два интервала, на которых следует применить машину.

Реализация алгоритма

Читаем входные данные.

cin >> n >> a >> b;

В переменной cnt содержим длину текущего несовпадающего интервала. В переменной res вычисляем ответ.

res = cnt = 0;

Последовательно обрабатываем буквы строк.

for (i = 0; i < n; i++)

Если a_i ≠ b_i, то увеличиваем cnt на единицу. Иначе сбрасываем cnt в ноль и увеличиваем количество интервалов res.

if (a[i] != b[i])

cnt++;

else

{

if (cnt > 0) res++;

cnt = 0;

}

Если cnt > 0, то следует учесть последний интервал, на котором необходимо применить машину.

if (cnt > 0) res++;

Выводим ответ.

cout << res << endl;

Реализация алгоритма

Читаем входные данные.

n = int(input())

a = input()

b = input()

В переменной cnt содержим длину текущего несовпадающего интервала. В переменной res вычисляем ответ.

res = cnt = 0

Последовательно обрабатываем буквы строк.

for i in range(n):

Если a_i ≠ b_i, то увеличиваем cnt на единицу. Иначе сбрасываем cnt в ноль и увеличиваем количество интервалов res.

if a[i] != b[i]: cnt += 1

else:

if cnt > 0: res += 1

cnt = 0

Если cnt > 0, то следует учесть последний интервал, на котором необходимо применить машину.

if cnt > 0: res += 1

Выводим ответ.

print(res)