Битовые последовательности, Помогите решить задачу |
1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!
Битовые последовательности, Помогите решить задачу |
Maksay |
Сообщение
#1
|
Группа: Пользователи Сообщений: 4 Пол: Мужской Реальное имя: Андрей Максай Репутация: 0 |
Люди, кто любит решать олимпиадные задачи на Pascal'е-помогите решить:
Есть 2 битовых последовательности длины N. Требуется узнать, можно ли получить из одной другую посредством переворачивания подпоследовательностей с четным кол-вом единиц, и если да-то как! Пример: 011010010 010101010 {011010010 все символы 010010110 с 4 по 7 010101010} P.S. Неделю бъюсь-ничего.Кстати N-до 100. |
Michael_Rybak |
Сообщение
#2
|
Michael_Rybak Группа: Пользователи Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
Надеюсь, теперь я правильно понял условие
Понятно, что преобразования у нас транзитивные и обратимые. 1) транзитивность – если из строки А можно получить В, а из В – С, то из А можно получить С (очевидно) 2) обратимость – если из А можно получить В, то из В можно получить А (очевидно, нужно просто выполнить операции в обратном порядке) Теперь попытаемся свести обе входные строки к некоторому каноническому виду. Будем перемещать все единицы вплотную влево. Для этого все время находим первый нолик, идем от него вправо, пока не встретим вторую по счету единицу, и переворачиваем. В конце концов одна из единиц останется "висеть" (хотя может получится, что она как раз окажется тоже вплотную к остальным). Назовем ее "плавающей". Например: 11000100110010011011 11000100110010011011 11100100010010011011 11100100010010011011 11110001000010011011 11110001000010011011 11111000010000011011 11111000010000011011 11111100000100001011 11111100000100001011 11111110000100000011 11111110000100000011 11111111000000100001 11111111000000100001 11111111100001000000 В данном случае плавающая единица оказалась на расстоянии 4х нулей от остальных: 11111111100001000000 Даже если бы она оказалась на расстоянии 0 (11111111110000000000), мы все равно ее назвали бы "плавающей". Из транзитивности и обратимости следует, что, если обе входные строки свелись к одному и тому же каноническому виду, то решение существует. Рассмотрим пример, для которого ответ - "да": 1) Вход 9 100011100 001011001 Приводим 100011100: 100011100 100011100 - (2,6) 111000100 Приводим 001011001: 001011001 001011001 – (1,5) 101001001 101001001 – (2,6) 110010001 110010001 – (3,9) 111000100 Чтобы получить ответ, выписываем операции для первой строки, а потом, в обратном порядке, операции для второй: (2,6) (3,9) (2,6) (1,5) Но теперь, конечно, возникает вопрос, почему нельзя, скажем, из строки 111110010 получить строку 111110001. Докажем, что разные канонические строки неприводимы друг к другу. В строке рассмотрим группы нулей (в т.ч. пустые), ограниченные по краям единицами, или краями строки. Групп будет на 1 больше, чем единиц. Например, в строке 1100010110 Будет шесть групп, длины 0,0,3,1,0,1 соответственно: <>1<>1<000>1<0>1<>1<0> Будем рассматривать общее количество нулей в *нечетных* группах: <>1<>1<000>1<0>1<>1<0> Легко проверить, что для нашей задачи эта характеристика является инвариантом, т.е. что переворот произвольной подпоследовательности с *четным* количеством единиц не меняет общего количества нулей в *нечетных* группах. Это объясняется тем, что из-за четности количества единиц все нули, которые были в нечетных группах, попадают опять в нечетные группы, а те, которые были в четных – попадают в четные. Поэтому, какие бы мы не выполняли перевороты, эта характеристика меняться не будет. А для канонических строк она как раз принимает все значения от 0 до n0, где n0 - количество нулей в строке. Действительно, плавающая единица образует две группы, одна из которых обязательно будет четной, а другая нечетной, а все остальные группы - пустые. n0 возможных положений плавающей единицы соответствуют n0 возможным значениям инварианта. Поэтому мы доказали, что, если сведя обе входные строки к каноническому виду, мы получили разные результаты, то ответ – "нет". Кстати, случай, когда количество единиц в строках отличается (или отличается длина строк), учитывать отдельно не нужно – канонические виды тоже получатся разными Сообщение отредактировано: Michael_Rybak - |
Текстовая версия | 27.04.2024 12:41 |