Имеется набор микросхем и несколько универсальных переходников. Каждая микросхема имеет некоторое количество контактов с двух сторон. Переходник может соединить две микросхемы с различным числом контактов. Микросхемы соединяются правой стороной к левой. Ваша программа должна определить возможно ли их последовательное соединение.
Порядок ввода исходных данных:
N - число микросхем
K - число переходников
L1R1 - количество контактов с двух (L1 и R1) сторон
...
LNRN - количество контактов с двух (LN и RN) сторон
Порядок вывода результатов:
YES/NO
Ограничения:
0 < N < 11, 0 <= K, 0 <= LN,RN <= 9
Пример ввода
5
1
12
23
33
44
45
Пример вывода
YES
в лоб, но работает.
uses crt;
type t_chip = record
left : integer;
right : integer;
end;
const n = 5;
const k = 1;
type t_sequence = array [ 1..n ] of integer;
const chips: array[ 1..n ] of t_chip =
(
(left:1; right:2),
(left:2; right:3),
(left:3; right:3),
(left:4; right:4),
(left:4; right:5)
);
var sequence: t_sequence = (1, 2, 3, 4, 5);
var found: boolean = false;
procedure dump(const s: t_sequence );
var
i: integer;
begin
for i := 1 to n do write(s[i]:3);
writeln;
end;
procedure _swap(var seq: t_sequence; a, b: integer);
var
t: integer;
begin
t := seq[a];
seq[a] := seq[b];
seq[b] := t;
end;
function need_adapters( const seq: t_sequence ): integer;
var
i, count: integer;
begin
count := 0;
for i := 1 to n - 1 do
if ( chips[seq[i]].right <> chips[seq[i + 1]].left ) then
inc( count );
need_adapters := count;
end;
function find_sequence( idx: integer; seq : t_sequence ): boolean;
var
i, t, need_adp: integer;
begin
if ( found ) then exit; { для вывода всех решений убрать }
if ( idx = n ) then begin
need_adp := need_adapters( seq );
if ( need_adp <= k ) then begin
dump( seq );
found := true;
end;
end;
for i := n downto idx + 1 do begin
_swap( seq, idx + 1, i);
find_sequence( idx + 1, seq );
_swap( seq, idx + 1, i);
end;
end;
begin
clrscr;
find_sequence( 0, sequence );
if ( found ) then writeln('YES') else writeln('NO');
readln;
end.