KANAP104.PAS

{ MK 2002                    }
{ Mantas Kanaporis           }
{ Vilniaus Ïemynos gimnazija }
{ -------------------------- }
{ X skyrius                  }
{ 4 uØdavinys                }

{ ID¸JA yra pritaikyti tÐ patÔ paieÕkos Ô gylÔ metodÐ. PaieÕkos nutraukimo
  sÐlyga (ribinis atvejis) yra galutinio ØodØio prijungimas. Kas kartÐ
  naujai paimtas Øodis yra paØymimas, kad neimti jo kelis kartus. }

Program Kanap104;

Type
  Tzodziai = array [1 .. 20] of string; { ØodØiÖ masyvas }
  Tnum = set of 1 .. 20; { aibÓs tipas, reikalingas kintajam, ØyminÑiam,
                           panaudotus ØodØius metagramai }
var
  zodziai : Tzodziai; { duoti ØodØiai (pradiniai duom.) }
  viso : byte;        { duotÖ ØodØiÖ skaiÑius }
  galima : boolean;   { ar galima sudaryti metagramÐ }

{ nuskaitomi pradiniai duomenys }
procedure nuskaitymas (var viso : byte; var zodziai : Tzodziai);
var
  F : Text;
  ck : byte;
begin
  assign (f, 'meta.txt');
  reset (f);
  readln (f, viso);
  for ck := 1 to viso do
  readln (f, zodziai [ck]);
  close (f)
end;

{ ar ØodØius, kuriÖ nr. masyve yra eil1, eil2, galima sujungti metagrandine }
function meta (eil1, eil2 : byte) : boolean;
var
  ck,                   { pagalbinis ciklo kintamasis }
  skirtumai : integer;  { skirtumÖ tarp duotÖ ØodØiÖ skaiÑius }
begin
  if length (zodziai [eil1]) = length (zodziai [eil2]) then
  begin             { jei ØodØiÖ ilgiai vienodi ir jie skiriasi viena raide, }
    skirtumai := 0; { tai metagrandÔ sudaryti galime, kitaip - ne }
    for ck := 1 to length (zodziai [eil1]) do
    if zodziai [eil1] [ck] <> zodziai [eil2] [ck] then inc (skirtumai);
    if skirtumai = 1 then meta := true
                     else meta := false
  end
  else meta := false { jei ØodØiÖ ilgiai skiriasi, }
end;                 { sudaryti metegrandies nepavyks }

procedure paieska (nr : byte; num : Tnum; var galima : boolean);
var
  ck : byte;
begin
  if galima then exit; { jei nustatÓme, kad galima, neverta toliau ieÕkoti }
  if 2 in num then galima := true  { jei galima prijunti paskutinÔ ØodÔ, }
  else                             { tai ir paØymime }
  begin
    for ck := 2 to viso do                    { bandoma prijunti ØodÔ, }
    if not (ck in num) and meta (nr, ck) then { kuris dar nepanaudotas ir }
    paieska (ck, num + [ck], galima)          { tinkamas metagrandØiai }
  end
end;

begin
  nuskaitymas (viso, zodziai);

  galima := false;   { darom prielaidÐ, kad metagrandinÓs sudaryti negalim }
  paieska (1, [1], galima);

  if galima then writeln ('GALIMA')   { jei visgi galime, tai ir paraÕome }
            else writeln ('NEGALIMA') { jei ne - irgi paraÕome }
end.