Битовые последовательности, Помогите решить задачу Опции

[Maksay]

Люди, кто любит решать олимпиадные задачи на Pascal'е-помогите решить:
Есть 2 битовых последовательности длины N.
Требуется узнать, можно ли получить из одной
другую посредством переворачивания подпоследовательностей
с четным кол-вом единиц, и если да-то как!
Пример:
011010010 010101010
{011010010
все символы
010010110
с 4 по 7
010101010}
P.S. Неделю бъюсь-ничего.Кстати N-до 100.

[Michael_Rybak]

В условии сказано: подпоследовательностей с четным кол-вом единиц.

Это значит, что любой нолик можно перевернуть, правильно? Это ведь подпоследовательность длины 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 - 6.09.2006 7:29

[Coder_perm]

В условии сказано: подпоследовательностей с четным кол-вом единиц.

Это значит, что любой нолик можно перевернуть, правильно? Это ведь подпоследовательность длины 1, с четным количеством (0) единиц.

ИМХО ты немного не правильно понял условие задачи:

1. Переворачивать, не значит менять 0 на 1 и обратно.
Это значит, что последовательность 110000 перевернется в 000011, а не в 001111.

2. Каждое переворачиваение должно происходить только с четным количеством элементов последовательности, а не общее число перевернутых элементов должно быть четным.

[Michael_Rybak]

>1. Переворачивать, не значит менять 0 на 1 и обратно.
мдя. что есть то есть

>с четным количеством элементов последовательности
Ну там сказано не элементов, а именно единиц. Т.е. в переворачиваемой последовательности количество элементов, равных единице, должно быть четным.

Сорри за неправильную интерпретацию.