Задача на логику Опции

[Tenshi]

В парламенте острова Невезения каждый из N = 6 депутатов имеет не более М = 2 врагов. ( Если А - враг Б, то Б - враг А). Для уменьшения разногласий президент решил преобразовать парламент в двухпалатный.
Составить программу, которая проверяет, можно ли парламент разделить на две палаты так, что быу каждого депутата в своей палате было не более М врагов.

[klem4]

const
  n = 6;
type
  TEnemies = set of byte;
  TRelationship = array [1..n] of TEnemies;

function Intersect(const i, j, k: byte; const
 iSet, jSet, kSet: TEnemies): boolean;
begin
  Intersect := (i in jSet + kSet) or (j in iSet + kSet) or (k in iSet + jSet);
end;

var
  r: TRelationship = (
    ([]),     // враги первого (пусто в данном случае)
    ([4]),    // враги второго
    ([4, 5]), // 3
    ([3, 2]), // 4
    ([3]),    // 5
    ([])      // 6
  );

  i, j, k, l, id: byte;
  idx: array [1..3] of byte;

begin
  for i := 1 to n - 2 do
   for j := i + 1 to n - 1 do
    for k := j + 1 to n do
     if not Intersect(i, j, k, r[i], r[j], r[k]) then begin
       id := 0;
       for l := 1 to n do
        if (l <> i) and (l <> j) and (l <> k) then begin
          inc(id); idx[id] := l;
        end;
        if not Intersect(idx[1], idx[2], idx[3], r[idx[1]], r[idx[2]], r[idx[3]]) then
         writeln('Group A: (', i, ',', j, ',', k,
               ') Group B: (', idx[1], ',', idx[2], ',', idx[3], ')');
     end;
end.

Сообщение отредактировано: klem4 - 23.05.2008 11:04