Начало
Соревнования
3. Булева функция
Задача средней сложности.
Самый универсальный способ решения – использовать динамическое программирование.
Для этого заполняем таблицу `T_{ij}` максимальным количеством единиц среди `i` булевских значений, таких что результат цепного вычисления равен `j`. Для получения результата нужно выполнить обратную трассировку по таблице.
var
n,i,j,k,b:longint;
t,h1,h2:array[1..100000,0..1] of longint;
f:string;
s:array[1..100000] of integer;
begin
readln(n);
readln(f);
{ заполнение таблицы }
t[1,0]:=0;
t[1,1]:=1;
h2[1,0]:=0;
h2[1,1]:=1;
for i:=2 to n do
begin
t[i,0]:=-1;
t[i,1]:=-1;
for j:=0 to 1 do
for k:=0 to 1 do
begin
b:=ord(f[j*2+k+1])-ord('0'); { вычисляем значение f(j,k) }
if (t[i-1,j]>=0) and (t[i,b]<t[i-1,j]+k) then
begin
t[i,b]:=t[i-1,j]+k;
h1[i,b]:=j; { запоминаем способ }
h2[i,b]:=k; { получения результата }
end;
end;
end;
{ обратная трассировка }
if t[n,1]<0 then
writeln('No solution')
else
begin
j:=1;
for i:=n downto 1 do
begin
s[i]:=h2[i,j];
j:=h1[i,j];
end;
for i:=1 to n do
write(s[i]);
writeln;
end;
end.
Другой способ решения – рассмотреть все возможные варианты для функции `f`. Всего может быть 16 вариантов задания этой функции, но все они сводятся к следующим пяти случаям.
| Булева функция | Последовательность |
| ???1 | 111...111 |
| 1??0 | 111...110 |
| 01?0 | 111...101 для четных `n` и 111...111 для нечетных `n` |
| 0010 | 100...000 |
| 0000 | No solution |
