Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Поиск цифры для удаления 
:(
    Опции темы
10vital08
Дата 7.3.2017, 15:12 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 4
Регистрация: 26.1.2017

Репутация: нет
Всего: нет



Добрый день!

У меня есть задание, помогите пожалуйста с алгоритмом решения.
Формулировка:

Последовательность из нулей и единиц четной длины назовем справедливой, если на четных местах этой последовательности столько же единиц, сколько на нечетных. Например, последовательность "011011" является справедливой, а последовательность "011101" — нет.

Задана некоторая последовательность нечетной длины из нулей и единиц. Из нее разрешается удалить одну цифру. Какую цифру следует удалить, чтобы последовательность стала справедливой?

Например, из последовательности "0111011" с этой целью можно удалить вторую цифру.

Входные данные

Входной файл содержит одну строку. Эта строка содержит последовательность нечетной длины из нулей и единиц. Длина последовательности не превышает 200001.

Выходные данные

Выведите в выходной файл одно число - номер цифры в последовательности, которую следует удалить, чтобы последовательность стала справедливой. Цифры нумеруются, начиная с 1. Если это сделать невозможно, выведите 0. Если решений несколько, выведите любое.
PM MAIL   Вверх
Akina
Дата 7.3.2017, 16:17 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Советчик
****


Профиль
Группа: Модератор
Сообщений: 20570
Регистрация: 8.4.2004
Где: Зеленоград

Репутация: 20
Всего: 453



1) Для каждой последовательности чётной длины введи характеристику "несправедливость", равную разности количества единиц на чётном и нечётном местах.
2) Если некий символ изымается, то "несправедливость" хвоста меняет знак (ведь чётные становятся нечётными и наоборот).
3) "Несправедливость" двух "склеенных" последовательностей равна сумме их "несправедливостей", если длина первой чётна, и разности, если нечётна.

Этого достаточно, чтобы построить алгоритм поиска точки изъятия символа, зная "несправедливость" всей последовательности и "несправедливость" блока от начала до текущей точки.


--------------------
 О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума.

PM MAIL WWW ICQ Jabber   Вверх
  
Ответ в темуСоздание новой темы Создание опроса
Правила форума "Алгоритмы"

maxim1000

Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.


Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000.

 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Алгоритмы | Следующая тема »


 




[ Время генерации скрипта: 0.1018 ]   [ Использовано запросов: 21 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.