Zadacha AB-shki
Dana posledovatel'nost' iz 2N jacheek. Dve sosednie iz nih - pustye, a
ostal'nye soderzhat N-1 simvolov A i N-1 simvolov B.
Primer dlja N = 5:
A B B A A B A B
Pravila peremeschenija:
Soderzhimoe ljubyh dvuh sosednih nepustyh jacheek mozhno, sohranjaja ih porjadok,
peresylat' v pustye jachejki.
Cel':
Ispol'zuja pravilo peremeschenija, dostich' konfiguracii, v kotoroj vse simvoly A raspolozheny levee vseh simvolov B. Mestopolozhenie pustyh jacheek posle peremeschenij ne imeet znachenija.
Zadanie:
Napisat' programmu, kotoraja:
- Vvodit s klaviatury nachal'nuju konfiguraciju v vide posledovatel'nosti simvolov A, B i nulej dlja pustyh jacheek, a takzhe modeliruet peremeschenija.
- Dlja zadannoj nachal'noj konfiguracii opredeljaet po krajnej mere odin plan peremeschenij, s pomosch'ju kotorogo mozhno dostich' celi, ili soobschaet, chto takogo plana ne suschestvuet. Vyvod dolzhen soderzhat' nachal'nuju konfiguraciju, promezhutochnye konfiguracii posle kazhdogo shaga, a takzhe zakljuchitel'nuju konfiguraciju.
- Nahodit plan dostizhenija celi za minimal'noe chislo shagov.
Rezul'taty:
Predstavit' po krajnej mere hotja by odno reshenie dlja primera, privedennogo
vyshe.
