Равномерен низ

Разглеждаме низове, съставени от два знака ‘0’ и ‘1’. Един такъв низ наричаме равномерен, ако започва с единица, няма съседни единици, броят на единиците не надминава броя на нулите и дължините на поднизовете от съседни нули се различават най-много с 1, например равномерни низове са ‘10001001000’, ‘1010’ и ‘101010100100100‘, а ‘0’, ‘011‘, ‘101001000’ – не са.

Казваме, че за един низ извършваме циклично изместване, ако първият му елемент го преместим на последно място. Например ‘10010’ → ‘00101’. Цикличното изместваме може да извършваме последователно многократно. Например след трикратно циклично изместване от ‘10010’ получаваме ‘10100’.

За даден равномерен низ разглеждаме операцията редукция, която извършва следното:

• Премахва единиците.
• Всеки подниз от нули (от първоначално дадения низ) от вид, който се среща по рядко се заменя с 1, а всеки подниз от нули от другия вид се заменя с 0. Ако двата вида поднизове от нули се срещат еднакво често, тогава по-късият се заменя с 1, а по-дългия – с 0.
• Ако полученият низ съдържа поне една единица, извършва се циклично изместване (еднократно или многократно), докато за първи път се получи низ с 1 на първо място.

Примери:

1. ‘1000100100’ се редуцира към ‘100’;
2. ‘10001001000100’ се редуцира към ‘1010’ (тук е приложено циклично изместване);
3. ‘100010010010001000’ се редуцира към ‘11000’ (тук е приложено циклично изместване);
4. ‘1001000’ се редуцира към ‘10’.
5. ‘100’ се редуцира към ‘0’.

Виждаме от примерите, че след редукция на равномерен низ, в някои случаи отново се получава равномерен низ, а в други случаи - не е така.

Напишете програма niz, която въвежда низ от нули и единици и намира след колко пъти последователно прилагане на операцията редуциране, низът който се е получил не е равномерен.

От първият рдаед на стандартния вход се въвежда низ от нули и единици. Дължината на низа не надминава 500 000.

На един ред на стандартния изход изведете цяло число и низ, отделени с един интервал. Числото трябва да е равно на броя пъти на последователно прилагане на операцията редуциране до първото получаване на низ, който не е равномерен. Низът трябва да е полученият низ, който не е равномерен. Ако този низ има повече от 50 знака, изведете само първите му 50 знака.

Обяснение на пример едно: 10010100 → 100 → 0

Обяснение на пример две: 1010010100 → 1010 → 00

Обяснение на пример три: Входният низ не е равномерен.