|
|
|
10vital08 |
|
|||
Новичок Профиль Группа: Участник Сообщений: 4 Регистрация: 26.1.2017 Репутация: нет Всего: нет |
Добрый день!
У меня есть задание, помогите пожалуйста с алгоритмом решения. Формулировка: Последовательность из нулей и единиц четной длины назовем справедливой, если на четных местах этой последовательности столько же единиц, сколько на нечетных. Например, последовательность "011011" является справедливой, а последовательность "011101" — нет. Задана некоторая последовательность нечетной длины из нулей и единиц. Из нее разрешается удалить одну цифру. Какую цифру следует удалить, чтобы последовательность стала справедливой? Например, из последовательности "0111011" с этой целью можно удалить вторую цифру. Входные данные Входной файл содержит одну строку. Эта строка содержит последовательность нечетной длины из нулей и единиц. Длина последовательности не превышает 200001. Выходные данные Выведите в выходной файл одно число - номер цифры в последовательности, которую следует удалить, чтобы последовательность стала справедливой. Цифры нумеруются, начиная с 1. Если это сделать невозможно, выведите 0. Если решений несколько, выведите любое. |
|||
|
||||
Akina |
|
|||
Советчик Профиль Группа: Модератор Сообщений: 20570 Регистрация: 8.4.2004 Где: Зеленоград Репутация: 20 Всего: 453 |
1) Для каждой последовательности чётной длины введи характеристику "несправедливость", равную разности количества единиц на чётном и нечётном местах.
2) Если некий символ изымается, то "несправедливость" хвоста меняет знак (ведь чётные становятся нечётными и наоборот). 3) "Несправедливость" двух "склеенных" последовательностей равна сумме их "несправедливостей", если длина первой чётна, и разности, если нечётна. Этого достаточно, чтобы построить алгоритм поиска точки изъятия символа, зная "несправедливость" всей последовательности и "несправедливость" блока от начала до текущей точки. -------------------- О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума. |
|||
|
||||
Правила форума "Алгоритмы" | |
|
Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.
Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000. |
1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей) | |
0 Пользователей: | |
« Предыдущая тема | Алгоритмы | Следующая тема » |
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |