Описание
Булевой функцией называется функция, принимающая одно из логических значений TRUE или FALSE и зависящая от некоторого (быть может, нулевого) количества аргументов, каждый из которых также может принимать любое из значений TRUE или FALSE

Любая булева функция однозначно задается своей таблицей истинности, в которой для каждого возможного набора значений аргументов указано значение функции. Например, x AND y - булева функция от двух аргументов. Ее таблица истинности выглядит так:

xyx AND y
000
010
100
111

Если договориться, что наборы значений аргументов в таблице располагаются в лексикографическом порядке, то функция AND однозначно задается третьим столбцом таблицы - строкой 0001. Аналогично, каждой булевой функции от k аргументов можно поставить в соответствие строку из нулей и единиц длины 2k

Задача
Задан набор из N+1 булевой функции (f,f1,f2,...,fN). Напишите программу, которая определяет, можно ли функцию f выразить через функции f1,f2,...,fN, и если такие представления возможны, то находит кратчайшее по числу символов среди них


Входные данные
В первой строке входного файла записано целое число N (1≤N≤9). Последующие N+1 строк содержат описания функций f1,f2,...,fN соответственно. Каждая из функций описывается строкой символов так, как указано выше. Число аргументов у функции f будет не более двух, а у остальных функций - не более трех

Выходные данные
Первая строка выходного файла должна содержать искомое символьное представление, либо строку "Impossible", если такого представления не существует. После функции с нулевым числом аргументов скобки не ставятся. Если у функции f один аргумент, то он обозначается через x, а если два - через x и y соответственно


Например:

FBOOLEAN.IN
2
1
1010
0

FBOOLEAN.OUT
f1(f2,f2)





Идеи
Полный перебор, перебор с отсечением

Комментарии
Если у нас имеется некоторый набор функций, то мы можем подставлять одни функции в другие, получая тем самым новые функции. Например, из функций f1(x,y), f2(x,y) и f3(x,y) можно построить функцию f4(x,y)=f1(f2(y,x),f3(y,y)). Решение задачи заключается в том, чтобы подставлять функции друг в друга всевозможными способами.

 



 Решение

{$G+,F-,B-,O-,S-,R-,N-,E-}

program fboolean;
const
  infile = 'fboolean.in';
  outfile = 'fboolean.out';
  MaxN = 9;
type
  parr = array [0..3] of integer;
  bfn  = record
                    A  : integer;
                    X  : array [0..1,0..1,0..1] of byte
                  end;
  repr = record
                    bf : bfn;
                    sl : word;
                    rfn, ra1, ra2, ra3 : integer
                  end;
const Power : parr = (1, 2, 4, 8);
      Tower : parr = (2, 4, 16, 256);
 
var
  bool2 : array [0..255] of repr;
  N  : integer;
  f : bfn;
  fn : integer;
  fi : array [1..MaxN] of bfn;
 
procedure readbfn (var BF : bfn);
var S : string;
    i : integer;
begin with BF do begin
  readln (S);
  case S[0] of
  #1:  A:=0;
  #2:  A:=1;
  #4:  A:=2;
  #8:  A:=3
  else runerror(239)
  end;
  for i:=0 to pred(length(S)) do
    X[i shr 2, (i shr 1) and 1, i and 1] := ord(S[i+1]='1');
end end;
 
procedure initb0 (N : integer);
begin with bool2[N] do begin
  bf.A := 0;
  bf.X[0,0,0] := N;
  sl := 65535;
end end;
 
procedure initb1 (N : integer);
var i, L : integer;
begin with bool2[N] do begin
  bf.A := 1;
  L := N;
  for i:=0 to 1 do
    begin
      bf.X[0,0,i] := L shr 1;
      L := (L shl 1) and 3
    end;
  sl := 65535;
  if N = 1 then
    begin
      sl := 1;
      rfn := -1       {x}
    end
end end;
 
procedure initb2 (N : integer);
var i, L : integer;
begin with bool2[N] do begin
  bf.A := 2;
  L := N;
  for i:=0 to 3 do
    begin
      bf.X[0,i shr 1,i and 1] := L shr 3;
      L := (L shl 1) and 15
    end;
  sl := 65535;
  if N = 3 then
    begin
      sl := 1;
      rfn := -1       {x}
    end else
  if N=5 then
    begin
      sl := 1;
      rfn := -2       {y}
    end
end end;
 
procedure initb3 (N : integer);
var i, L : integer;
begin with bool2[N] do begin
  bf.A := 3;
  L := N;
  for i:=0 to 7 do
    begin
      bf.X[i shr 2,(i shr 1) and 1,i and 1] := L shr 7;
      L := (L shl 1) and 255
    end;
  sl := 65535;
  if N = $0f then
    begin
      sl := 1;
      rfn := -1       {x}
    end else
  if N= $33 then
    begin
      sl := 1;
      rfn := -2       {y}
    end else
  if N= $55 then
    begin
      sl := 1;
      rfn := -3       {z}
    end
end end;
 
function getnumber (var f : bfn) : integer;
var fn : integer;
begin
  case f.A of
  0:  fn := f.X[0,0,0];
  1:  fn := f.X[0,0,0]*2 + f.X[0,0,1];
  2:  fn := f.X[0,0,0]*8 + f.X[0,0,1]*4 + f.X[0,1,0]*2 + f.X[0,1,1];
  3:  fn := f.X[0,0,0]*128+f.X[0,0,1]*64+ f.X[0,1,0]*32+ f.X[0,1,1]*16 +
            f.X[1,0,0]*8 + f.X[1,0,1]*4 + f.X[1,1,0]*2 + f.X[1,1,1]
  end;
  getnumber := fn
end;
 
procedure getcomposition (var R : repr; var Fu : bfn; var A1, A2, A3 : repr);
var i, j, k : integer;
begin
  R.bf.A := f.A;
  case Fu.A of
  0:  begin
        R.sl := 2;
        case f.A of
        0:   R.bf.X[0,0,0] := Fu.X[0, 0, 0];
        1:   for i:=0 to 1 do
             R.bf.X[0,0,i] := Fu.X[0, 0, 0];
        2:   for i:=0 to 1 do for j:=0 to 1 do
             R.bf.X[0,i,j] := Fu.X[0, 0, 0];
        3:   for i:=0 to 1 do for j:=0 to 1 do for k:=0 to 1 do
             R.bf.X[i,j,k] := Fu.X[0, 0, 0]
        end
      end;
  1:  begin
        R.sl := 4 + A1.sl;
        case f.A of
        0:   R.bf.X[0,0,0] := Fu.X[0, 0, A1.bf.X[0, 0, 0]];
        1:   for i:=0 to 1 do
             R.bf.X[0,0,i] := Fu.X[0, 0, A1.bf.X[0, 0, i]];
        2:   for i:=0 to 1 do for j:=0 to 1 do
             R.bf.X[0,i,j] := Fu.X[0, 0, A1.bf.X[0, i, j]];
        3:   for i:=0 to 1 do for j:=0 to 1 do for k:=0 to 1 do
             R.bf.X[i,j,k] := Fu.X[0, 0, A1.bf.X[i,j,k]];
        end
      end;
  2:  begin
        R.sl := 5 + A1.sl + A2.sl;
        case f.A of
        0:   R.bf.X[0,0,0] := Fu.X[0, A1.bf.X[0, 0, 0], A2.bf.X[0, 0, 0]];
        1:   for i:=0 to 1 do
             R.bf.X[0,0,i] := Fu.X[0, A1.bf.X[0, 0, i], A2.bf.X[0, 0, i]];
        2:   for i:=0 to 1 do for j:=0 to 1 do
             R.bf.X[0,i,j] := Fu.X[0, A1.bf.X[0, i, j], A2.bf.X[0, i, j]];
        3:   for i:=0 to 1 do for j:=0 to 1 do for k:=0 to 1 do
             R.bf.X[i,j,k] := Fu.X[0, A1.bf.X[i,j,k], A2.bf.X[i,j,k]];
        end
      end;
  3:  begin
        R.sl := 6 + A1.sl + A2.sl + A3.sl;
        case f.A of
        0:   R.bf.X[0,0,0] := Fu.X[A1.bf.X[0, 0, 0], A2.bf.X[0, 0, 0], A3.bf.X[0, 0, 0]];
        1:   for i:=0 to 1 do
             R.bf.X[0,0,i] := Fu.X[A1.bf.X[0, 0, i], A2.bf.X[0, 0, i], A3.bf.X[0, 0, i]];
        2:   for i:=0 to 1 do for j:=0 to 1 do
             R.bf.X[0,i,j] := Fu.X[A1.bf.X[0, i, j], A2.bf.X[0, i, j], A3.bf.X[0, i, j]];
        3:   for i:=0 to 1 do for j:=0 to 1 do for k:=0 to 1 do
             R.bf.X[i,j,k] := Fu.X[A1.bf.X[i,j,k], A2.bf.X[i,j,k], A3.bf.X[i,j,k]];
        end
      end
  end
end;
 
var ed : boolean;
    R  : repr;
procedure try (z, A1, A2, A3 : integer);
var N : integer;
begin
  N := fi[z].A;
  if (N > 0) and (bool2[A1].sl = 65535) then exit;
  if (N > 1) and (bool2[A2].sl = 65535) then exit;
  if (N > 2) and (bool2[A3].sl = 65535) then exit;
  getcomposition (R, fi[z], bool2[A1], bool2[A2], bool2[A3]);
     { R := F (A1, A2, A3) }
  R.rfn := z;
  N := getnumber (R.bf);
  if bool2[N].sl > R.sl then
    begin
      R.ra1 := A1;
      R.ra2 := A2;
      R.ra3 := A3;
      bool2[N] := R;
      ed := true
    end
end;
 
function step : boolean;
var k, i1, i2, i3, tf : integer;
begin
  ed := false;
  tf := pred(tower[f.A]);
  for k:=1 to N do
    with fi[k] do
      case A of
      0:  try (k, 0, 0, 0);
      1:  for i1:=0 to tf do try (k, i1, 0, 0);
      2:  for i1:=0 to tf do
            for i2:=0 to tf do
              try (k, i1, i2, 0);
      3:  for i1:=0 to tf do
            for i2:=0 to tf do
              for i3:=0 to tf do
                try (k, i1, i2, i3);
      end;
  step := ed
end;
 
procedure writeexpr (N : integer);
var
  k  : integer;
begin with bool2[N] do begin
  if rfn = -1 then write ('x') else
  if rfn = -2 then write ('y') else
  if rfn = -3 then write ('z');
  if rfn < 0 then exit;
  write ('f',rfn);
  k := fi[rfn].A;
  if k = 0 then exit;
  write ('(');
  writeexpr (ra1);
  if k > 1 then begin write (','); writeexpr (ra2) end;
  if k > 2 then begin write (','); writeexpr (ra3) end;
  write (')')
end end;
 
 
var i : integer;
begin
  assign (input, infile); reset (input);
  readln (N);
  readbfn (f);
  for i:=1 to N do readbfn (fi[i]);
  case f.A of
  0:  for i:=0 to 1 do initb0 (i);
  1:  for i:=0 to 3 do initb1 (i);
  2:  for i:=0 to 15 do initb2 (i);
  3:  for i:=0 to 255 do initb3 (i)
  else runerror (239);
  end;
  fn := getnumber (f);
 
  repeat until not step;
  assign (output, outfile); rewrite (output);
  if bool2[fn].sl = 65535 then write ('Impossible')
                          else writeexpr (fn);
  writeln;
  close(input); close(output)
end.

 

© Особенности национальных задач по информатике