Божевільний вчений#10118

Божевільний вчений (Розбір)

Будемо переглядати рядки $a$ і $b$ зліва направо. Розглянемо позиції, в яких символи рядків відрізняються. Нехай $i$ — індекс першої такої позиції, що $a_{i} \neq = b_{i}$ a_i \ne b_i. Це означає, що символ у рядку $b$ на позиції $i$ необхідно інвертувати. У цей момент ми фіксуємо початок інтервалу застосування машини.

Далі продовжуємо рухатися вправо, поки символи рядків продовжують відрізнятися, тобто для всіх індексів $k$ з інтервалу $i \leq k \leq j$ i \le k \le j виконується умова $a_{k} \neq = b_{k}$ a_k \ne b_k. Як тільки зустрічається позиція $j + 1$ j + 1, для якої $a_{j + 1} = b_{j + 1}$ a_{j+1} = b_{j+1}, поточний інтервал $[i; j]$ завершується. Цей інтервал є максимальним за включенням: розширити його ні вліво, ні вправо не можна.

Кожному такому інтервалу відповідає рівно одне застосування машини MCBF-3000, оскільки машина інвертує всі символи на вибраній підрядку, тим самим одночасно виправляючи всі неспівпадіння всередині інтервалу. Таким чином, відповіддю на задачу є кількість таких максимальних інтервалів.

Приклад

Для заданого прикладу існує два неперетинних інтервали, на яких необхідно застосувати машину MCBF-3000.

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

Читаємо вхідні дані.

cin >> n >> a >> b;

У змінній $c n t$ зберігаємо довжину поточного інтервалу неспівпадінь. У змінній $r es$ накопичуємо відповідь — кількість застосувань машини.

res = cnt = 0;

Послідовно обробляємо символи рядків.

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

Якщо $a_{i} \neq = b_{i}$ a_i \ne b_i, збільшуємо $c n t$ на одиницю.

  if (a[i] != b[i])
    cnt++;

В іншому випадку (якщо $a_{i} = b_{i}$ a_i = b_i), поточний інтервал неспівпадінь завершується: скидаємо $c n t$ в нуль і збільшуємо лічильник інтервалів $r es$ на одиницю.

  else
  {
    if (cnt > 0) res++;
    cnt = 0;
  }

Якщо $c n t > 0$ cnt > 0, це означає, що в кінці рядка залишився незавершений інтервал неспівпадінь, для якого також необхідно здійснити одне застосування машини.

if (cnt > 0) res++;

Виводимо відповідь.

cout << res << endl;

Python реалізація

Читаємо вхідні дані.

n = int(input())
a = input()
b = input()

res = cnt = 0

Послідовно обробляємо символи рядків.

for i in range(n):

Якщо $a_{i} \neq = b_{i}$ a_i \ne b_i, збільшуємо $c n t$ на одиницю.

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

  else:
    if cnt > 0: res += 1
    cnt = 0

if cnt > 0: res += 1

Виводимо відповідь.

print(res)