Domácí kolo

E: Evoluce

Abys mohl odevzdávat úlohy, musíš se přihlásit nebo zaregistrovat

Soutež skončila. Získané body již nejdou do výsledků.

Zadání (Řešení)

Během dalších průzkumných misí na Ma-stře se cestovatelům podařilo objevit mnoho mimozemských organismů. Po zdlouhavých pokusech vědci zjistili, že všechny nově objevené organismy mají stejný základ DNA. Mimozemskou DNA jednoho organismu lze zapsat jako řetězec, který se skládá ze znaků a, b. Během evoluce se s geny děly pouze tyto dva typy změn:

  • změnění jednoho znaku na opačný – vyměnění a za b nebo b za a,
  • změnění všech znaků na opačné na nějakém libovolně dlouhém úseku řetězce počínaje prvním znakem – tedy např.: babbabbb (změnili jsme první dva znaky), ababab (změnili jsme všechny tři znaky), ale už ne aaaabb (změnili jsme druhý a třetí znak, ale nezměnili jsme první).

Na vstupu dostaneme dva stejně dlouhé řetězce mimozemské DNA. Pro výzkum a pochopení vývoje jiných forem života je potřeba vědět, jak hodně se od sebe jednotlivé druhy evolučně liší – tedy na kolik nejméně změn dokážeme z jednoho řetězce vytvořit druhý.

Tvar vstupu

Na prvním řádku souboru je číslo T – počet testů v souboru. Následují jednotlivé testy bezprostředně za sebou. Na prvním řádku každého testu je N – délka obou řetězců. Na druhém a třetím řádku jsou dva řetězce délky N složené ze znaků ab.

Tvar výstupu

Pro každý test vypište na samostatný řádek nejmenší počet operací provedených na první řetězec, po jejichž provedení budou řetězce shodné.

Lehká verze

  • T ≤ 10
  • N ≤ 106
  • existuje optimální řešení, které si vystačí pouze s jedním typem z povolených operací

Těžká verze

  • T ≤ 10
  • N ≤ 106

Ukázkový vstup

2
7
aabaaba
aaaaabb
5
abbaa
bbaba

Ukázkový výstup

2
2

Vysvětlení ukázkového vstupu a výstupu

V prvním případě je optimálním řešením provést první operaci na třetí a sedmý znak řetězce (číslujeme od jedničky). V druhém případě je jedním z možných optimálních řešení nejprve provést první operaci na druhý znak (čímž dostaneme aabaa) a pak provést druhou operaci na první čtyři znaky. Tento test by se v lehčím vstupu neobjevil, protože s pouze jednou z operací na dva kroky vyřešit nejde.

Máš na to!

I ty můžeš vyhrát! Nebo to aspoň zkusit :)