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

시간 제한1초메모리 제한1024 MB

요약

균형 잡힌 0과 1 문자열에 축소 연산을 반복 적용해, 결과가 더 이상 균형 문자열이 아닐 때까지 몇 번 적용했는지와 그 결과 문자열을 구합니다.

난이도: 보통10점 중 5점
유형: 문자열, 시뮬레이션, 구현
정답자: 아직 제출이 없습니다

문제

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

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

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

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

Примери:

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

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

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

입력

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

출력

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

힌트

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

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

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

예제3

예제 1
입력
```
10010100
```
예상 출력
```
2 0
```
예제 2
입력
```
1010010100
```
예상 출력
```
2 00
```
예제 3
입력
```
1011
```
예상 출력
```
0 1011
```