IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

2 страниц V  1 2 >  
 Ответить  Открыть новую тему 
> Битовые последовательности, Помогите решить задачу
сообщение
Сообщение #1





Группа: Пользователи
Сообщений: 4
Пол: Мужской
Реальное имя: Андрей Максай

Репутация: -  0  +


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


Perl. Just code it!
******

Группа: Пользователи
Сообщений: 4 100
Пол: Мужской
Реальное имя: Андрей

Репутация: -  44  +


Может быть вариант что нам для получения придется преревернуть несколько подпоследовательностей ? Ну на рпимер с 4 по 7, с 12 по 20 и с 23 по 25 ? Или нам надо перевернуть какую-то одну (из всех имеющихся) последовательность с нечетным кол-вом едениц ?

Хотя сори, слово подпоследовательностей говорит само за себя smile.gif_


--------------------
perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Гость






В дополнение к предыдущему вопросу: может ли понадобиться "разворот" перекрывающихся подпоследовательностей? Допустим, сначала 4-7, а затем 6-10? Или это не разрешено?

Кстати, если можно - еще хотя бы несколько тестов приведи...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Perl. Just code it!
******

Группа: Пользователи
Сообщений: 4 100
Пол: Мужской
Реальное имя: Андрей

Репутация: -  44  +


Volvo, и на твой вопрос ответ судя по всему тоже да, ибо в примере сначала была перевернута вся последовательность, а потом кусок из середины smile.gif


--------------------
perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Гость






Тогда есть высокая (очень высокая) вероятность того, что ВСЕГДА можно исходную последовательность привести к результату. За исключением случаев, когда в исходной последовательности всего одна единица.

Кстати, приведенный пример решается так:
исходная:
011010010

010101010 = результат...

Так что... Перекрывающихся подпоследовательностей не было. Вопрос в силе.
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6





Группа: Пользователи
Сообщений: 4
Пол: Мужской
Реальное имя: Андрей Максай

Репутация: -  0  +


Извиняюсь, пример действительно неудачный.Переворачивать можно сколько угодно раз и как угодно.
Другие тесты:
1)Вход:
9
100011100
001011001
Выход:
Да
6 9
3 8
1 5
2)Вход:
7
1001001
Изменить невозможно
3)Вход:
7
11001101
10101101
Выход:
Нет
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Профи
****

Группа: Пользователи
Сообщений: 705
Пол: Мужской

Репутация: -  20  +


У меня вот такой алгоритм получился:

uses crt;
var c,i,j,n:integer;
s1,s2:string;
function pr(s:string):string;
begin
if s='' then pr:=s else
pr:=s[length(s)]+pr(copy(s,1,length(s)-1));
end;

begin
clrscr;
s1:='100011100';s2:='001011001'; {s1:='011010010';s2:='010101010';}
n:=byte(s1[0]);
writeln (s1); writeln (s2);
i:=1;
for i:=1 to n-1 do begin
if s1[i]=s2[i] then continue;
c:=byte(s2[i]='1'); j:=i;
repeat
inc(j);
c:=c+byte(s2[j]='1');
until (j>n) or (not(odd(c )) and (s2[j]=s1[i]));
if (j>n) then writeln ('NO') else begin
s2:=copy(s2,1,i-1)+pr(copy(s2,i,j-i+1))+copy(s2,j+1,255);
writeln ( i,' ',j,' -',s2,' ');
end;
end;
readln;
end.


Не знаю, будет ли он работать во всех случаях (по идее должен), но по нему вариант "Нет" очень даже возможен. Другого способа чего-то в голову не приходит.

Сообщение отредактировано: volvo -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


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 -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Новичок
*

Группа: Пользователи
Сообщений: 19
Пол: Мужской
Реальное имя: Антонио

Репутация: -  2  +


Цитата(Michael_Rybak @ 6.09.2006 6:03) *

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

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


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

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

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

 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


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

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

Сорри за неправильную интерпретацию.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Надеюсь, теперь я правильно понял условие smile.gif

Понятно, что преобразования у нас транзитивные и обратимые.

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 возможным значениям инварианта.

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

Кстати, случай, когда количество единиц в строках отличается (или отличается длина строк), учитывать отдельно не нужно – канонические виды тоже получатся разными smile.gif


Сообщение отредактировано: Michael_Rybak -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #12


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


А эту задачу можно сдать на каком-нибудь онлайн архиве?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #13


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(Michael_Rybak @ 6.09.2006 14:53) *

Понятно, что преобразования у нас транзитивные и обратимые.
1) транзитивность – если из строки А можно получить В, а из В – С, то из А можно получить С (очевидно)

Транзитивность означает существование преобразования, которое (в твоем случае) сразу переводит А в С. А это не только неочевидно, но и неверно.
А: 1100 0011
В: 0011 0011
С: 0011 1100
Найдешь преобразование, переводящее из А в С?
Впрочем, транзитивность ты и не используешь smile.gif. Обратимость же действительно важна.

Мне кажется, такое понимание переворачивания (имени Coder_perm) тоже спорно и не особо лучше первоначального варианта. Нет возможности узнать достоверно, что имеется в виду?


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #14


Гость






Цитата(lapp @ 7.09.2006 13:48)
Нет возможности узнать достоверно, что имеется в виду?
Ну, если автор пишет:
Цитата(Maksay @ 5.09.2006 18:04)
Пример:
011010010 010101010
{011010010
все символы
010010110
с 4 по 7
010101010}

, то очевидно, что имеется в виду именно вариант переворачивания "имени Coder_perm" ©...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #15


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


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

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

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

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


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


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

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

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

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


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #17


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


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

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

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

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

Цитата(lapp @ 7.09.2006 23:58) *

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


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

Для примера, рассмотрим все канонические битовые строки длины 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

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

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

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

Тогда получается, что плавающая единица образует две группы - слева от нее, и справа от нее. И одну из них (например, левую) мы все время учитываем в сумме, а другую - нет. Левую, или правую - зависит от кол-ва единиц.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #18


Профи
****

Группа: Пользователи
Сообщений: 705
Пол: Мужской

Репутация: -  20  +


Ну вы и монстры, блин smile.gif

Michael_Rybak
Алгоритм интересный, но в реализации будет наверное громоздким. Но у него есть преимущество перед моим - "да" или "нет" он скажет до вывода результата, у меня вычисляется в процессе. Хотя мой тоже можно переделать (просто прогнать 2 раза: 1 раз для "да"-"нет", второй раз результат smile.gif )

Мне непонятен только вот этот пример:
2)Вход:
7
1001001
Изменить невозможно

Почему невозможно, если можно так: 1001001, 1001001 и т.д. ?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #19


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Цитата
Алгоритм интересный, но в реализации будет наверное громоздким


Совсем нет:


{$AppType CONSOLE}

const MAX_N = 128;

type TAr = array [1 .. MAX_N] of longint;

var n0, n1: integer;
a0, b0, a1, b1: TAr;
s0, s1: string;
i, len: integer;

procedure ToCanonic(var s: string; var n: longint; var a, b: TAr);
var i, j, k, ones: longint;
t: char;
begin
n := 0;
for i := 1 to Length(s) do
if s[i] = '0' then begin
ones := 0;
for j := i + 1 to Length(s) do
if s[j] = '1' then begin
Inc(ones);
if ones = 2 then begin
Inc(n);
a[n] := i;
b[n] := j;
for k := i to (i + j) Div 2 do begin
t := s[k];
s[k] := s[i + j - k];
s[i + j - k] := t;
end;
break;
end;
end;
if ones < 2 then
break; //достигли плавающей единицы
end;
end;

begin
Readln(len);
Readln(s0);
Readln(s1);
ToCanonic(s0, n0, a0, b0);
ToCanonic(s1, n1, a1, b1);
if s0 <> s1 then
Writeln('No')
else begin
Writeln('Yes');
for i := 1 to n0 do
Writeln(a0[i], ' ', b0[i]);
for i := n1 downto 1 do
Writeln(a1[i], ' ', b1[i]);
end;
end.


Цитата
Хотя мой тоже можно переделать (просто прогнать 2 раза: 1 раз для "да"-"нет", второй раз результат smile.gif )

А ты можешь доказать правильность своего?

Цитата
Почему невозможно, если можно так: 1001001, 1001001 и т.д.


Согласен.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #20


Профи
****

Группа: Пользователи
Сообщений: 705
Пол: Мужской

Репутация: -  20  +


Цитата(Michael_Rybak @ 8.09.2006 16:28) *

А ты можешь доказать правильность своего?

На олимпиадах не требуется доказательство правильности решения задачи, важна работоспособность на тестовых примерах, а на них все работает, так что..
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

2 страниц V  1 2 >
 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 29.03.2024 8:20
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name