DNA - COCI

Biolozi su otkrili neobičnu DNA molekulu koju možemo zamisliti kao niz od N znakova od kojih je svaki A ili B. Određenim mutacijama sva su se slova ovog niza pretvorila u A. Biolozima je to bilo vrlo neobično pa su malo pomnije proučili mutacije ove molekule.

Ispostavilo se da postoje dvije vrste mutacija. Jedna vrsta mutacije promijenit će jedan element niza (dakle A → B ili B → A). Druga vrsta mutacije promijenit će neki prefiks niza, što znači da će se svako slovo od prvog do K-tog (za neki K između 1 i N, uključivo) zamijeniti sa drugim slovom (A sa B, B sa A).

Izračunajte najmanji mogući broj mutacija koji je od početnog stanja molekule mogao dovesti do konačnog stanja (u kojem su sva slova jednaka A). Mutacije se mogu događati bilo kojim redoslijedom.