| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Поиск цифры для удаления |
| Автор: 10vital08 7.3.2017, 15:12 |
| Добрый день! У меня есть задание, помогите пожалуйста с алгоритмом решения. Формулировка: Последовательность из нулей и единиц четной длины назовем справедливой, если на четных местах этой последовательности столько же единиц, сколько на нечетных. Например, последовательность "011011" является справедливой, а последовательность "011101" — нет. Задана некоторая последовательность нечетной длины из нулей и единиц. Из нее разрешается удалить одну цифру. Какую цифру следует удалить, чтобы последовательность стала справедливой? Например, из последовательности "0111011" с этой целью можно удалить вторую цифру. Входные данные Входной файл содержит одну строку. Эта строка содержит последовательность нечетной длины из нулей и единиц. Длина последовательности не превышает 200001. Выходные данные Выведите в выходной файл одно число - номер цифры в последовательности, которую следует удалить, чтобы последовательность стала справедливой. Цифры нумеруются, начиная с 1. Если это сделать невозможно, выведите 0. Если решений несколько, выведите любое. |
| Автор: Akina 7.3.2017, 16:17 |
| 1) Для каждой последовательности чётной длины введи характеристику "несправедливость", равную разности количества единиц на чётном и нечётном местах. 2) Если некий символ изымается, то "несправедливость" хвоста меняет знак (ведь чётные становятся нечётными и наоборот). 3) "Несправедливость" двух "склеенных" последовательностей равна сумме их "несправедливостей", если длина первой чётна, и разности, если нечётна. Этого достаточно, чтобы построить алгоритм поиска точки изъятия символа, зная "несправедливость" всей последовательности и "несправедливость" блока от начала до текущей точки. |