Blestemul faraonilor
(Timisoara,pregatire, feb.1996)

  Triunghiul regal are ca varfuri centrele bazelor a trei piramide. Undeva in
acest triunghi se afla ascunsa comoara faraonilor. Blestemul faraonillor consta
in faptul ca orice cautator de comori, odata aflat intr-un punct din triunghiul
regal, va putea avea drept pozitie urmatoare doar mijloacele celor trei
segmente ce unesc acest punct cu varfurile triunghiului. Initial, cautatorul
de comori se afla pe una din laturile triunghiului (inclusiv varfurile). Se 
considera ca el a gasit comoara daca ajunge intr-o pozitie ce coincide cu cea 
a comorii.
  Dandu-se coordonatele triunghiului regal, ale comorii si ale punctului de
plecare, se cere:
        a. sa se determine daca pozitia comorii este accesibila cautatorului
           de comori; in caz afirmativ sa se descrie drumul parcurs de
           cautator indicand pozitiile succesive pe care le ocupa;
        b. sa se indice, daca exista, o pozitie in care sa fie ascunsa comoara
           astfel incat cautatorul sa nu o poata gasi pornind din punctul de
           plecare.
  Fisierul de intrare ziua10_2.inp contine mai multe seturi de date fiecare pe
un rand. Un set de date contine 5 perechi de numere naturale reprezentand 
coordonatele triughiului regal, ale comorii si respectiv ale punctului de 
plecare.
  Pentru un set de date de intrare iesirea corespunzatoare din fisierul 
ziua10_2.out contine: pentru punctul a. raspunsul DA sau NU dupa cum comoara 
este accesibila sau nu; in caz afirmativ pe urmatoarea linie - numarul n de 
pozitii care formeaza drumul si pe urmatoarele n linii coordonatele acestor 
pozitii; pentru punctul b. coordonatele pozitiei cerute daca exista sau mesajul
"Nu exista" in caz contrar.
Obs. Consideram ca se lucreaza numai cu numere intregi. In acest sens in loc de 
media aritmetica a doua numere naturale se va considera partea intreaga a 
semisumei lor.
Exemplu.
pentru setul de date de intrare:
0 1 4 1 2 3 2 2 2 1
iesirea este:
DA
2
2 1
2 2
Nu exista
===============================

Solutia 1 (Ovidiu ghiorghioiu)
program Faraoni;
  var t:packed array[1..3,1..2] of integer;
      c:packed array[1..2] of integer;
      p:packed array[1..2] of integer;
      vp:packed array[0..511,0..1] of set of byte;
      ch:boolean;
      i,j,k,ii,jj,minx,maxx,miny,maxy:integer;
  procedure Citire;
    var f:text;
        i:byte;
    begin
      assign(f,'faraoni.in');
      reset(f);
      readln(f,t[1,1],t[1,2],t[2,1],t[2,2],t[3,1],t[3,2],c[1],c[2],p[1],p[2]);
      minx:=511;
      maxx:=0;
      miny:=511;
      maxy:=0;
      for i:=1 to 3 do
        begin
          if t[i,1]<minx then minx:=t[i,1];
          if t[i,1]>maxx then maxx:=t[i,1];
          if t[i,2]<miny then miny:=t[i,2];
          if t[i,2]>maxy then maxy:=t[i,2]
        end;
      close(f)
    end;
  begin
    Citire;
    fillchar(vp,sizeof(vp),0);
    vp[p[1],p[2] div 256]:=vp[p[1],p[2] div 256]+[p[2] mod 256];
    repeat
      ch:=false;
      for i:=minx to maxx do
        for j:=miny to maxy do
          if (j mod 256 in vp[i,j div 256]) then
            begin
              for k:=1 to 3 do
                begin
                  ii:=(i+t[k,1]) div 2;
                  jj:=(j+t[k,2]) div 2;
                  if not (jj mod 256 in vp[ii,jj div 256]) then
                    begin
                      vp[ii,jj div 256]:=vp[ii,jj div 256]+[jj mod 256];
                      ch:=true
                    end;
                end;
            end;
    until not ch or (c[2] mod 256 in vp[c[1],c[2] div 256]);
    if ch then write('Da')
          else write('Nu');
    readln
  end.
-------------------------------
