Люди, кто любит решать олимпиадные задачи на Pascal'е-помогите решить:
Есть 2 битовых последовательности длины N.
Требуется узнать, можно ли получить из одной
другую посредством переворачивания подпоследовательностей
с четным кол-вом единиц, и если да-то как!
Пример:
011010010 010101010
{011010010
все символы
010010110
с 4 по 7
010101010}
P.S. Неделю бъюсь-ничего.Кстати N-до 100.
Может быть вариант что нам для получения придется преревернуть несколько подпоследовательностей ? Ну на рпимер с 4 по 7, с 12 по 20 и с 23 по 25 ? Или нам надо перевернуть какую-то одну (из всех имеющихся) последовательность с нечетным кол-вом едениц ?
Хотя сори, слово подпоследовательностей говорит само за себя _
В дополнение к предыдущему вопросу: может ли понадобиться "разворот" перекрывающихся подпоследовательностей? Допустим, сначала 4-7, а затем 6-10? Или это не разрешено?
Кстати, если можно - еще хотя бы несколько тестов приведи...
Volvo, и на твой вопрос ответ судя по всему тоже да, ибо в примере сначала была перевернута вся последовательность, а потом кусок из середины
Тогда есть высокая (очень высокая) вероятность того, что ВСЕГДА можно исходную последовательность привести к результату. За исключением случаев, когда в исходной последовательности всего одна единица.
Кстати, приведенный пример решается так:
исходная:
011010010
010101010 = результат...
Так что... Перекрывающихся подпоследовательностей не было. Вопрос в силе.
Извиняюсь, пример действительно неудачный.Переворачивать можно сколько угодно раз и как угодно.
Другие тесты:
1)Вход:
9
100011100
001011001
Выход:
Да
6 9
3 8
1 5
2)Вход:
7
1001001
Изменить невозможно
3)Вход:
7
11001101
10101101
Выход:
Нет
У меня вот такой алгоритм получился:
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.
В условии сказано: подпоследовательностей с четным кол-вом единиц.
Это значит, что любой нолик можно перевернуть, правильно? Это ведь подпоследовательность длины 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
>1. Переворачивать, не значит менять 0 на 1 и обратно.
мдя. что есть то есть
>с четным количеством элементов последовательности
Ну там сказано не элементов, а именно единиц. Т.е. в переворачиваемой последовательности количество элементов, равных единице, должно быть четным.
Сорри за неправильную интерпретацию.
Надеюсь, теперь я правильно понял условие
Понятно, что преобразования у нас транзитивные и обратимые.
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 возможным значениям инварианта.
Поэтому мы доказали, что, если сведя обе входные строки к каноническому виду, мы получили разные результаты, то ответ – "нет".
Кстати, случай, когда количество единиц в строках отличается (или отличается длина строк), учитывать отдельно не нужно – канонические виды тоже получатся разными
А эту задачу можно сдать на каком-нибудь онлайн архиве?
>Найдешь преобразование, переводящее из А в С?
А чего придираться?
Понятно, что я имел ввиду, что преобразование - это цепочка переворотов, а не один переворот. Т.е. "если из строки А путем нескольких переворотов ..." и т. д.
>транзитивность ты и не используешь
В том то и дело, что использую. Использую для того, чтобы канонический вид имел право выступать в качестве промежуточного звена. Если бы транзитивности у преобразований не было (преобразований, очевидно, в смысле цепочек переворотов), то от канонического вида толку б не было.
> > Найдешь преобразование, переводящее из А в С?
> А чего придираться?
???
> Понятно, что я имел ввиду, что преобразование - это цепочка переворотов,
> а не один переворот. Т.е. "если из строки А путем нескольких переворотов ..." и т. д.
Вообще, транзитивность обычно не применяется к бинарным операциям. Обычно это свойство операций сравнения (a<b, b<c => a<c). Я просто попытался распространить это на бинарные операции (что, впрочем, не имеет особого смысла, так как в группах выражается свойством принадлежности результата операции к группе). То, что ты имел в виду на самом деле означает, что если операцию удалось произвести два раза, то это можно повторить - что настолько очевидно, что непонятно, у кого может возникнуть вопрос. Попробуй перенести свое понятие на обычные числа (скажем, на группу целых чисел по сложению), и ты поймешь, что это "свойство" абсолютно ничего не добавляет
> >транзитивность ты и не используешь
> В том то и дело, что использую. Использую для того, чтобы канонический вид
> имел право выступать в качестве промежуточного звена. Если бы транзитивности
> у преобразований не было (преобразований, очевидно, в смысле цепочек
> переворотов), то от канонического вида толку б не было.
Повторяю, речь идет только о возможности выполнять законные преобразования, которая, конечно, есть всегда. Существования обратной операции вполне достаточно. Подумай над этим.
В целом решение интересное, но некоторые моменты мне не ясны..
Ты пишешь:
> плавающая единица образует две группы, одна из которых
> обязательно будет четной, а другая нечетной,
А почему это? Известно, что количество нулей сохраняется, и если оно изначально было четным, то будет четным и в конце. Соответственно, оно будет разбито на чет-чет или нечет-нечет..
Что я упустил?
> > > Найдешь преобразование, переводящее из А в С?
> > А чего придираться?
> ???
Сорри, слегка грубовато, но мне кажется очевидным, какую "транзитивность" имел ввиду я. Ну и понятно, что я не стал бы утверждать, что один переворот транзитивен в смысле твоего контрпримера.
>и ты поймешь, что это "свойство" абсолютно ничего не добавляет
ок, я согласен с некоторой аксиоматичностью этого свойства. Мне все же кажется, что так оно, все таки, нагляднее - можем из А получить канон., из В получить канон (=> по обратимости можем из канон. получить В), потому, по транзитивности, из А можем В.
Согласен, что транзитивность можно было при этом не упоминать.
Ну вы и монстры, блин
Michael_Rybak
Алгоритм интересный, но в реализации будет наверное громоздким. Но у него есть преимущество перед моим - "да" или "нет" он скажет до вывода результата, у меня вычисляется в процессе. Хотя мой тоже можно переделать (просто прогнать 2 раза: 1 раз для "да"-"нет", второй раз результат )
Мне непонятен только вот этот пример:
2)Вход:
7
1001001
Изменить невозможно
Почему невозможно, если можно так: 1001001, 1001001 и т.д. ?
{$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.
я нашел тест который не работает через вышеуказанный алгоритм
вот такой:
6
111000010
001110100