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

[Maksay]

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

[Michael_Rybak]

>Найдешь преобразование, переводящее из А в С?

А чего придираться?

Понятно, что я имел ввиду, что преобразование - это цепочка переворотов, а не один переворот. Т.е. "если из строки А путем нескольких переворотов ..." и т. д.

>транзитивность ты и не используешь
В том то и дело, что использую. Использую для того, чтобы канонический вид имел право выступать в качестве промежуточного звена. Если бы транзитивности у преобразований не было (преобразований, очевидно, в смысле цепочек переворотов), то от канонического вида толку б не было.

[Lapp]

> > Найдешь преобразование, переводящее из А в С?
> А чего придираться?
???

> Понятно, что я имел ввиду, что преобразование - это цепочка переворотов,
> а не один переворот. Т.е. "если из строки А путем нескольких переворотов ..." и т. д.
Вообще, транзитивность обычно не применяется к бинарным операциям. Обычно это свойство операций сравнения (a<b, b<c => a<c). Я просто попытался распространить это на бинарные операции (что, впрочем, не имеет особого смысла, так как в группах выражается свойством принадлежности результата операции к группе). То, что ты имел в виду на самом деле означает, что если операцию удалось произвести два раза, то это можно повторить - что настолько очевидно, что непонятно, у кого может возникнуть вопрос. Попробуй перенести свое понятие на обычные числа (скажем, на группу целых чисел по сложению), и ты поймешь, что это "свойство" абсолютно ничего не добавляет

> >транзитивность ты и не используешь
> В том то и дело, что использую. Использую для того, чтобы канонический вид
> имел право выступать в качестве промежуточного звена. Если бы транзитивности
> у преобразований не было (преобразований, очевидно, в смысле цепочек
> переворотов), то от канонического вида толку б не было.
Повторяю, речь идет только о возможности выполнять законные преобразования, которая, конечно, есть всегда. Существования обратной операции вполне достаточно. Подумай над этим.

В целом решение интересное, но некоторые моменты мне не ясны..
Ты пишешь:
> плавающая единица образует две группы, одна из которых
> обязательно будет четной, а другая нечетной,
А почему это? Известно, что количество нулей сохраняется, и если оно изначально было четным, то будет четным и в конце. Соответственно, оно будет разбито на чет-чет или нечет-нечет..
Что я упустил?

[Michael_Rybak]

> > > Найдешь преобразование, переводящее из А в С?
> > А чего придираться?
> ???

Сорри, слегка грубовато, но мне кажется очевидным, какую "транзитивность" имел ввиду я. Ну и понятно, что я не стал бы утверждать, что один переворот транзитивен в смысле твоего контрпримера.

>и ты поймешь, что это "свойство" абсолютно ничего не добавляет
ок, я согласен с некоторой аксиоматичностью этого свойства. Мне все же кажется, что так оно, все таки, нагляднее - можем из А получить канон., из В получить канон (=> по обратимости можем из канон. получить В), потому, по транзитивности, из А можем В.

Согласен, что транзитивность можно было при этом не упоминать.

> плавающая единица образует две группы, одна из которых
> обязательно будет четной, а другая нечетной,
А почему это? Известно, что количество нулей сохраняется, и если оно изначально было четным, то будет четным и в конце. Соответственно, оно будет разбито на чет-чет или нечет-нечет..
Что я упустил?

Мы смотрим не на четность количества нулей, а на само количество нулей.

Для примера, рассмотрим все канонические битовые строки длины 10, в которых встречается ровно 4 единички. По ходу считаем для них наш инвариант I.

1111000000 - <>1<>1<>1<>1<000000> - I = 6
1110100000 - <>1<>1<>1<0>1<00000> - I = 5
1110010000 - <>1<>1<>1<00>1<0000> - I = 4
1110001000 - <>1<>1<>1<000>1<000> - I = 3
1110000100 - <>1<>1<>1<0000>1<00> - I = 2
1110000010 - <>1<>1<>1<00000>1<0> - I = 1
1110000001 - <>1<>1<>1<000000>1<> - I = 0

Получается, что значение инварианта различно для всех возможных канонических строк.

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

Вообще, во всем решении, говоря о "нечетных" группах, я говорил о порядковом номере. Т.е. мы просто идем по строке слева направо, сладывая кол-во нулей в группах, и каждую вторую группу при этом игнорируем.

Тогда получается, что плавающая единица образует две группы - слева от нее, и справа от нее. И одну из них (например, левую) мы все время учитываем в сумме, а другую - нет. Левую, или правую - зависит от кол-ва единиц.