Битовые последовательности, Помогите решить задачу |
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, с четным количеством (0) единиц. Тогда идея такая: 1. Заменяем все нолики единичками 2. Если n четное, переворачиваем всю строку, получаем все нули. Если нечетное, то переворачиваем со второго по последний, потом второй превращаем обратно в единицу, потом переворачиваем первые два. Например: 11111 10000 - перевернули 2-5 11000 - перевернули 2-2 00000 - перевернули 1-2 Таким образом, любую строку мы превратили в строку нулей. А теперь заменяем нужные нули на единицы. Единственный случай, когда это не работает - это когда первая строка - "1", а вторая - "0". Тогда нельзя сделать "потом *второй* превращаем обратно в единицу", потому что второго нету. На приведенном примере: 9 100011100 001011001 100011100 Заменяем нули единицами. 2-2: 110011100 3-3: 111011100 4-4: 111111100 8-8: 111111110 9-9: 111111111 Превращаем всё в нули: 2-9: 100000000 2-2: 110000000 1-2: 000000000 Строим то, что нужно: 3-3: 001000000 5-5: 001010000 6-6: 001011000 9-9: 001011001 Ответ: да 2 2 3 3 4 4 8 8 9 9 2 9 2 2 1 2 3 3 5 5 6 6 9 9 Сообщение отредактировано: Michael_Rybak - |
Coder_perm |
Сообщение
#3
|
Новичок Группа: Пользователи Сообщений: 19 Пол: Мужской Реальное имя: Антонио Репутация: 2 |
В условии сказано: подпоследовательностей с четным кол-вом единиц. Это значит, что любой нолик можно перевернуть, правильно? Это ведь подпоследовательность длины 1, с четным количеством (0) единиц. ИМХО ты немного не правильно понял условие задачи: 1. Переворачивать, не значит менять 0 на 1 и обратно. Это значит, что последовательность 110000 перевернется в 000011, а не в 001111. 2. Каждое переворачиваение должно происходить только с четным количеством элементов последовательности, а не общее число перевернутых элементов должно быть четным. |
Michael_Rybak |
Сообщение
#4
|
Michael_Rybak Группа: Пользователи Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
>1. Переворачивать, не значит менять 0 на 1 и обратно.
мдя. что есть то есть >с четным количеством элементов последовательности Ну там сказано не элементов, а именно единиц. Т.е. в переворачиваемой последовательности количество элементов, равных единице, должно быть четным. Сорри за неправильную интерпретацию. |
Текстовая версия | 27.04.2024 13:26 |