Lo scienziato pazzo (Editoriale)

Esamineremo le stringhe $a$ e $b$ da sinistra verso destra. Consideriamo le posizioni in cui i simboli delle stringhe differiscono. Sia $i$ l'indice della prima posizione tale che a_i \ne b_i. Ciò significa che il simbolo nella stringa $b$ nella posizione $i$ deve essere invertito. In questo momento fissiamo l'inizio dell'intervallo di applicazione della macchina.

Continuiamo poi a muoverci verso destra finché i simboli delle stringhe continuano a differire, cioè finché per tutti gli indici $k$ dell'intervallo i \le k \le j è soddisfatta la condizione a_k \ne b_k. Non appena si incontra una posizione j + 1 per cui a_{j+1} = b_{j+1}, l'intervallo corrente $[i;j]$ si conclude. Questo intervallo è massimale per inclusione: non può essere esteso né a sinistra né a destra.

A ciascuno di questi intervalli corrisponde esattamente un'applicazione della macchina MCBF-3000, poiché la macchina inverte tutti i simboli sulla sottostringa selezionata, correggendo così simultaneamente tutte le discrepanze all'interno dell'intervallo. Pertanto, la risposta al problema è il numero di tali intervalli massimali.

Esempio

Per l'esempio dato esistono due intervalli disgiunti su cui è necessario applicare la macchina MCBF-3000.

Implementazione dell'algoritmo

Leggiamo i dati in input.

cin >> n >> a >> b;

Nella variabile $cnt$ memorizziamo la lunghezza dell'intervallo corrente di discrepanze. Nella variabile $res$ accumuliamo la risposta — il numero di applicazioni della macchina.

res = cnt = 0;

Elaboriamo in sequenza i simboli delle stringhe.

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

Se a_i \ne b_i, incrementiamo $cnt$ di uno.

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

Altrimenti (se a_i = b_i), l'intervallo corrente di discrepanze si conclude: azzeriamo $cnt$ e incrementiamo di uno il contatore degli intervalli $res$.

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

Se cnt > 0, significa che alla fine della stringa è rimasto un intervallo di discrepanze non concluso, per il quale è comunque necessario eseguire un'applicazione della macchina.

if (cnt > 0) res++;

Stampiamo la risposta.

cout << res << endl;

Implementazione in Python

Leggiamo i dati in input.

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

Nella variabile $cnt$ memorizziamo la lunghezza dell'intervallo corrente di discrepanze. Nella variabile $res$ accumuliamo la risposta — il numero di applicazioni della macchina.

res = cnt = 0

Elaboriamo in sequenza i simboli delle stringhe.

for i in range(n):

Se a_i \ne b_i, incrementiamo $cnt$ di uno.

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

Altrimenti (se a_i = b_i), l'intervallo corrente di discrepanze si conclude: azzeriamo $cnt$ e incrementiamo di uno il contatore degli intervalli $res$.

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

Se cnt > 0, significa che alla fine della stringa è rimasto un intervallo di discrepanze non concluso, per il quale è comunque necessario eseguire un'applicazione della macchina.

if cnt > 0: res += 1

Stampiamo la risposta.

print(res)