Задача №113786. Туризм
Министерство туризма Лайнландии решило разработать интересный маршрут для туристов. В Лайнландии n городов, расположенных вдоль одной дороги. Города пронумерованы от 1 до n вдоль дороги, причём в некоторых городах есть достопримечательности, а в других — нет. Введем обозначение: пусть a i = 1 , если в i -м городе есть достопримечательности, и a i = 0 , если нет.
Выбор маршрута будет осуществлять министр туризма. Для того, чтобы ему было из чего выбирать, решено было разработать два различных аналогичных маршрута. Каждый маршрут должен представлять собой несколько идущих подряд вдоль дороги городов: l , l + 1, ..., r . Два маршрута считаются аналогичными, если они посещают одинаковое количество городов, причём количество городов в маршрутах, содержащих достопримечательности, также совпадает.
Чтобы маршрут был как можно интереснее, он должен посещать максимальное возможное количество городов. Помогите сотрудникам министерства, найдите два аналогичных маршрута, содержащих максимальное возможное количество городов.
В единственной строке входных данных расположена строка из символов « 0 » и « 1 », i -й символ этой строки задает значение a i . Длина этой строки хотя бы 3 и не превосходит 10 6 . Символы не разделяются пробелами.
Выведите четыре числа s 1 , t 1 , s 2 и t 2 — номера первого и последнего города первого маршрута и номера первого и последнего города второго маршрута, соответственно. Гарантируется, что ответ всегда существует.
10101
1 4 2 5