Difference between revisions of "Psihologia concursurilor de informatică/6 Probleme de concurs 1"

From Algopedia
Jump to: navigation, search
 
(3 intermediate revisions by the same user not shown)
Line 1: Line 1:
 
⇦ înapoi la [[Psihologia concursurilor de informatică]]
 
⇦ înapoi la [[Psihologia concursurilor de informatică]]
  
= Capitolul VI: Probleme de concurs =
+
= Capitolul VI: Probleme de concurs (1-6) =
  
 
== Problema 1 ==
 
== Problema 1 ==
Line 869: Line 869:
 
}
 
}
 
</syntaxhighlight>
 
</syntaxhighlight>
 +
  
 
== Problema 4 ==
 
== Problema 4 ==
Line 1,054: Line 1,055:
  
 
Programul prezentat mai sus poate fi optimizat, dacă timpul o permite și dacă acest lucru este necesar. Lăsăm cititorul să încerce să rezolve aceeași problemă folosind o cantitatate de memorie direct proporțională cu '''''N'''''.
 
Programul prezentat mai sus poate fi optimizat, dacă timpul o permite și dacă acest lucru este necesar. Lăsăm cititorul să încerce să rezolve aceeași problemă folosind o cantitatate de memorie direct proporțională cu '''''N'''''.
 +
 +
 +
== Problema 5 ==
 +
 +
Această problemă a fost propusă la Olimpiada Națională de Informatică, Slatina 1995, la clasa a XI-a. Pe atunci programarea dinamică era o tehnică de programare destul de puțin cunoscută de către majoritatea elevilor.
 +
 +
'''ENUNȚ''': O regiune deșertică este reprezentată printr-un tablou de dimensiuni '''''M'''''x'''''N''''' (1 ≤ '''''M''''' ≤ 100, 1 ≤ '''''N''''' ≤ 100). Elementele tabloului sunt numere naturale mai mici ca 255, reprezentând diferențele de altitudine față de nivelul mării (cota 0). Să se stabilească:
 +
 +
a) Un traseu pentru a traversa deșertul de la nord la sud (de la linia 1 la linia '''''M'''''), astfel:
 +
 +
* Se pornește dintr-un punct al liniei 1;
 +
* Deplasarea se poate face în una din direcțiile: E, SE, S, SV, V;
 +
* Suma diferențelor de nivel (la urcare și la coborâre) trebuie să fie minimă.
 +
 +
b) Un traseu pentru a traversa deșertul de la nord la sud în condițiile punctului (a), la care se adaugă condiția:
 +
 +
* Lungimea traseului să fie minimă.
 +
 +
'''Intrarea''': Fișierul de intrare <tt>INPUT.TXT</tt> conține un singur set de date cu următoarea structură:
 +
 +
{|class="wikitable"
 +
| linia 1: || '''''M N'''''
 +
|-
 +
| linia 2 ... linia '''''M'''''+1: || elementele tabloului (pe linii) separate prin spații
 +
|}
 +
 +
'''Ieșirea''': Fișerul de ieșire <tt>OUTPUT.TXT</tt> va conține rezultatele în următorul format:
 +
 +
(a)<br>
 +
<suma diferențelor de nivel><br>
 +
TRASEU: <math>(i_1,j_1)\to(i_2,j_2)\to\cdots\to(i_k,j_k)</math><br>
 +
(b)<br>
 +
<suma diferențelor de nivel> <lungime traseu><br>
 +
TRASEU: <math>(i_1,j_1)\to(i_2,j_2)\to\cdots\to(i_p,j_p)</math>
 +
 +
 +
unde <math>i_x</math> și <math>j_x</math> sunt linia și coloana fiecărei celule vizitate.
 +
 +
'''Exemplu''':
 +
 +
{|class="wikitable
 +
! <tt>INPUT.TXT</tt> ||  <tt>OUTPUT.TXT</tt>
 +
|-
 +
| <tt>4 4<br>
 +
10 7 2 5<br>
 +
13 20 25 3<br>
 +
2 4 2 20<br>
 +
5 10 9 11<br></tt>
 +
| <tt>(a)<br>
 +
5<br>
 +
TRASEU: (1,3)->(2,4)->(3,3)->(3,2)->(4,1)<br>
 +
(b)<br>
 +
9 3<br>
 +
TRASEU: (1,3)->(2,4)->(3,3)->(4,2)<br></tt>
 +
|}
 +
 +
Acesta a fost enunțul original. Iată acum completările propuse și o precizare importantă:
 +
 +
* '''Timpul de implementare''': 45 minute - 1h (la concurs a fost cam 1h 30 min);
 +
* '''Timpul de rulare''': 2-3 secunde;
 +
* '''Complexitatea cerută''': <math>O(N^2)</math>;
 +
* La punctul (b), condiția nou adăugată este mai puternică decât cea de la punctul (a). Cu alte cuvinte, în primul rând contează lungimea drumului și abia apoi, dintre toate drumurile de lungime minimă, trebuie ales cel pentru care suma denivelărilor este minimă. Pentru a vă convinge că ordinea în care sunt impuse condițiile este importantă, să privim exemplul de mai sus. Dacă este mai importantă minimizarea sumei denivelărilor, atunci minimul este 5, iar drumul este soluția de la punctul (a). Dacă este mai importantă minimizarea lungimii drumului, atunci lungimea minimă este 3, iar din toate drumurile de lungime 3, cel mai puțin costisitor este cel indicat la punctul (b).
 +
 +
'''REZOLVARE''': Vom lăsa punctul (b) al acestei probleme în seama cititorului, întrucât el nu este altceva decât o simplificare a punctului (a). Să ne ocupăm acum de punctul (a). Vom numi efort diferența de altitudine (în modul) la deplasarea cu un pas. Scopul este deci găsirea unor drumuri de efort total minim. Matricea de altitudini o vom nota cu <tt>Alt</tt>.
 +
 +
O primă posibilitate de abordare a problemei este „greedy”, dar aceasta nu e cea mai fericită alegere, chiar dacă este una comodă. Ideea de bază este următoarea: Încercăm să pornim din colțul de NV și să ne deplasăm la fiecare pas pe acea direcție pentru care efortul este minim, până ajungem la ultima linie. Apoi pornim din a doua coloană a primei linii și aplicăm aceeași tactică, apoi din a treia coloană și așa mai departe până la colțul de NE. În final tipărim soluția cea mai bună găsită. Iată însă un exemplu pe care această metodă dă greș:
 +
 +
<math>
 +
Alt=
 +
\begin{pmatrix}
 +
2 & 1 & 2 \\
 +
10 & 1 & 10 \\
 +
10 & 10 & 10
 +
\end{pmatrix}
 +
</math>
 +
 +
Pe această matrice, algoritmul greedy va găsi traseele (1,1) → (2,2) → (3,2) de efort total 10, (1,2) → (2,2) → (3,2) de efort total 9 și (3,1) → (2,2) → (3,2) de efort total 10. Așadar, rezultatul optim ar fi 9, ceea ce este fals deoarece alegerea traseului (1,1) → (2,1) → (3,1) ar duce la un efort total de 8, deci mai mic.
 +
 +
Motivul pentru care acest algoritm nu funcționează cum trebuie este că el nu privește în perspectivă. În cazul de mai sus, coborârea în „văile” de altitudine 1 era o primă mutare tentantă, dar fără nici un rezultat, deoarece până la urmă tot era necesară suirea la altitudinea 10. Soluția corectă este ca, pentru a afla efortul minim cu care se poate ajunge la o locație oarecare, să analizăm toate drumurile care duc la acea locație. Dacă am cunoaște efortul minim cu care se poate ajunge la fiecare din vecinii din E, NE, N, NV, și V ai unei celule, atunci putem cu ușurință, pe baza unor comparații, să deducem din ce parte este cel mai avantajos să venim în respectiva celulă și cu ce efort minim.
 +
 +
Mai concret, vom construi o matrice cu aceleași dimensiuni ca și matricea <tt>Alt</tt>, pe care o vom denumi <tt>Eff</tt>. În această matrice, <tt>Eff[i,j]</tt> reprezintă efortul minim necesar pentru a ajunge de pe un punct oarecare de pe linia 1 în celula ('''''i''''','''''j'''''). Deducem că <tt>Eff[1,j]</tt>=0, ∀ 1 ≤ '''''j''''' ≤ '''''N'''''. Noi trebuie să completăm matricea <tt>Eff</tt>, apoi să căutăm minimul dintre toate elementele de pe linia '''''M''''' (care este chiar efortul minim căutat) și să reconstituim traseul de urmat.
 +
 +
Ca să vedem cum anume se face completarea matricei, facem mai întâi observația că, odată ce am ajuns pe o linie, putem fie să coborâm direct pe linia imediat inferioară, fie să ne deplasăm câțiva pași numai spre stânga sau numai spre dreapta, apoi să coborâm pe linia următoare. În orice locație ('''''X''''','''''Y''''') a matricei putem veni dinspre E, NE, N, NV, sau V. Pentru acești cinci vecini presupunem deja calculate eforturile minime necesare, respectiv <tt>Eff[X,Y+1], Eff[X-1,Y+1], Eff[X-1,Y], Eff[X-1,Y-1], Eff[X,Y-1]</tt>. Atunci, în funcție de direcția din care venim, efortul depus până la punctul ('''''X''''','''''Y''''') va fi:
 +
 +
{|
 +
| dinspre est:      || <tt>Eff[X,Y+1]+ |Alt[X,Y+1] - Alt[X,Y]|</tt>; || (1)
 +
|-
 +
| dinspre nord-est:  || <tt>Eff[X-1,Y+1]+ |Alt[X-1,Y+1] - Alt[X,Y]|</tt>; || (2)
 +
|-
 +
| dinspre nord:      || <tt>Eff[X-1,Y]+ |Alt[X-1,Y] - Alt[X,Y]|</tt>; || (3)
 +
|-
 +
| dinspre nord-vest: || <tt>Eff[X-1,Y-1]+ |Alt[X-1,Y-1] - Alt[X,Y]|</tt>; ||  (4)
 +
|-
 +
| dinspre vest:      || <tt>Eff[X,Y-1]+ |Alt[X,Y-1] - Alt[X,Y]|;</tt> ||  (5)
 +
|}
 +
 +
În principiu, nu avem decât să calculăm minimul dintre aceste expresii ca să aflăm valoarea lui <tt>Eff[X,Y]</tt>. În felul acesta, matricea <tt>Eff</tt> se va completa pe linie, de sus în jos. Totuși, apare o problemă: pentru a-l afla pe </tt>Eff[X,Y]</tt> avem nevoie de <tt>Eff[X,Y-1]</tt> (dacă ne deplasăm spre est), iar pentru a-l afla pe <tt>Eff[X,Y-1]</tt> avem nevoie de <tt>Eff[X,Y]</tt> (dacă ne deplasăm spre vest)! Bineînțeles, avem sentimentul că ne învârtim după propria coadă. Totuși, dezlegarea nu e complicată, ținând cont de observația făcută mai sus, că pe aceeași linie deplasarea se face într-o singură direcție. Este suficient să parcurgem fiecare linie de două ori: prima oară o parcurgem de la stânga la dreapta, în ipoteza că deplasarea pe linia respectivă se face spre est, apoi încă o dată de la dreapta la stânga, în ipoteza că deplasarea pe linia respectivă se face spre vest. La prima parcurgere, vom minimiza efortul pentru fiecare căsuță cu expresia (5), iar la a doua - cu expresia (1). Minimizarea cu expresiile (2), (3) și (4) se poate face la oricare din parcurgeri, deoarece elementele liniei superioare nu se mai modifică.
 +
 +
După cum am spus, efortul minim se obține căutând minimul de pe ultima linie a matricei <tt>Eff</tt> (aceasta deoarece nu contează în ce punct de pe ultima linie este sosirea). Punctul în  care se atinge acest minim este tocmai punctul de sosire. Reconstituirea efectivă a drumului se face în sens invers: se pleacă din  punctul de sosire <math>(i_k,j_k)</math> și se caută un punct vecin lui pe una din cele cinci direcții permise, <math>(i_{k-1},j_{k-1})</math> astfel încât
 +
 +
<math>
 +
\mathit{Eff}[i_k,j_k] = \mathit{Eff}[i_{k-1},j_{k-1}] + |Alt[i_k,j_k] - Alt[i_{k-1},j_{k-1}]|
 +
</math>
 +
 +
Cu alte cuvinte, se testează pentru care din expresiile (1) - (5) se verifică egalitatea. Se reia, recursiv, același procedeu pentru locația <math>(i_{k-1},j_{k-1})</math>.
 +
 +
Iată cum se completează matricea <tt>Eff</tt> pentru exemplul dat și cum se reconstituie drumul:
 +
 +
<math>
 +
Alt =
 +
\begin{pmatrix}
 +
10 &  7 &  2 &  5 \\
 +
13 & 20 & 25 &  3 \\
 +
2 &  4 &  2 & 20 \\
 +
5 & 10 &  9 & 11
 +
\end{pmatrix}
 +
</math>
 +
 +
<math>
 +
\mathit{Eff} =
 +
\begin{pmatrix}
 +
0 &  0 &  0 &  0 \\
 +
3 & 10 & 15 &  1 \\
 +
6 &  4 &  2 & 18 \\
 +
5 & 10 &  9 & 11
 +
\end{pmatrix}
 +
</math>
 +
 +
Minimul de pe linia a 4-a a matricei <tt>Eff</tt> este <tt>Eff[4,1]=5</tt>, deci sosirea se face în colțul de SV. Din ce parte am ajuns aici ? Se testează toți vecinii și se constată că <tt>Eff[4,1] = Eff[3,2] + |Alt[4,1] - Alt[3,2]|</tt>, deci s-a venit de la locația (3,2). Apoi se constată că:
 +
 +
* <tt>Eff[3,2] = Eff[3,3] + |Alt[3,2] - Alt[3,3]|</tt>;
 +
* <tt>Eff[3,3] = Eff[2,4] + |Alt[3,3] - Alt[2,4]|</tt>;
 +
* <tt>Eff[2,4] = Eff[1,3] + |Alt[2,4] - Alt[1,3]|</tt>;
 +
 +
Din aceste relații rezultă că traseul urmat este (1,3) → (2,4) → (3,3) → (3,2) → (4,1).
 +
 +
Pentru o mai mare ușurință a implementării, se vor adăuga două coloane fictive la matricea <tt>Alt</tt>: coloanele 0 și '''''N'''''+1. Facem acest lucru pentru a ne putea referi la celula ('''''X''''','''''Y'''''-1) atunci când ('''''X''''','''''Y''''') este o celulă din prima coloană (respectiv la celula ('''''X''''','''''Y'''''+1) atunci când ('''''X''''','''''Y''''') este o celulă de pe ultima coloană) fără a primi un mesaj de eroare. Trebuie însă să fim atenți ca nu cumva noile coloane adăugate să perturbe datele de ieșire și să rezulte că traseul optim trece prin coloana 0 sau '''''N'''''+1. Pentru a scăpa de grija celulelor de pe aceste două coloane și a ne asigura că ele nu vor putea fi selectate pentru traseul optim, le vom atribui altitudini foarte mari. Deoarece diferența maximă de nivel la fiecare pas este 255, rezultă că efortul total maxim ce se poate obține este 255 x 99 = 25.245. Așadar, o altitudine a coloanelor laterale de 30.000 este suficientă.
 +
 +
<syntaxhighlight lang="c">
 +
#include <stdio.h>
 +
#include <math.h>
 +
#define NMax 101
 +
#define Infinity 30000
 +
typedef int Matrix[NMax][NMax+1];
 +
 +
Matrix Alt, Eff;
 +
int M, N;
 +
FILE *OutF;
 +
 +
void ReadData(void)
 +
{ FILE *F=fopen("input.txt", "rt");
 +
  int i,j;
 +
 +
  fscanf(F, "%d %d\n", &M, &N);
 +
  for (i=1; i<=M; i++)
 +
    for (j=1; j<=N; j++)
 +
      fscanf(F, "%d", &Alt[i][j]);
 +
  fclose(F);
 +
}
 +
 +
void Optimize(int X1, int Y1, int X2, int Y2)
 +
/* Testeaza daca in (X1,Y1) se poate ajunge
 +
  cu efort mai mic dinspre (X2,Y2) */
 +
{
 +
  if (Eff[X2][Y2]+abs(Alt[X1][Y1]-Alt[X2][Y2])<Eff[X1][Y1])
 +
    Eff[X1][Y1]=Eff[X2][Y2]+abs(Alt[X1][Y1]-Alt[X2][Y2]);
 +
}
 +
 +
void Traverse(void)
 +
{ int i,j;
 +
 +
  for (j=1; j<=N;) Eff[1][j++]=0;
 +
  for (i=1; i<=M; i++)
 +
    Eff[i][0]=Eff[i][N+1]=Infinity; /* Bordeaza matricea */
 +
  for (i=2; i<=M; i++)
 +
    {
 +
      for (j=1; j<=N; j++)
 +
        {
 +
          Eff[i][j]=Infinity;
 +
          Optimize(i, j, i-1, j);      /* De la N  */
 +
          Optimize(i, j, i-1, j-1);    /* De la NV */
 +
          Optimize(i, j, i-1, j+1);    /* De la NE */
 +
          Optimize(i, j, i, j-1);      /* De la V  */
 +
        }
 +
      for (j=N; j; j--)
 +
        Optimize(i, j, i, j+1);        /* De la E  */
 +
    }
 +
}
 +
 +
void GoBack(int X, int Y)
 +
/* Reconstituie drumul */
 +
{
 +
  if (X>1)
 +
    if (Eff[X][Y]==Eff[X][Y-1]
 +
                  +abs(Alt[X][Y-1]-Alt[X][Y]))
 +
    GoBack(X, Y-1);
 +
    else if (Eff[X][Y]==Eff[X-1][Y-1]
 +
                        +abs(Alt[X-1][Y-1]-Alt[X][Y]))
 +
    GoBack(X-1, Y-1);
 +
    else if (Eff[X][Y]==Eff[X-1][Y]
 +
                        +abs(Alt[X-1][Y]-Alt[X][Y]))
 +
    GoBack(X-1, Y);
 +
    else if (Eff[X][Y]==Eff[X-1][Y+1]
 +
                        +abs(Alt[X-1][Y+1]-Alt[X][Y]))
 +
    GoBack(X-1, Y+1);
 +
    else if (Eff[X][Y]==Eff[X][Y+1]
 +
                        +abs(Alt[X][Y+1]-Alt[X][Y]))
 +
    GoBack(X, Y+1);
 +
  if (X>1) fprintf(OutF, "->");
 +
  fprintf(OutF,"(%d,%d)", X, Y);
 +
}
 +
 +
void WriteSolution(void)
 +
{ int j,k;
 +
 +
  OutF=fopen("output.txt", "wt");
 +
  /* Cauta punctul de sosire */
 +
  fputs("(a)\n",OutF);
 +
  for (j=2, k=1; j<=N; j++)
 +
    if (Eff[M][j]<Eff[M][k]) k=j;
 +
  fprintf(OutF, "%d\n", Eff[M][k]);
 +
  fputs("TRASEU: ",OutF);
 +
  GoBack(M, k);
 +
  fprintf(OutF,"\n");
 +
  fclose(OutF);
 +
}
 +
 +
void main(void)
 +
{
 +
  ReadData();
 +
  Traverse();
 +
  WriteSolution();
 +
}
 +
</syntaxhighlight>
 +
 +
 +
== Problema 6 ==
 +
 +
Propunem în continuare o problemă care s-a dat la Olimpiada Națională de Informatică, Suceava 1996, la clasa a XII-a. Menționăm că un singur concurent a reușit să o ducă la bun sfârșit în timpul concursului. Problema se numește „Cartierul Enicbo”.
 +
 +
'''ENUNȚ''': În orașul Acopan s-a construit un nou cartier. Noul cartier are patru bulevarde paralele și un număr de '''''N''''' străzi perpendiculare pe ele. Există deci în total 4'''''N''''' intersecții. Furgoneta oficiului poștal trebuie să distribuie poșta în fiecare zi; în acest scop, furgoneta pleacă de la oficiul poștal aflat la intersecția bulevardului 1 cu strada 1 și, urmând rețeaua stradală, trece exact o dată prin fiecare intersecție astfel încât să încheie traseul în punctul de plecare.
 +
 +
Conducerea oficiului poștal roagă participanții la olimpiadă să o ajute să afle în câte moduri distincte se poate stabili traseul furgonetei.
 +
 +
'''Intrarea''': Programul va citi de la tastatură valoarea lui '''''N''''' (2 ≤ '''''N''''' ≤ 200).
 +
 +
'''Ieșirea''': Pe ecran se va afișa soluția (numărul de trasee distincte pentru valoarea respectivă a lui '''''N''''').
 +
 +
'''Exemplu''': Pentru '''''N'''''=3 există 4 soluții (se citește de la tastatură numărul 3 și se afișează pe ecran numărul 4). Iată soluțiile efective:
 +
 +
[[File:Psycho-fig53.png]]
 +
 +
'''Timp de execuție''': 30 secunde pentru un text
 +
 +
'''Timp de implementare''': 1h 30 min.
 +
 +
'''Complexitate cerută''': <math>O(N^2)</math>
 +
 +
'''REZOLVARE''': Primul lucru care ne vine în gând este „se cere numărul de cicluri hamiltoniene într-un graf, deci problema e exponențială”. Rezolvarea backtracking nu e deloc greu de implementat, dar nu are nici o șansă să meargă pentru valori mari ale lui '''''N'''''. Afirmația de mai sus este corectă, dar incompletă; din această cauză concluzia este falsă. Se scapă din vedere faptul că graful nu este oarecare, ci are un aspect foarte particular.
 +
 +
Și în această problemă vom încerca să utilizăm soluțiile locale (pentru valori mici ale lui '''''N''''') pentru aflarea soluției globale. Respectiv, vom rezolva problema pentru '''''N'''''=2, apoi o vom extinde pentru  '''''N'''''=3, 4 și așa mai departe. Pentru început, însă, încercăm să simplificăm enunțul, reducând problema la una echivalentă, dar mai simplă.
 +
 +
Să considerăm o posibilă soluție pentru '''''N'''''=5:
 +
 +
[[File:Psycho-fig54.png]]
 +
 +
În loc să lucrăm cu segmente în această rețea, vom lucra cu ochiuri. Furgoneta parcurge un ciclu, deci închide în circuitul ei un număr de ochiuri. Am marcat aceste ochiuri cu un „X” în figura de mai sus. Așadar, oricărui drum al furgonetei i se poate atașa o matrice cu 3 linii și '''''N'''''-1 coloane, în care unele celule sunt bifate cu „X”, iar altele nu. Să vedem în primul rând care este corespondența între numărul de circuite hamiltoniene și numărul de matrice de acest tip.
 +
 +
Se observă că pentru orice circuit există un altul căruia îi este atașată aceeași matrice. Circuitul pereche este tocmai circuitul parcurs în sens invers, care închide în interior aceleași ochiuri de rețea:
 +
 +
[[File:Psycho-fig55.png]]
 +
 +
Acest lucru se întâmplă deoarece transformarea graf-matrice ignoră sensul de parcurgere a circuitului hamiltonian. De aici rezultă că pentru a calcula numărul de circuite hamiltoniene trebuie să calculăm numărul de matrice și să-l înmulțim cu 2.
 +
 +
În continuare, să analizăm câteva proprietăți ale matricelor în discuție.
 +
 +
'''1.''' Elementele bifate cu „X” în matrice formează o singură figură conexă.
 +
 +
Demonstrație: dacă figura nu ar fi conexă, adică dacă ar exista mai multe figuri, ele nu ar putea fi înconjurate de furgonetă într-un singur drum. De remarcat că toate pătratele înconjurate de furgonetă trebuie bifate cu X, deci furgoneta nu poate înconjura pătrate nebifate. De aceea, traseul de mai jos (care prezintă o porțiune oarecare de circuit) este imposibil.
 +
 +
[[File:Psycho-fig56.png]]
 +
 +
Conexitatea se referă numai la vecinătatea pe latură, nu și pe colț. Spre exemplu, figura de mai jos este incorectă, deoarece, pentru a o înconjura, furgoneta trebuie să treacă de două ori prin punctul încercuit:
 +
 +
[[File:Psycho-fig57.png]]
 +
 +
'''2.''' Elementele bifate cu „X” formează o structură aciclică.
 +
 +
Demonstrație: dacă structura ar fi ciclică, ar rezulta că elementele bifate cu „X” închid între ele elemente nebifate, pe care furgoneta însă nu poate să le ocolească. Iată un exemplu de ciclicitate:
 +
 +
[[File:Psycho-fig58.png]]
 +
 +
Practic, situația de mai sus obligă furgoneta să facă două drumuri: unul pe exterior și unul în jurul ochiului marcat cu „?”.
 +
 +
'''3.''' Nici un nod interior al rețelei nu poate avea toate cele patru ochiuri vecine marcate cu „X”.
 +
 +
Demonstrație: dacă ar exista un asemenea nod, el nu ar putea fi parcurs de furgonetă, deci ciclul nu ar mai fi hamiltonian. Este cazul nodului încercuit în figura următoare:
 +
 +
[[File:Psycho-fig59.png]]
 +
 +
'''4.''' Structura elementelor bifate cu „X” în cadrul matricei este arborescentă.
 +
 +
Demonstrația rezultă imediat din punctele anterioare: figura este conexă și aciclică.
 +
 +
'''5.''' Numărul de celule bifate este P = 2'''''N'''''-1.
 +
 +
Demonstrația se face prin inducție matematică. Să presupunem că structura noastră ar avea un singur pătrat bifat. Atunci structura ar avea patru laturi „la vedere”. Traseul furgonetei care ocolește structura ar avea patru laturi. O structură de două pătrate (desigur lipite) va avea șase laturi la vedere:
 +
 +
[[File:Psycho-fig60.png]]
 +
 +
Să ne imaginăm acum că orice structură cu '''''k''''' pătrate are <math>S_k</math> laturi la vedere. Trebuie să demonstrăm că toate structurile cu '''''k'''''+1 pătrate au același număr de laturi la vedere și să aflăm efectiv acest număr, <math>S_{k+1}</math>. Cel de-al '''''k'''''+1-lea pătrat trebuie alipit la structura deja existentă în așa fel încât să nu se închidă nici un ciclu. El se va lipi deci de o latură la vedere a unui pătrat din structură. În acest fel, va dispărea o latură la vedere, dar vor apărea trei în loc. Numărul de laturi la vedere va crește prin urmare cu 2. Această cifră nu depinde de locul în care este alipit al k+1-lea pătrat, nici de forma structurii deja existente, deci am demonstrat că toate structurile arborescente cu k pătrate au același număr de laturi la vedere. Pentru a afla efectiv acest număr, pornim de la relațiile recurente stabilite prin inducție și eliminăm recurența:
 +
 +
<math>
 +
\begin{align}
 +
S_{k + 1} & = S_k + 2 \\
 +
S_1 & = 4
 +
\end{align}
 +
\Biggr\}
 +
\implies S_k = 2k + 2
 +
</math>
 +
 +
Deoarece numărul total de noduri al rețelei este de 4'''''N''''', rezultă că structura noastră trebuie să aibă 4'''''N''''' laturi la vedere. Notând cu '''''P''''' numărul de pătrate bifate din matrice și rezolvând ecuația de mai jos, rezultă valoarea lui '''''P''''':
 +
 +
<math>
 +
2P + 2 = 4N \implies P = 2N - 1 = 2(N - 1) + 1
 +
</math>
 +
 +
Cum numărul de coloane al matricei este '''''N'''''-1, deducem că în medie pe fiecare coloană se vor afla două pătrate bifate, cu excepția uneia pe care se vor afla trei pătrate bifate. La nivel local, proprietatea este de asemenea respectată: numărul de pătrate bifate din primele '''''k''''' coloane ale matricei este 2'''''k''''', existând posibilitatea să mai fie un pătrat suplimentar. De exemplu, în figura dată mai sus pentru '''''N'''''=5, în primele două coloane se află patru elemente „X”, deci o medie de două pătrate pe fiecare coloană. În primele trei coloane există șapte elemente „X”, adică o medie de două pătrate pe coloană și un surplus de un pătrat. Lăsăm ca temă cititorului să demonstreze că, în primele '''''k''''' coloane există întotdeauna fie 2'''''k''''', fie 2'''''k'''''+1 pătrate. Orice număr mai mare duce la ciclicitatea figurii, orice număr mai mic duce la neconexitatea ei.
 +
 +
Pe fiecare coloană există opt combinații posibile de elemente bifate și nebifate, pe care le vom codifica cu numere de la 0 la 7, conform unei numărători binare:
 +
 +
[[File:Psycho-fig61.png]]
 +
 +
Să vedem acum care dintre aceste combinații rămân valabile. O coloană de tipul 0 nu poate exista, deoarece ea ar „rupe” matricea în două bucăți separate, deci proprietatea de conexitate nu ar fi respectată.
 +
 +
Dacă pe coloana '''''k''''' se află o combinație de tipul 3, ce s-ar putea afla pe coloana '''''k'''''+1 ?
 +
 +
[[File:Psycho-fig62.png]]
 +
 +
Pentru ca punctul A să se afle pe traseul furgonetei, este obligatoriu să bifăm pătratul de sub el. Pentru a menține conexitatea figurii apărute, trebuie bifat și pătratul din centrul coloanei '''''k'''''+1. Cea de-a treia celulă a coloanei '''''k'''''+1 nu poate fi bifată, deoarece punctul B ar fi înconjurat din patru părți de celule bifate, lucru care s-a stabilit că este imposibil. Se vede că singura combinație posibilă pentru coloana '''''k'''''+1 este 6. Ce combinație putem pune pe coloana k+2 ? Printr-un raționament analog, deducem că numai combinația 3:
 +
 +
[[File:Psycho-fig63.png]]
 +
 +
Iată că, pentru a putea respecta condițiile de corectitudine a matricei, am fi nevoiți să continuăm la nesfârșit cu coloane cu combinațiile 3-6-3-6 etc. Deci niciuna din aceste combinații nu poate apărea în matrice.
 +
 +
În continuare, vom defini mai multe șiruri de forma <math>S_k(i,t)</math>, unde:
 +
 +
* '''''k''''' este numărul unei coloane;
 +
* '''''i''''' este un număr de combinație (respectiv 1, 2, 4, 5 sau 7);
 +
* '''''t''''' este un număr care poate avea valoarea 0 sau 1.
 +
 +
<math>S_k(i,t)</math> semnifică „numărul de matrice (corecte) cu k coloane astfel încât pe coloana cu numărul '''''k''''' să se afle combinația '''''i''''', iar surplusul de pătrate bifate peste media de două pătrate pe fiecare coloană să fie '''''t'''''”. De exemplu, <math>S_7(5,1)</math> reprezintă numărul de matrice corecte (care respectă regulile de construcție) cu 7 coloane, astfel încât pe ultima coloană să se afle combinația 5 și să existe un surplus de 1 pătrat (adică numărul total de pătrate să fie 2 x 7 + 1 = 15).
 +
 +
Facem observația că pe a '''''N'''''-1-a coloană se pot afla doar combinațiile 5 sau 7 (pentru a acoperi colțurile de NE și SE ale grafului), iar surplusul de pătrate trebuie să fie 1 (deoarece în '''''N'''''-1 coloane trebuie să se afle '''''P'''''=2('''''N'''''-1)+1 pătrate bifate). Deci scopul nostru este să calculăm suma <math>S_{N-1}(5,1) + S_{N-1}(7,1)</math> și să o înmulțim cu 2 ca să aflăm numărul de cicluri hamiltoniene.
 +
 +
De asemenea, remarcăm că șirurile <math>S_k(1,1)</math>, <math>S_k(2,1)</math> și <math>S_k(4,1)</math> nu sunt definite. Aceasta deoarece combinațiile 1, 2 și 4 au un singur pătrat bifat pe coloană, adică mai puțin decât media de două pătrate. Este imposibil ca după adăugarea unei asemenea coloane să mai existe un surplus. (deoarece ar rezulta că în primele '''''k'''''-1 coloane exista un surplus de două pătrate). La polul opus, șirul <math>S_k(7,0)</math> nu este definit, deoarece combinația 7 are toată coloana bifată, adică peste medie, deci nu se poate să nu apară un surplus de pătrate bifate.
 +
 +
Mai trebuie stabilite formulele de recurență între șirurile <math>S_k(1,0)</math>, <math>S_k(2,0)</math>, <math>S_k(4,0)</math>, <math>S_k(5,0)</math>, <math>S_k(5,1)</math> și <math>S_k(7,1)</math>. Termenii inițiali ai recurenței sunt:
 +
 +
* <math>S_1(1,0)=0</math> deoarece matricea nu poate începe cu combinația 1
 +
* <math>S_1(2,0)=0</math> deoarece matricea nu poate începe cu combinația 2
 +
* <math>S_1(4,0)=0</math> deoarece matricea nu poate începe cu combinația 4
 +
* <math>S_1(5,0)=1</math> deoarece există o singură matrice de o coloană cu combinația 5
 +
* <math>S_1(5,1)=0</math> deoarece combinația 5 are două pătrate, deci nu există surplus
 +
* <math>S_1(7,1)=1</math> deoarece există o singură matrice de o coloană cu combinația 7
 +
 +
Pentru a stabili relația de recurență pentru șirul <math>S_k(1,0)</math>, ne întrebăm: cărei coloane îi poate urma coloana '''''k''''' de tip 1 astfel încât să nu mai existe surplus ? Dacă observăm că pe coloana '''''k''''' avem un singur element bifat (deci sub medie), rezultă că pe coloana '''''k'''''-1 exista un surplus de un pătrat. Deci coloana '''''k'''''-1 putea fi de tipul 5 sau 7, acestea fiind singurele tipuri de coloană după care poate exista un surplus. Rezultă formula:
 +
 +
<math>
 +
S_k(1,0)=S_{k-1}(5,1)+S_{k-1}(7,1)
 +
</math>
 +
 +
Printr-o simetrie perfectă se calculează aceeași formulă și pentru șirul <math>S_k(4,0)</math>:
 +
 +
<math>
 +
S_k(4,0)=S_{k-1}(5,1)+S_{k-1}(7,1)
 +
</math>
 +
 +
La șirul S_k(2,0), mai trebuie făcută observația că o coloană de tip 2 nu poate urma unei coloane de tip 5, deoarece se strică conexitatea figurii. Rezultă:
 +
 +
<math>
 +
S_k(2,0)=S_{k-1}(7,1)
 +
</math>
 +
 +
Șirul <math>S_k(5,0)</math> provine din adăugarea unei coloane de tipul 5 după o coloană de tipul 1, 4 sau 5. Coloana '''''k'''''-1 nu poate fi de tipul 2 deoarece figura rezultată nu este conexă, nici de tipul 7 deoarece ar rezulta că în primele '''''k'''''-2 coloane media de celule bifate este mai mică decât 2.
 +
 +
<math>
 +
S_k(5,0)=S_{k-1}(1,0)+S_{k-1}(4,0)+S_{k-1}(5,0)
 +
</math>
 +
 +
Șirul <math>S_k(5,1)</math> provine din adăugarea unei coloane de tipul 5 după o coloană de tipul 5 sau 7, deoarece tipul de coloană 5 are două pătrate bifate, deci conservă surplusul:
 +
 +
<math>
 +
S_k(5,1)=S_{k-1}(5,1)+S_{k-1}(7,1)
 +
</math>
 +
 +
În sfârșit, o coloană de tip 7 poate urma oricărui tip de coloană pentru care surplusul este 0, adică:
 +
 +
<math>
 +
S_k(7,1)=S_{k-1}(1,0)+S_{k-1}(2,0)+S_{k-1}(4,0)+S_{k-1}(5,0)
 +
</math>
 +
 +
Acestea sunt formulele de recurență. Rezultatul care trebuie afișat pe ecran este <math>2[S_{N-1}(5,1)+S_{N-1}(7,1)]</math>, deoarece după '''''N'''''-1 coloane surplusul trebuie să fie 1, iar colțurile matricii trebuie să fie bifate. Se observă că <math>S_k(1,0)=S_k(4,0)=S_k(5,1)</math>. Practic, problema se reduce la trei șiruri. Notăm:
 +
 +
<math>
 +
\begin{align}
 +
A_k & = S_k(5,0) \\
 +
B_k & = S_k(1,0) = S_k(4,0) = S_k(5,1) \\
 +
C_k & = S_k(7,1) \implies S_k(2,0)=C_{k-1}
 +
\end{align}
 +
</math>
 +
 +
De aici rezultă grupul de relații:
 +
 +
<math>
 +
\begin{cases}
 +
A_k & = A_{k - 1} + 2B_{k - 1} \\
 +
B_k & = B_{k - 1} + C_{k - 1} \\
 +
C_k & = A_{k - 1} + 2B_{k - 1} + C_{k - 2} = A_k + C_{k - 2}
 +
\end{cases}
 +
</math>
 +
 +
și
 +
 +
<math>
 +
\begin{cases}
 +
A_1 & = 1 \\
 +
B_1 & = 0 \\
 +
C_1 & = 1
 +
\end{cases}
 +
</math>
 +
 +
Noi avem nevoie de valoarea
 +
 +
<math>
 +
2(B_{N-1} + C_{N-1}) = 2B_N
 +
</math>
 +
 +
Programul de mai jos nu face decât să implementeze calculul acestor șiruri recurente. Trebuie avut grijă însă cu reprezentarea internă a numerelor, deoarece pentru '''''N'''''=200 valorile ajung la 81 de cifre. Este deci necesară reprezentarea numerelor ca șiruri de cifre.
 +
 +
<syntaxhighlight lang="c">
 +
#include <stdio.h>
 +
#include <mem.h>
 +
 +
typedef int Huge[85];
 +
Huge A,B,C,C2,HTemp;
 +
int N,k;
 +
 +
void Atrib(Huge H, int V)
 +
/* H <- V */
 +
{
 +
  memset(H,0,sizeof(Huge));
 +
  H[0]=1;
 +
  H[1]=V;
 +
}
 +
 +
void Add(Huge A, Huge B)
 +
/* A <- A+B */
 +
{ int i,T=0;
 +
 +
  if (B[0]>A[0])
 +
    { for (i=A[0]+1;i<=B[0];) A[i++]=0;
 +
      A[0]=B[0];
 +
    }
 +
    else for (i=B[0]+1;i<=A[0];) B[i++]=0;
 +
  for (i=1;i<=A[0];i++)
 +
    { A[i]+=B[i]+T;
 +
      T=A[i]/10;
 +
      A[i]%=10;
 +
    }
 +
  if (T) A[++A[0]]=T;
 +
}
 +
 +
void WriteHuge(Huge H)
 +
{ int i;
 +
 +
  for (i=H[0];i;printf("%d",H[i--]));
 +
  printf("\n");
 +
}
 +
 +
void main(void)
 +
{
 +
  printf("N=");scanf("%d",&N);
 +
  Atrib(A,1);
 +
  Atrib(B,0);
 +
  Atrib(C,1);
 +
  Atrib(C2,0);
 +
  for (k=2;k<=N;k++)
 +
    { memmove(HTemp,C,sizeof(Huge));
 +
      Add(A,B);Add(A,B);  /* A(k) = A(k-1) + 2*B(k-1) */
 +
      Add(B,C);          /* B(k) = B(k-1) + C(k-1)  */
 +
      memmove(C,A,sizeof(Huge));
 +
      Add(C,C2);          /* C(k) = A(k) + C(k-2)    */
 +
      memmove(C2,HTemp,sizeof(Huge)); /* noul C(K-2) */
 +
    }
 +
  Add(B,B);              /* Rezultatul este 2*B(n)  */
 +
  WriteHuge(B);
 +
}
 +
</syntaxhighlight>

Latest revision as of 12:32, 9 March 2018

⇦ înapoi la Psihologia concursurilor de informatică

Capitolul VI: Probleme de concurs (1-6)

Problema 1

ENUNȚ: Se consideră următorul joc: Pe o tablă liniară cu 2N+1 căsuțe sunt dispuse N bile albe (în primele N căsuțe) și N bile negre (în ultimele N căsuțe), căsuța din mijloc fiind liberă. Bilele albe se pot mișca numai spre dreapta, iar cele negre numai spre stânga. Mutările posibile sunt:

  1. O bilă albă se poate deplasa o căsuță spre dreapta, numai dacă aceasta este liberă;
  2. O bilă albă poate sări peste bila aflată imediat în dreapta ei (indiferent de culoarea acesteia), așezându-se în căsuța de dincolo de ea, numai dacă aceasta este liberă;
  3. O bilă neagră se poate deplasa o căsuță spre stânga, numai dacă aceasta este liberă;
  4. O bilă neagră poate sări peste bila aflată imediat în stânga ei (indiferent de culoarea acesteia), așezându-se în căsuța de dincolo de ea, numai dacă aceasta este liberă.

Trebuie schimbat locul bilelor albe cu cele negre. Se mai cere în plus ca prima mutare să fie făcută cu o bilă albă.

Intrarea: De la tastatură se citește numărul N ≤ 1000.

Ieșirea: În fișierul OUTPUT.TXT se vor tipări două linii terminate cu <Enter>. Pe prima se va tipări numărul de mutări efectuate, iar pe a doua o succesiune de cifre cuprinse între 1 și 4, nedespărțite prin spații, corespunzătoare mutărilor ce trebuie făcute.

Exemple:

  • N=1 ⇒ Ieșirea "141"
  • N=2 ⇒ Ieșirea "14322341"

Complexitate cerută: O(N^{2}).

Timp de implementare: 1h.

Timp de rulare: 10 secunde pentru un test.

REZOLVARE: La prima vedere, problema pare să se preteze la o rezolvare în timp exponențial, prin metoda „Branch and Bound”. Un neajuns al enunțului pare să fie faptul că nu se specifică dacă numărul de mutări efectuate trebuie sau nu să fie minim. Pentru a ne lămuri, să privim în detaliu soluțiile pentru N=1 și N=2:

  • Pentru N = 1, toate mutările sunt forțate ((a) - se mută bila albă, (b) - se sare cu cea neagră peste ea, (c) - se mută din nou bila albă); trebuie remarcat că după mutările (a) și (b) se obțin două configurații simetrice una în raport cu cealaltă (oglindite).
  • Pentru N = 2, se poate începe sărind cu bila albă de la margine peste cealaltă, dar această mutare ar duce la blocarea jocului. Este deci obligatoriu să se înceapă prin a împinge bila albă centrală (a). Următoarea mutare este forțată ((b) - se sare cu bila neagră peste cea albă), apoi toate mutările sunt obligate (în sensul că dacă la orice pas se face altă mutare decât cea care conduce la soluție, jocul se blochează în câteva mutări): (c) - se împinge bila neagră, (d), (e) - se sare de două ori cu bilele albe, (f) - se împinge bila neagră, (g) - se sare cu bila neagră, (h) - se împinge bila albă. Trebuie din nou remarcat că după mutările (c) și (e) se obțin două configurații simetrice.

Așadar în ambele cazuri, soluția este unică. De fapt, există două soluții asemănătoare, una dacă se începe cu o mutare a bilei albe și una dacă se începe cu o mutare a bilei negre. Fiindcă enunțul impune ca prima mutare să se facă cu o bilă albă, soluția este unică. Se mai observă și că, atât pentru N=1 cât și pentru N=2 șirul de mutări este simetric. Pentru a indica efectiv modul de determinare a soluției (care va sugera și ideea de scriere a programului) și pentru a explica observațiile de mai sus, să generalizăm observațiile făcute pentru un N oarecare.

  • Configurația inițială este:
Psycho-fig32.png
  • Se împinge bila albă și se sare cu cea neagră peste ea (șirul de mutări 14):
Psycho-fig33.png
  • Se împinge bila neagră și se sare de două ori cu cele albe peste ea (șirul de mutări 322):
Psycho-fig34.png
  • Se împinge bila albă și se sare de trei ori cu cele negre peste ea (șirul de mutări 1444):
Psycho-fig35.png
  • Se împinge bila neagră și se sare de patru ori cu cele albe peste ea (șirul de mutări 32222):
Psycho-fig36.png
...
  • Se împinge bila albă (mutarea 1)
Psycho-fig37.png
  • Se sare de N ori cu cele negre peste ea (șirul de mutări 44..44):
Psycho-fig38.png

Ultimele două configurații sunt simetrice. În acest moment șirul de mutări se inversează:

  • Se împinge bila albă (mutarea 1):
Psycho-fig39.png

...

  • Se sare de patru ori cu bilele albe și se împinge bila neagră (șirul de mutări 22223):
Psycho-fig40.png
  • Se sare de trei ori cu bilele negre și se împinge bila albă (șirul de mutări 4441):
Psycho-fig41.png
  • Se sare de două ori cu bilele albe și se împinge bila neagră (șirul de mutări 223):
Psycho-fig42.png
  • Se sare cu bila neagră și se împinge bila albă (șirul de mutări 41), obținându-se configurația finală:
Psycho-fig43.png

În concluzie, șirul de mutări este: o împingere - un salt - o împingere - două salturi - o împingere - trei salturi - ... - o împingere - N-1 salturi - o împingere - N salturi - o împingere - N-1 salturi - ... - o împingere - trei salturi - o împingere - două salturi - o împingere - un salt - o împingere, culorile alternând la fiecare pas.

Pentru a calcula numărul de mutări, putem să le numărăm pe măsură ce le efectuăm, dar deoarece se cere afișarea mai întâi a numărului de mutări și după aceea a mutărilor în sine, trebuie fie să stocăm toate mutările în memorie, fie să lucrăm cu fișiere temporare, ambele variante putând duce la complicații nedorite. Din fericire, numărul de mutări se poate calcula cu ușurință astfel: fiecare piesă albă trebuie mutată în medie cu N pași către dreapta și fiecare piesă neagră trebuie mutată cu N pași către stânga. Deci numărul total de pași este 2N(N+1). Din secvența generală de mutări expusă mai sus se observă că nu se fac decât 2N împingeri de piese (mutări de un singur pas), restul fiind salturi (mutări de câte doi pași). Deci numărul de mutări este:

2N+{\frac  {2N(N+1)-2N}{2}}=2N+N^{2}=N(N+2)

De aici deducem că nu există un algoritm mai bun decât O(N^{2}), deoarece numărul de mutări este O(N^{2}). Propunem ca temă cititorului să demonstreze că nu există decât două succesiuni de mutări care rezolvă problema, din care una începe cu mutarea unei piese albe, iar cealaltă este oglindirea ei și începe cu mutarea unei piese negre, deci nu poate constitui o soluție corectă. Demonstrația începe prin a arăta că sunt necesare cel puțin 2N împingeri de piese. Această demonstrație explică de ce nu se cere un număr minim de mutări în enunț - cerința nu ar avea sens întrucât soluția este oricum unică. Acestea fiind zise, programul arată astfel:

#include <stdio.h>
int N;
FILE *OutF;

void Jump(int Level, char A, char B)
{ int i;
  putc(A,OutF);
  for (i=1;i<=Level;i++) putc(B,OutF);
  if (Level<N)
    {
      Jump(Level+1,'1'+'2'-A,'4'+'3'-B);
      for (i=1;i<=Level;i++) putc(B,OutF);
    }
  putc(A,OutF);
}

void main(void)
{
  printf("N=");scanf("%d",&N);
  OutF=fopen("output.txt","wt");
  fprintf(OutF,"%ld\n",(long)N*(N+2));
  Jump(1,'1','4');
  fprintf(OutF,"\n");
  fclose(OutF);
}


Problema 2

Problema următoare a fost propusă la a VI-a Olimpiadă Internațională de Informatică, Stockholm 1994. Este și ea un bun exemplu de situație în care putem cădea în plasa unei rezolvări „Branch and Bound” atunci când nu este cazul.

ENUNȚ: Se dă o configurație de 3 x 3 ceasuri, fiecare având un singur indicator care poate arăta numai punctele cardinale (adică orele 3, 6, 9 și 12). Asupra acestor ceasuri se poate acționa în nouă moduri distincte, fiecare acțiune însemnând mișcarea limbilor unui anumit grup de ceasuri în sens orar cu 90°. În figura de mai jos se dă un exemplu de configurație inițială a ceasurilor și se arată care sunt cele nouă tipuri de mutări (pentru fiecare tip de mutare se mișcă numai ceasurile reprezentate hașurat).

Psycho-fig44.png

Se cere ca, într-un număr minim de mutări, să aducem toate indicatoarele la ora 12.

Intrarea se face din fișierul INPUT.TXT, care conține configurația inițială sub forma unei matrice 3 x 3. Pentru fiecare ceas se specifică câte o cifră: 0 = ora 12, 1 = ora 3, 2 = ora 6, 3 = ora 9.

Ieșirea se va face în fișierul OUTPUT.TXT sub forma unui șir de numere între 1 și 9, pe un singur rând, separate prin spațiu, reprezentând șirul de mutări care aduc ceasurile în starea finală. Se cere o singură soluție.

Exemplu: Pentru figura de mai sus, fișierul INPUT.TXT este

3 3 0
2 2 2
2 1 2

iar fișierul OUTPUT.TXT ar putea fi:

5 8 4 9

Timp de implementare: 1h - 1h 15min.

Timp de rulare: o secundă.

Complexitate cerută: O(1) (timp constant).

REZOLVARE: Din câte am văzut pe la concursuri, peste jumătate din elevi s-ar apuca direct să implementeze o rezolvare Branch and Bound la această problemă, fără să-și mai bată capul prea mult. Există argumente în favoarea acestei inițiative:

  • Mulți preferă să nu mai piardă timpul căutând o altă soluție, mai ales că problema seamănă mult cu „Lampa lui Dario Uri” (care de fapt este exact problema ceasurilor, dar în care ceasurile au doar două stări în loc de patru). În plus, se știe că pe cazul general al unei table N x N, cele două probleme nu admit rezolvări polinomiale și atunci cea mai sigură soluție este prin tehnica Branch and Bound.
  • De asemenea, se observă că numărul total de configurații posibile pentru o tablă cu 9 ceasuri este de 4^{9}, adică aproximativ un sfert de milion. Un algoritm Branch and Bound ar furniza așadar o soluție în timp rezonabil. Raționamentul multor elevi este „decât să pierd timpul căutând o soluție mai bună, fără să am certitudinea că o voi găsi, mai bine folosesc timpul implementând un Branch care măcar știu sigur că merge”.
  • Problema cere o soluție într-un număr minim de pași, lucru care îi cam descurajează pe cei care încă ar vrea să caute alte rezolvări. „Alte rezolvări” înseamnă de obicei un Greedy comod de implementat, iar asupra rezolvărilor Greedy se poartă întotdeauna discuții interminabile pe culoarele sălilor de concurs referitor la „cât de bune sunt” (adică în cât la sută din cazuri furnizează soluția optimă).

Se pierd însă din vedere unele lucruri esențiale. În primul rând, tabla nu este de N x N, ci are dimensiuni fixate, 3 x 3. În al doilea rând, implementarea unui Branch and Bound în timp de concurs este o aventură nu tocmai ușor de dus la bun sfârșit (personal mi-a fost frică să o încerc vreodată). În sfârșit, după cum se va vedea mai jos, problema șirului minim de transformări este o pseudo-problemă, deoarece soluția simplă este oricum unică.

Ce se înțelege prin „soluție simplă”? Să remarcăm două lucruri:

  1. Aplicarea de patru ori a aceleiași mutări nu schimbă nimic în configurația ceasurilor. Într-adevăr, mutarea va afecta de fiecare dată același grup de ceasuri, iar aplicarea de patru ori va roti fiecare indicator cu 360°, adică îl va aduce în poziția inițială. Din acest motiv, toate afirmațiile făcute în cele ce urmează vor fi valabile în algebra modulo 4.
  2. Ordinea în care se aplică transformările nu contează.

În consecință, prin „soluție simplă” se înțelege un șir de mutări ordonat crescător în care nici o mutare nu apare de mai mult de trei ori. Să demonstrăm acum că soluția simplă este unică.

Fie A\in M_{3}({\mathbb  {Z}}_{4}) matricea citită de la intrare, unde a_{{i,j}} arată de câte ori a fost rotit ceasul C_{{i,j}} peste ora 12. Fie matricea B\in M_{3}({\mathbb  {Z}}_{4}),b_{{i,j}}=4-a_{{i,j}}. Matricea B arată de câte ori mai trebuie rotit fiecare ceas până la ora 12. O soluție înseamnă a efectua fiecare din cele 9 mutări de un număr de ori, p_{1},p_{2},\dots ,p_{9}. Cum afectează aceste mutări ceasurile? Se poate deduce ușor:

Ceasul Tipurile de mutări care îl afectează
C_{{1,1}} 1, 2, 4
C_{{1,2}} 1, 2, 3, 5
C_{{1,3}} 2, 3, 6
C_{{2,1}} 1, 4, 5, 7
C_{{2,2}} 1, 3, 5, 7, 9
C_{{2,3}} 3, 5, 6, 9
C_{{3,1}} 4, 7, 8
C_{{3,2}} 5, 7, 8, 9
C_{{3,3}} 6, 8, 9

Se obține deci un sistem de 9 ecuații cu 9 necunoscute:

P={\begin{pmatrix}p_{1}+p_{2}+p_{4}&p_{1}+p_{2}+p_{3}+p_{5}&p_{2}+p_{3}+p_{6}\\p_{1}+p_{4}+p_{5}+p_{7}&p_{1}+p_{3}+p_{5}+p_{7}+p_{9}&p_{3}+p_{5}+p_{6}+p_{9}\\p_{4}+p_{7}+p_{8}&p_{5}+p_{7}+p_{8}+p_{9}&p_{6}+p_{8}+p_{9}\\\end{pmatrix}}\equiv B

Să presupunem că acest sistem admite două soluții p_{1},p_{2},\dots ,p_{9} și q_{1},q_{2},\dots ,q_{9}. Atunci P\equiv B{\pmod  {4}} și Q\equiv B{\pmod  {4}}, deci P\equiv Q{\pmod  {4}} și, prin diferite combinații liniare ale celor 9 ecuații se deduce p_{1}\equiv q_{1}, p_{2}\equiv q_{2}, ..., p_{9}\equiv q_{9}{\pmod  {4}}, adică cele două soluții sunt echivalente.

Odată ce am demonstrat că soluția este unică, algoritmul de găsire a ei este foarte simplu: găsim o soluție oarecare, o ordonăm crescător și eliminăm orice grup de 4 mutări identice. Pentru a găsi o soluție oarecare, avem nevoie de niște mutări predefinite care să miște un singur ceas cu o singură poziție înainte, fără a afecta celelalte ceasuri. Aceste mutări vor fi reținute sub forma unui vector cu 9 componente, fiecare componentă indicând de câte ori se efectuează fiecare din cele 9 tipuri de mutări. Deoarece avem nevoie de 9 asemenea mutări predefinite, câte una pentru fiecare ceas, rezultatul va fi o matrice predefinită. De exemplu, pentru a determina secvența de mutări care rotește ceasul C_{{1,1}} cu o poziție, trebuie rezolvat sistemul

{\begin{pmatrix}p_{1}+p_{2}+p_{4}&p_{1}+p_{2}+p_{3}+p_{5}&p_{2}+p_{3}+p_{6}\\p_{1}+p_{4}+p_{5}+p_{7}&p_{1}+p_{3}+p_{5}+p_{7}+p_{9}&p_{3}+p_{5}+p_{6}+p_{9}\\p_{4}+p_{7}+p_{8}&p_{5}+p_{7}+p_{8}+p_{9}&p_{6}+p_{8}+p_{9}\\\end{pmatrix}}\equiv {\begin{pmatrix}1&0&0\\0&0&0\\0&0&0\end{pmatrix}}

lucru care nu este foarte ușor, dar se poate duce la bun sfârșit în timp de concurs. Soluția este p_{1}=3,p_{2}=3,p_{3}=3,p_{4}=3,p_{5}=3,p_{6}=2,p_{7}=3,p_{8}=2,p_{9}=0, adică mutarea 1 trebuie efectuată de trei ori, mutarea 2 de trei ori ș.a.m.d. Se obține prima linie din matricea predefinită, (3, 3, 3, 3, 3, 2, 3, 2, 0). Mai trebuie rezolvate propriu-zis sistemele de ecuații pentru ceasurile C_{{1,2}} și C_{{2,2}}, soluțiile celorlalte sisteme decurgând ușor prin simetrie. Soluțiile apar în textul sursă.

Odată determinate aceste șiruri elementare de mutări, vom lua pe rând fiecare ceas, vom aplica șirul elementar corespunzător de atâtea ori cât e nevoie pentru a-l aduce la ora 12 și vom aduna modulo 4 toate mutările făcute. Vectorul sumă care rezultă este tocmai soluția noastră.

Pentru exemplul din enunț, folosind constantele din programul sursă, obținem:

B={\begin{pmatrix}1&1&0\\2&2&2\\2&3&2\end{pmatrix}}

și

1 x (3,3,3,3,3,2,3,2,0) = (3,3,3,3,3,2,3,2,0) +
1 x (2,3,2,3,2,3,1,0,1) = (2,3,2,3,2,3,1,0,1)
0 x (3,3,3,2,3,3,0,2,3) = (0,0,0,0,0,0,0,0,0)
2 x (2,3,1,3,2,0,2,3,1) = (0,2,2,2,0,0,0,2,2)
2 x (2,3,2,3,1,3,2,3,2) = (0,2,0,2,2,2,0,2,0)
2 x (1,3,2,0,2,3,1,3,2) = (2,2,0,0,0,2,2,2,0)
2 x (3,2,0,3,3,2,3,3,3) = (2,0,0,2,2,0,2,2,2)
3 x (1,0,1,3,2,3,2,3,2) = (3,0,3,1,2,1,2,1,2)
2 x (0,2,3,2,3,3,3,3,3) = (0,0,2,0,2,2,2,2,2)
------------------------
(0,0,0,1,1,0,0,1,1)

Prin urmare soluția simplă a exemplului este: 4 5 8 9.

#include <stdio.h>
typedef int Matrix[9][9];
typedef int Vector[9];
const Matrix A=
  {{3,3,3,3,3,2,3,2,0},  // Mutarile care misca ceasul C11
   {2,3,2,3,2,3,1,0,1},  // .
   {3,3,3,2,3,3,0,2,3},  // .
   {2,3,1,3,2,0,2,3,1},  // .
   {2,3,2,3,1,3,2,3,2},  // .
   {1,3,2,0,2,3,1,3,2},  // .
   {3,2,0,3,3,2,3,3,3},  // .
   {1,0,1,3,2,3,2,3,2},  // .
   {0,2,3,2,3,3,3,3,3}}; // Mutarile care misca ceasul C33

void main(void)
{ FILE *F=fopen("input.txt","rt");
  Vector V={0,0,0,0,0,0,0,0,0}; // Vectorul suma
  int i,j,k;

  for (i=0;i<=8;i++)
    { fscanf(F,"%d",&k);
      for (j=0;j<=8;j++)
        V[j]=(V[j]+(4-k)*A[i][j])%4;
    }
  fclose(F);

  F=fopen("output.txt","wt");
  for(i=0;i<=8;i++)
    for(j=1;j<=V[i];j++)
      fprintf(F,"%d ",i+1);
  fclose(F);
}


Problema 3

Problema de mai jos este un exemplu de situație în care căutarea exhaustivă a soluției este cea mai bună alegere. Ea a fost propusă spre rezolvare la a VIII-a Olimpiadă Internațională de Informatică, Veszprem, Ungaria 1996.

ENUNȚ: Văzând succesul cubului său magic, Rubik a inventat versiunea plană a jocului, numit „pătrate magice”. Se folosește o tablă compusă din 8 pătrate de dimensiuni egale. Cele opt pătrate au culori distincte, codificate prin numere de la 1 la 8, ca în figura următoare:

Psycho-fig45.png

Configurația tablei se poate reprezenta într-un vector cu 8 elemente citind cele opt pătrate, începând din colțul din stânga sus și mergând în sens orar. De exemplu, configurația din figură se reprezintă prin vectorul (1, 2, 3, 4, 5, 6, 7, 8). Aceasta este configurația inițială a tablei.

Unei configurații i se pot aplica trei transformări elementare, identificate prin literele „A”, „B” și „C”:

  • „A” schimbă între ele cele două linii ale tablei;
  • „B” rotește circular spre dreapta întregul dreptunghi (cu o poziție);
  • „C” rotește în sens orar cele patru pătrate centrale (cu o poziție);

Efectele transformărilor elementare asupra configurației inițiale sunt reprezentate în figura de mai jos:

Psycho-fig46.png

Din configurația inițială se poate ajunge în orice configurație folosind numai combinații de tranformări elementare. Trebuie să scrieți un program care calculează o secvență de transformări elementare care să aducă tabla de la configurația inițială la o anumită configurație finală cerută.

Intrarea: Fișierul INPUT.TXT conține 8 întregi pe aceeași linie, separați prin spații, descriind configurația finală.

Ieșirea se va face în fișierul OUTPUT.TXT. Pe prima linie a acestuia se va tipări lungimea L a secvenței de transformări, iar pe fiecare din următoarele L linii se va tipări câte un caracter „A”, „B” sau „C”, corespunzător mutărilor care trebuie efectuate.

Exemplu:

INPUT.TXT OUTPUT.TXT
2 6 8 4 5 7 3 1 7
B
C
A
B
C
C
B

Timp limită pentru un test: 20 secunde.

Timp de implementare: 1h 30’ - 1h 45’

Note:

  1. La concurs s-au acordat, pentru fiecare test, două puncte dacă se furniza o soluție și încă două dacă lungimea ei nu depășea 300 de mutări.
  2. Concurenților li s-a furnizat un program auxiliar, MTOOL.EXE, cu care se puteau verifica soluțiile furnizate.

REZOLVARE: Și la această problemă se întrevăd două abordări, ca și în problema ceasurilor: una bazată pe mutări predefinite, iar cealaltă pe o căutare exhaustivă a soluției. De data aceasta însă, prima este neinspirată. Să le analizăm pe rând pe fiecare, plecând de la următoarele considerente:

  • Dacă se aplică de două ori la rând mutarea A, tabla rămâne nemodificată;
  • Dacă se aplică de patru ori consecutiv una din mutările B sau C, tabla rămâne nemodificată;
  • Ordinea în care se efectuează mutările contează.

Soluția pe care autorul a prezentat-o la concurs avea predefinite mai multe mutări care schimbau între ele oricare două pătrate vecine de pe tablă. Mergând din aproape în aproape, fiecare pătrat era adus în poziția corespunzătoare. Spre exemplu, succesiunea de mutări predefinite care duceau la configurația din exemplu este:

Psycho-fig47.png

Această soluție funcționează instantaneu și este relativ ușor de implementat. Ea are însă defectul că soluția furnizată este extrem de lungă, ajungând frecvent la 500 de mutări. Din cele zece teste date, numai trei s-au încadrat în limita de 300 de mutări. Iată mai jos și sursa Pascal prezentată la concurs, care a câștigat numai 26 din cele 40 de puncte acordate pentru problemă:

program Magic;
{$B-,I-,R-,S-}
{ Tabla este 1 2 3 4
             A B C D }
const r12='BCBBB'; { Roteste in sens orar coloanele 12 }
      r23='C';     { Roteste in sens orar coloanele 23 }
      r34='BBBCB'; { Roteste in sens orar coloanele 34 }
      r14='BBCBB'; { Roteste in sens orar coloanele 41 }

      plBCD=r12+r23+r34+r14; { Permuta patratele BCD }
      PL234=plBCD+'A'+plBCD+'A'; { Permuta coloanele 234 }

      { SXY schimba intre ele coloanele X si Y }
      S14='B'+PL234;
      S12='BBB'+S14+'B';
      S23='BB'+S14+'BB';
      S34='B'+S14+'BBB';
      S13=r12+r12+r23+r23+r12+r12;
      S24='B'+S13+'BBB';

      { RevXY schimba intre ele patratele vecine X si Y }
      RevC3=plBCD+r23+r12+r12+r34+r34+'BBB'+plBCD+'A';
      RevD4='BBB'+RevC3+'B';
      RevB2='B'+RevC3+'BBB';
      RevA1='BB'+RevC3+'BB';

      Rev23='C'+RevC3+'CCC';
      Rev12='B'+Rev23+'BBB';
      Rev34='BBB'+Rev23+'B';
      Rev14='BB'+Rev23+'BB';

      RevAB='A'+Rev12+'A';
      RevBC='A'+Rev23+'A';
      RevCD='A'+Rev34+'A';
      RevAD='A'+Rev14+'A';

type Matrix=array[1..2,1..4] of Integer;
     Vector=array[1..60000] of Char;
var A,B:Matrix;
    V:Vector;
    N:Integer;

procedure MakeAMatrix;
begin
  A[1,1]:=1;
  A[1,2]:=2;
  A[1,3]:=3;
  A[1,4]:=4;
  A[2,1]:=8;
  A[2,2]:=7;
  A[2,3]:=6;
  A[2,4]:=5;
end;

procedure ReadBMatrix;
begin
  Assign(Input,'input.txt');
  Reset(Input);
  Read(B[1,1]);
  Read(B[1,2]);
  Read(B[1,3]);
  Read(B[1,4]);
  Read(B[2,4]);
  Read(B[2,3]);
  Read(B[2,2]);
  Read(B[2,1]);
  Close(Input);
end;

procedure AddString(S:String);
{ Adauga o secventa la sirul-solutie }
var i:Integer;
begin
  for i:=1 to Length(S) do
    begin
      Inc(N);
      V[N]:=S[i];
    end;
end;

procedure FindElement(K:Integer;var X,Y:Integer);
{ Cauta un element intr-o permutare }
var i,j:Integer;
begin
  for i:=1 to 2 do
    for j:=1 to 4 do
      if A[i,j]=K then begin
                         X:=i;
                         Y:=j;
                         Exit;
                       end;
end;

procedure Switch(var X,Y:Integer);
{ Schimba intre ele doua numere }
var IAux:Integer;
begin
  IAux:=X;X:=Y;Y:=IAux;
end;

procedure Process;
{ Transforma pozitia in pozitia B prin schimbari
  repetate ale elementelor vecine }
var i,j,k,l,m:Integer;
begin
  for j:=1 to 4 do
    for i:=1 to 2 do
      begin
        FindElement(B[i,j],k,l);
        { Gaseste elementul care trebuie adus
          pe pozitia (i,j) }
        if k<>i then begin
                       { Il aduce pe linia corecta }
                       case l of
                         1:AddString(RevA1);
                         2:AddString(RevB2);
                         3:AddString(RevC3);
                         4:AddString(RevD4);
                       end; {case}
                       Switch(A[k,l],A[i,l]);
                       k:=i;
                     end;
        for m:=l downto j+1 do
          { Il aduce pe coloana corecta }
          begin
            if k=1
              then case m of
                     2:AddString(Rev12);
                     3:AddString(Rev23);
                     4:AddString(Rev34);
                   end
              else case m of
                     2:AddString(RevAB);
                     3:AddString(RevBC);
                     4:AddString(RevCD);
                   end;
            Switch(A[k,m],A[k,m-1]);
          end;
      end;
end;

procedure Cut(K,D:Integer);
{ Taie din vectorul V D pozitii incepand cu K }
var i:Integer;
begin
  for i:=K to N-D do
    V[i]:=V[i+D];
  Dec(N,D);
end;

procedure Reduce;
{ Reduce secventele de mutari identice }
var i:Integer;
begin
  i:=1;
  repeat
    case V[i] of
      'A':if (i<=N-1) and (V[i+1]='A')
            then Cut(i,2)
            else Inc(i);
      'B':if (i<=N-3) and (V[i+1]='B')
            and (V[i+2]='B') and (V[i+3]='B')
            then Cut(i,4)
            else Inc(i);
      'C':if (i<=N-3) and (V[i+1]='C')
            and (V[i+2]='C') and (V[i+3]='C')
            then Cut(i,4)
            else Inc(i);
    end; {case}
  until i=N;
end;

procedure WriteSolution;
var i:Integer;
begin
  Assign(Output,'output.txt');
  Rewrite(Output);
  WriteLn(N);
  for i:=1 to N do WriteLn(V[i]);
  Close(Output);
end;

begin
  N:=0;
  MakeAMatrix;
  ReadBMatrix;
  Process;
  Reduce;
  WriteSolution;
end.

Singura soluție pare deci a fi una de tipul Branch and Bound, care nu este tocmai la îndemână. Cu toate acestea, numărul total de configurații posibile ale tablei este de numai 8! = 40320. Într-adevăr, fiecare poziție de pe tablă se reprezintă printr-o permutare a mulțimii {1,2,3,4,5,6,7,8}. Se poate face deci cu ușurință o căutare exhaustivă a soluției. Aceasta simplifică mult structurile de date folosite (implementarea Branch & Bound folosește structuri destul de încâlcite). În plus, practica arată că se poate ajunge în orice configurație în mai puțin de 25 de mutări.

Algoritmul de căutare este cunoscut sub numele de algoritmul lui Lee și are la bază următoarea idee: Se pornește cu configurația inițială, care este depusă într-o coadă. La fiecare pas se extrage prima configurație disponibilă din coadă, se efectuează pe rând fiecare din cele trei mutări și se obțin trei succesori. Aceștia sunt adăugați la sfârșitul cozii, dacă nu există deja în coadă. Acest pas se numește expandare. Expandarea continuă până când elementul selectat spre expandare este tocmai configurația finală.

Figura următoare indică modul de expandare a cozii, cu mențiunea că printr-o succesiune de litere ne-am referit la configurația care se obține efectuând mutările respective:

Psycho-fig48.png

Se observă că, la pasul 2, în coadă au fost adăugate doar configurațiile „AB” și „AC”, iar configurația „AA” nu, deoarece prin efectuarea de două ori a mutării „A” se revine la configurația inițială, care a fost deja expandată. De asemenea, la pasul 3, după expandarea configurației „B” au fost adăugate în coadă numai configurațiile „BB” și „BC”, deoarece configurația „BA” este echivalentă cu configurația „AB”, aflată deja în listă.

Pseudocodul algoritmului este:

citeste datele de intrare
initializeaza coada cu configuratia initiala
cat timp primul element al cozii nu este configuratia finala:
  expandeaza primul element al cozii
  pentru i=[A,B,C]
    daca succesorul i nu a fost deja pus in coada atunci
      adauga succesorul i in coada
  sterge primul element al cozii
reconstituie sirul de mutari

Algoritmul de mai sus garantează și găsirea soluției optime (în număr minim de mutări). Rămân de lămurit două lucruri: (1) Cum ne dăm seama dacă o configurație există deja în coadă și (2) cum se face reconstituirea soluției.

Pentru a afla dacă o configurație mai există în listă, cea mai simplă metodă ar fi o căutare secvențială a listei. Totuși, această versiune ar fi extrem de lentă, deoarece coada atinge rapid dimensiuni respectabile (de ordinul miilor de elemente). În plus, un element al listei ar reține configurația propriu-zisă (un vector cu opt elemente), ceea ce ar duce la un consum ridicat de memorie. Testul de egalitate a doi vectori ar fi și el costisitor din punct de vedere al timpului.

Există însă o altă metodă mai simplă. Am demonstrat că numărul de configurații posibile ale tablei este 8! = 40320. Dacă am putea găsi o funcție bijectivă H:{\mathbf  {P_{8}}}\to \{0,1,\dots ,40319\}, unde {\mathbf  {P_{8}}} este mulțimea permutărilor de 8 elemente, atunci ar fi suficient un vector caracteristic cu 40320 elemente. De îndată ce introducem în coadă o nouă configurație K, nu avem decât să bifăm elementul corespunzător din vectorul caracteristic. Înainte de a adăuga o configurație în coadă, testăm dacă nu cumva elementul corespunzător ei a fost deja bifat, semn că nodul a mai fost vizitat.

Cum se construiește funcția H? Pentru orice permutare p\in {\mathbf  {P_{8}}}, H(p) este poziția lui p în ordonarea lexicografică a lui {\mathbf  {P_{8}}} (începând de la 0):

H(1, 2, 3, 4, 5, 6, 7, 8) = 0
H(1, 2, 3, 4, 5, 6, 8, 7) = 1
H(1, 2, 3, 4, 5, 7, 6, 8) = 2
....................................
H(8, 7, 6, 5, 4, 3, 1, 2) = 40318
H(8, 7, 6, 5, 4, 3, 2, 1) = 40319

Se observă că primele 7! = 5040 elemente din ordonare au pe prima poziție un 1, următoarele 5040 au pe prima poziție un 2 etc. De asemenea, dintre elementele care au pe prima poziție un 1, primele 6! = 720 au pe a doua poziție un 2, următoarele 720 au pe a doua poziție un 3 etc.

Să calculăm de exemplu H(2, 6, 8, 4, 5, 7, 3, 1). Prima cifră a permutării este 2, deci se adaugă 7! = 5040. Rămân cifrele 1, 3, 4, 5, 6, 7 și 8. A doua cifră a permutării este 6, a cincea ca valoare dintre cifrele rămase, deci se adaugă 4 x 6! = 2880. Rămân cifrele 1, 3, 4, 5, 7 și 8 etc. Se aplică procedeul până la ultima cifră și rezultă:

Cifre rămase Permutarea Valoarea adăugată
1, 2, 3, 4, 5, 6, 7, 8 2 1 x 7! = 5040
1, 3, 4, 5, 6, 7, 8 6 4 x 6! = 2880
1, 3, 4, 5, 7, 8 8 5 x 5! = 600
1, 3, 4, 5, 7 4 2 x 4! = 48
1, 3, 5, 7 5 2 x 3! = 12
1, 3, 7 7 2 x 2! = 4
1, 3 3 1 x 1! = 1
1 1 0 x 0! = 0
H(p) = 8585

Reciproc se construiește permutarea când i se cunoaște valoarea atașată:

Cifre nefolosite H(p) Cifra selectată
1, 2, 3, 4, 5, 6, 7, 8 8585 8585 div 7! = 1 2 8585 mod 7! = 3545
1, 3, 4, 5, 6, 7, 8 3545 3545 div 6! = 4 6 3545 mod 6! = 665
1, 3, 4, 5, 7, 8 665 665 div 5! = 5 8 665 mod 5! = 65
1, 3, 4, 5, 7 65 65 div 4! =2 4 65 mod 4! = 17
1, 3, 5, 7 17 17 div 3! = 2 5 17 mod 3! = 5
1, 3, 7 5 5 div 2! = 2 7 5 div 2! = 1
1, 3 1 1 div 1!=1 3 1 mod 1! = 0
1 0 0 div 0!=0 1

Rezultă p=(2, 6, 8, 4, 5, 7, 3, 1).

Această metodă de căutare are și avantajul că în listă se va ține un singur număr pe doi octeți, făcându-se economie de memorie. Expandarea unui nod constă din trei pași:

  1. Se extrage primul număr din listă și se reconstituie configurația atașată;
  2. Se fac cele trei mutări, obținându-se trei succesori;
  3. Pentru fiecare succesor se calculează funcția H și dacă configurația nu este găsită în listă, este adăugată.

Pentru a face reconstituirea soluției avem nevoie de date suplimentare. Respectiv, vectorul caracteristic atașat permutărilor nu va mai reține doar dacă o poziție a fost „văzută” sau nu, ci și poziția din care ea provine (prin valoarea funcției H). Trebuie de asemenea reținut tipul mutării (A, B sau C) prin care s-a ajuns în acea configurație. Cei doi vectori se numesc Father și MoveKind. Inițial, toate elementele vectorului Father au eticheta „Unknown”, semnificând că nodurile nu au fost încă vizitate, cu excepția elementului atașat configurației inițiale, care poartă eticheta specială „Root” (rădăcină).

Pseudocodul pentru expandarea unui nod arată cam așa:

K ← primul numar din coada
P ← H-1(K)
afla cei trei succesori QA, QB, QC
pentru i=A,B,C
  daca Father[H(Qi)]=Unknown atunci
    Father[H(Qi)] ← K
    MoveKind[H(Qi)] ← i
    adauga H(Qi) in coada
sterge K din coada

Reconstituirea soluției se face recursiv: se pornește de la configurația finală și se merge înapoi (folosind informația din vectorul Father) până la configurația inițială, măsurându-se astfel numărul de mutări. La revenire se tipăresc toate mutările efectuate (folosind informația din vectorul MoveKind).

#include <stdio.h>
#include <stdlib.h>
#define Unknown 0xFFFF
#define Root 0xFFFE

typedef huge unsigned Vector[40320];
typedef char CharVector[40320];
typedef int Perm[8];
typedef struct list { unsigned X; struct list * Next; } List;

Perm StartPerm={1,2,3,4,5,6,7,8}, EndPerm;
const Perm Moves[3]=
   {{7,6,5,4,3,2,1,0},
    {3,0,1,2,5,6,7,4},
    {0,6,1,3,4,2,5,7}};
/* Cele trei tipuri de mutari */
Vector Father; /* Legaturile de tip tata */
CharVector MoveKind;
unsigned StartValue,EndValue;
/* Valorile atasate configuratiilor initiala si finala */
List *Head, *Tail; /* Coada de expandat */

/**** Bijectia care asociaza un numar unei permutari ****/

unsigned Perm2Int(Perm P)
{ int i,j,k,Fact=5040;
  unsigned Sum=0;

  for (i=0;i<=6;i++)
    { k=P[i]-1;
      for (j=0;j<i;j++)
        if (P[j]<P[i]) k--;
      Sum+=k*Fact;
      Fact/=(7-i);
    }
  return Sum;
}

void Int2Perm(unsigned Sum, Perm P)
{ int i,j,k,Order,Fact=5040;
  Perm Used={0,0,0,0,0,0,0,0};

  for (i=0;i<=7;i++)
    { Order=Sum/Fact;
      j=-1;
      for (k=0;k<=Order;k++)
        do j++; while (Used[j]);
      Used[j]=1;
      P[i]=j+1;
      Sum%=Fact;
      if (i!=7) Fact/=(7-i);
    }
}

/**** Lucrul cu liste ****/

void InitList(void)
{
  Head=Tail=malloc(sizeof(List));
  Tail->X=StartValue;
  Tail->Next=NULL;
}

void AddToTail(unsigned K)
{
  Tail->Next=malloc(sizeof(List));
  Tail=Tail->Next;
  Tail->X=K;
  Tail->Next=NULL;
}

void Behead(void)
/* Sterge capul listei */
{ List *LCor=Head;

  Head=Head->Next;
  free(LCor);
}

/**** Cautarea propriu-zisa ****/

void MakeMove(Perm P,Perm Q,int Kind)
/* Kind = 0, 1 sau 2 */
{ int i;
  for (i=0;i<=7;i++)
    Q[i]=P[Moves[Kind][i]];
}

void Expand(void)
{ List *LCor;
  Perm P1,P2;
  unsigned i,XSon,Done;

  InitList();
  do {
    Int2Perm(Head->X,P1);
    for(i=0;i<=2;i++)
      { MakeMove(P1,P2,i);
        XSon=Perm2Int(P2);
        if (Father[XSon]==Unknown)
          { Father[XSon]=Head->X;
            MoveKind[XSon]=i+65;
            AddToTail(XSon);
          }
      }
    Done=(Head->X==EndValue);
    Behead(); }
  while (!Done);
}

/* Intrarea si iesirea */

void InitData(void)
{ FILE *F=fopen("input.txt","rt");
  unsigned i;

  for (i=0;i<=7;i++) fscanf(F,"%d",&EndPerm[i]);
  fclose(F);
  StartValue=Perm2Int(StartPerm);
  EndValue=Perm2Int(EndPerm);
  for (i=0;i<40320;) Father[i++]=Unknown;
  Father[StartValue]=Root;
}

void WriteMove(FILE *F,unsigned K,int Len)
{
  if (K!=StartValue)
    { WriteMove(F,Father[K],Len+1);
      fprintf(F,"%c\n",MoveKind[K]);
    }
    else fprintf(F,"%d\n",Len);
}

void Restore(void)
{ FILE *F=fopen("output.txt","wt");

  WriteMove(F,EndValue,0);
  fclose(F);
}

void main(void)
{
  InitData();
  Expand();
  Restore();
}


Problema 4

Continuăm cu o problemă care a fost de asemenea dată spre rezolvare la a VIII-a Olimpiadă Internațională de Informatică, Veszprem 1996. Problema în sine nu a fost foarte grea și mulți elevi au luat punctaj maxim. Totuși, enunțul permite unele modificări interesante care practic schimbă cu totul problema.

ENUNȚ: Să considerăm următorul joc de două persoane. Tabla de joc constă într-o secvență de întregi pozitivi. Cei doi jucători mută pe rând. Mutarea fiecărui jucător constă în alegerea unui număr de la unul din cele două capete ale secvenței. Numărul ales este șters de pe tablă. Jocul se termină când toate numerele au fost selectate. Primul jucător câștigă dacă suma numerelor alese de el este mai mare sau egală cu cea a numerelor alese de cel de-al doilea jucător. În caz contrar, câștigă al doilea jucător.

Dacă tabla conține inițial un număr par de elemente, atunci primul jucător are o strategie de câștig. Trebuie să scrieți un program care implementează strategia cu care primul jucător câștigă jocul. Răspunsurile celui de-al doilea jucător sunt date de un program rezident. Cei doi jucători comunică prin trei proceduri ale modulului Play care v-a fost pus la dispoziție. Procedurile sunt StartGame, MyMove și YourMove. Primul jucător începe jocul apelând procedura fără parametri StartGame. Dacă alege numărul de la capătul din stânga, el va apela procedura MyMove('L'). Analog, apelul de procedură MyMove('R') trimite un mesaj celui de-al doilea jucător prin care îl informează că a ales numărul de la capătul din dreapta. Cel de-al doilea jucător, deci computerul, mută imediat, iar primul jucător poate afla mutarea acestuia executând procedura YourMove(C), unde C este o variabilă de tip Char (în C/C++ apelul este YourMove(&C)). Valoarea lui C este 'L' sau 'R', după cum numărul ales este de la capătul din stânga sau din dreapta.

Intrarea: Prima linie din fișierul INPUT.TXT conține dimensiunea inițială N a tablei. N este par și 2 ≤ N ≤ 100. Următoarele N linii conțin fiecare câte un număr, reprezentând conținutul tablei de la stânga la dreapta. Fiecare număr este cel mult 200.

Ieșirea: Când jocul se termină, programul trebuie să scrie rezultatul final în fișierul OUTPUT.TXT. Fișierul conține două numere pe prima linie, reprezentând suma numerelor alese de primul, respectiv de cel de-al doilea jucător. Programul trebuie să joace un joc corect și ieșirea trebuie să corespundă jocului jucat.

Exemplu:

INPUT.TXT OUTPUT.TXT
6
4
7
2
9
5
2
15 14

Timp limită de execuție: 20 secunde pentru un test.

Acesta a fost enunțul original, la care va trebui să facem câteva modificări, în parte deoarece nu putem folosi modulul Play, în parte pentru a face problema mai restrictivă:

  • Mutările vor fi anunțate pe ecran prin tipărirea unui caracter 'L' sau 'R';
  • Mutările celui de-al doilea jucător vor fi comunicate de un partener uman, prin introducerea de la tastatură a unui caracter 'L' sau 'R';
  • Rezultatul final se va tipări pe ecran, sub aceeași formă (pereche de numere).
  • Timpul de gândire pentru fiecare mutare trebuie să fie cât mai mic (practic răspunsul să fie instantaneu);
  • Complexitatea totală a calculelor efectuate să fie O(N).
  • Timpul de implementare a fost cam de 1h 40 min. Propunem reducerea lui la 30 minute.

REZOLVARE: Este ușor de demonstrat că o rezolvare „greedy” a problemei (la fiecare mutare jucătorul 1 alege numărul mai mare) nu atrage întotdeauna câștigul. Iată un contraexemplu:

Psycho-fig49.png

La prima mutare, jucătorul 1 poate să aleagă fie numărul 7, fie numărul 2. Dacă se va „lăcomi” la 7, jucătorul 2 va lua numărul 10 și inevitabil va câștiga. Soluția pentru primul jucător este să ia numărul 2, apoi, indiferent de ce va juca partenerul său, va putea lua numărul 10 și va câștiga.

Iată o soluție izbitor de simplă de complexitate O(N): La citirea datelor se face suma elementelor aflate pe poziții pare și a celor aflate pe poziții impare. Să presupunem că suma elementelor de ordin par este mai mare sau egală cu cea a elementelor de ordin impar (cazul invers se tratează analog). Atunci, dacă primul jucător ar putea să aleagă toate elementele de ordin par (care sunt într-adevăr N/2, adică atâtea câte are el dreptul să aleagă), ar câștiga jocul. Jucătorul 1 poate începe jocul prin a lua primul sau ultimul element din secvență, deci îl va alege pe ultimul, care are număr de ordine par. Al doilea jucător are de ales între primul și al N-1-lea element, ambele având număr de ordine impar. Indiferent ce variantă o va adopta, primul jucător va avea din nou acces la un element de pe o poziție pară. Dacă jucătorul 2 alege elementul din stânga (primul), atunci jucătorul 1 va putea lua elementul de după el (al doilea), iar dacă jucătorul 2 alege elementul din dreapta (al N-1-lea), atunci jucătorul 1 va putea lua elementul dinaintea el (al N-2-lea). Deci primul jucător nu are altceva de făcut decât să repete mutările făcute de cel de-al doilea. Să privim de exemplu desfășurarea jocului pe tabla dată în enunț:

Psycho-fig50.png

Programul în sine nici nu are nevoie să mai rețină vectorul de numere în memorie, din moment ce primul jucător nu are altceva de făcut decât să imite mutările celui de-al doilea. Un calcul al sumelor la citirea datelor este suficient. Complexitatea O(N) este optimă, deoarece vectorul trebuie parcurs cel puțin o dată pentru citirea configurației inițiale a tablei.

#include <stdio.h>

void main(void)
{ FILE *F=fopen("input.txt","rt");
  int SEven,SOdd,N,i,K;

  fscanf(F,"%d\n",&N);
  for (i=1, SEven=SOdd=0; i<=N; i++)
    { fscanf(F, "%d\n", &K);
      if (i&1) SOdd+=K;
        else SEven+=K;
    }
  fclose(F);

  printf("Mutarea mea: %c\n", SEven>=SOdd ? 'R' : 'L');
  for (i=1; i<N/2; i++)
    { printf("Mutarea dvs. (L/R) ? ");
      printf("Mutarea mea: %c\n", getchar());
      getchar(); /* Caracterul newline */
    }
  printf("Mutarea dvs. (L/R) ? ");
  getchar();

  if (SEven>=SOdd)
    printf("%d %d\n", SEven, SOdd);
    else printf("%d %d\n", SOdd, SEven);
}

O a doua variantă a enunțului aduce unele condiții suplimentare:

  • Se cere să se tipărească numai diferența maximă de scor pe care o poate obține primul jucător, considerând că ambii parteneri joacă perfect;
  • Complexitatea cerută este O(N^{2}).
  • Timpul de implementare este de 45 minute, maxim 1h.


REZOLVARE: Trebuie mai întâi să lămurim ce se înțelege prin „joc perfect”. Jucătorul 1 are întotdeauna victoria la îndemână (metoda este arătată mai sus), dar nu la orice scor. Jucătorul 2 urmărește să minimizeze diferența de scor. Fie D diferența de scor cu care se termină un joc. D poate lua diferite valori pentru aceeași configurație inițială a tablei, în funcție de mutările făcute de cei doi jucători. Fie D_{{MAX}} diferența maximă de scor pe care o poate obține primul jucător indiferent de mutările celui de-al doilea. Exact această valoare trebuie aflată. D_{{MAX}} nu este propriu-zis o diferență maximă. Jucătorul 1 poate să câștige și la diferențe mai mari decât D_{{MAX}}, dar trebuie ca jucătorul 2 să-l „ajute”. Să reluăm exemplul cu 4 numere:

Psycho-fig51.png

În acest caz, primul jucător are asigurat scorul 12-8 (deci diferența 4). Pentru aceasta, el începe prin a lua numărul 2, apoi, orice ar replica celălalt, va lua numărul 10, jucătorului 2 revenindu-i așadar numerele 1 și 7. El poate obține și scorul 17-3 (jucătorul 1 ia numărul 7, celălalt ia 2, jucătorul 1 ia 10, iar celălalt ia 1), dar aceasta se întâmplă numai dacă jucătorul 2 face o greșeală. După cum am arătat mai sus, dacă primul jucător începe luând numărul 7, el pierde în mod normal partida. Iată deci că în acest caz D_{{MAX}}=4.

Pentru a putea afla diferența maximă de scor, este bine să privim mereu în adâncime. Există patru variante în care ambii parteneri pot face câte o mutare:

  1. Ambii jucători aleg numere din partea stângă;
  2. Ambii aleg numere din partea dreaptă;
  3. Primul jucător alege numărul din stânga, iar celălalt pe cel din dreapta;
  4. Primul jucător alege numărul din dreapta, iar celălalt pe cel din stânga;

În urma oricărei variante de mutare, secvența se scurtează cu două elemente. Dacă am putea cunoaște dinainte care este rezultatul jocului pentru fiecare din secvențele scurte, am putea să decidem care variantă de joc este cea mai convenabilă pentru secvența inițială, ținând cont și de modul de joc al jucătorului al doilea. Tocmai de aici vine și ideea de rezolvare. Să notăm cu A[1], A[2], ..., A[N] secvența citită la intrare. Vom construi o matrice D cu N linii și N coloane, unde D[i,j] este diferența maximă pe care o poate obține jucătorul 1 pentru secvența A[i], A[i+1], ..., A[j]. Bineînțeles, sunt luate în considerare numai secvențele de lungime pară. Scopul nostru este să-l aflăm pe D[1,N].

Elementele matricei pe care le putem afla fără multă bătaie de cap sunt D[1,2], D[2,3], ..., D[N-1,N]. Într-adevăr, dintr-o secvență de numai două numere, primului jucător îi revine cel mai mare, iar celui de-al doilea - cel mai mic. Așadar

D[i,i+1]=|A[i]-A[i+1]|

Cum calculăm D[i,j] dacă cunoaștem valorile matricei D pentru toate subsecvențele incluse în secvența A[i], A[i+1], ..., A[j] ? După cum am mai spus, avem patru variante:

Psycho-fig52.png

Trebuie să ținem minte că, dacă primul jucător optează să-l aleagă pe A[i] (una din primele două variante), atunci jucătorul 2 va juca în așa fel încât pierderea să fie minimă, iar scorul final va fi \min(R_{1},R_{2}). Dacă jucătorul 1 alege varianta 3 sau 4, scorul final va fi \min(R_{3},R_{4}). Dar jucătorul 1 este primul la mutare, deci va alege varianta care îi maximizează profitul. Rezultatul este

D[i,j]=\max(\min(R_{1},R_{2}),\min(R_{3},R_{4}))

adică

{\begin{aligned}D[i,j]=\max(&A[i]+\min(D[i+2,j]-A[i+1],D[i+1,j-1]-A[j]),\\&A[j]+\min(D[i+1,j-1]-A[i],D[i,j-2]-A[j-1]))\end{aligned}}

Matricea D se completează pe diagonală, pornind de la diagonala principală și mergând până în colțul de N-E. Iată cum arată matricea atașată datelor de intrare din enunț:

D={\begin{pmatrix}X&3&X&10&X&7\\X&X&5&X&9&X\\X&X&X&7&X&4\\X&X&X&X&4&X\\X&X&X&X&X&3\\X&X&X&X&X&X\end{pmatrix}}

Pentru exemplul din enunț, răspunsul este deci D_{{MAX}}=7. Cum elementele matricei sunt parcurse cel mult o dată, rezultă o complexitate de O(N^{2}).

#include <stdio.h>
#include <stdlib.h>
#define NMax 101

int D[NMax][NMax], A[NMax], N;

void ReadData(void)
{ FILE *F=fopen("input.txt","rt");
  int i;

  fscanf(F,"%d\n",&N);
  for (i=1; i<=N;)
    fscanf(F, "%d\n", &A[i++]);
  fclose(F);
}

int Min(int A, int B)
{
  return A<B ? A : B;
}

int Max(int A, int B)
{
  return A>B ? A : B;
}

void FindMax(void)
{ int i,j,k;

  for (i=1;i<N;i++)
    D[i][i+1]=abs(A[i]-A[i+1]);
  for (k=3;k<=N-1;k++)
    for (i=1;i+k<=N;i++)
      { j=i+k;
        D[i][j]=Max(A[i]+Min(D[i+2][j]-A[i+1],
                             D[i+1][j-1]-A[j]),
                    A[j]+Min(D[i+1][j-1]-A[i],
                             D[i][j-2]-A[j-1]));
      }
  printf("Diferenta maxima este %d\n",D[1][N]);
}

void main(void)
{
  ReadData();
  FindMax();
}

Programul prezentat mai sus poate fi optimizat, dacă timpul o permite și dacă acest lucru este necesar. Lăsăm cititorul să încerce să rezolve aceeași problemă folosind o cantitatate de memorie direct proporțională cu N.


Problema 5

Această problemă a fost propusă la Olimpiada Națională de Informatică, Slatina 1995, la clasa a XI-a. Pe atunci programarea dinamică era o tehnică de programare destul de puțin cunoscută de către majoritatea elevilor.

ENUNȚ: O regiune deșertică este reprezentată printr-un tablou de dimensiuni MxN (1 ≤ M ≤ 100, 1 ≤ N ≤ 100). Elementele tabloului sunt numere naturale mai mici ca 255, reprezentând diferențele de altitudine față de nivelul mării (cota 0). Să se stabilească:

a) Un traseu pentru a traversa deșertul de la nord la sud (de la linia 1 la linia M), astfel:

  • Se pornește dintr-un punct al liniei 1;
  • Deplasarea se poate face în una din direcțiile: E, SE, S, SV, V;
  • Suma diferențelor de nivel (la urcare și la coborâre) trebuie să fie minimă.

b) Un traseu pentru a traversa deșertul de la nord la sud în condițiile punctului (a), la care se adaugă condiția:

  • Lungimea traseului să fie minimă.

Intrarea: Fișierul de intrare INPUT.TXT conține un singur set de date cu următoarea structură:

linia 1: M N
linia 2 ... linia M+1: elementele tabloului (pe linii) separate prin spații

Ieșirea: Fișerul de ieșire OUTPUT.TXT va conține rezultatele în următorul format:

(a)
<suma diferențelor de nivel>
TRASEU: (i_{1},j_{1})\to (i_{2},j_{2})\to \cdots \to (i_{k},j_{k})
(b)
<suma diferențelor de nivel> <lungime traseu>
TRASEU: (i_{1},j_{1})\to (i_{2},j_{2})\to \cdots \to (i_{p},j_{p})


unde i_{x} și j_{x} sunt linia și coloana fiecărei celule vizitate.

Exemplu:

INPUT.TXT OUTPUT.TXT
4 4

10 7 2 5
13 20 25 3
2 4 2 20
5 10 9 11

(a)

5
TRASEU: (1,3)->(2,4)->(3,3)->(3,2)->(4,1)
(b)
9 3
TRASEU: (1,3)->(2,4)->(3,3)->(4,2)

Acesta a fost enunțul original. Iată acum completările propuse și o precizare importantă:

  • Timpul de implementare: 45 minute - 1h (la concurs a fost cam 1h 30 min);
  • Timpul de rulare: 2-3 secunde;
  • Complexitatea cerută: O(N^{2});
  • La punctul (b), condiția nou adăugată este mai puternică decât cea de la punctul (a). Cu alte cuvinte, în primul rând contează lungimea drumului și abia apoi, dintre toate drumurile de lungime minimă, trebuie ales cel pentru care suma denivelărilor este minimă. Pentru a vă convinge că ordinea în care sunt impuse condițiile este importantă, să privim exemplul de mai sus. Dacă este mai importantă minimizarea sumei denivelărilor, atunci minimul este 5, iar drumul este soluția de la punctul (a). Dacă este mai importantă minimizarea lungimii drumului, atunci lungimea minimă este 3, iar din toate drumurile de lungime 3, cel mai puțin costisitor este cel indicat la punctul (b).

REZOLVARE: Vom lăsa punctul (b) al acestei probleme în seama cititorului, întrucât el nu este altceva decât o simplificare a punctului (a). Să ne ocupăm acum de punctul (a). Vom numi efort diferența de altitudine (în modul) la deplasarea cu un pas. Scopul este deci găsirea unor drumuri de efort total minim. Matricea de altitudini o vom nota cu Alt.

O primă posibilitate de abordare a problemei este „greedy”, dar aceasta nu e cea mai fericită alegere, chiar dacă este una comodă. Ideea de bază este următoarea: Încercăm să pornim din colțul de NV și să ne deplasăm la fiecare pas pe acea direcție pentru care efortul este minim, până ajungem la ultima linie. Apoi pornim din a doua coloană a primei linii și aplicăm aceeași tactică, apoi din a treia coloană și așa mai departe până la colțul de NE. În final tipărim soluția cea mai bună găsită. Iată însă un exemplu pe care această metodă dă greș:

Alt={\begin{pmatrix}2&1&2\\10&1&10\\10&10&10\end{pmatrix}}

Pe această matrice, algoritmul greedy va găsi traseele (1,1) → (2,2) → (3,2) de efort total 10, (1,2) → (2,2) → (3,2) de efort total 9 și (3,1) → (2,2) → (3,2) de efort total 10. Așadar, rezultatul optim ar fi 9, ceea ce este fals deoarece alegerea traseului (1,1) → (2,1) → (3,1) ar duce la un efort total de 8, deci mai mic.

Motivul pentru care acest algoritm nu funcționează cum trebuie este că el nu privește în perspectivă. În cazul de mai sus, coborârea în „văile” de altitudine 1 era o primă mutare tentantă, dar fără nici un rezultat, deoarece până la urmă tot era necesară suirea la altitudinea 10. Soluția corectă este ca, pentru a afla efortul minim cu care se poate ajunge la o locație oarecare, să analizăm toate drumurile care duc la acea locație. Dacă am cunoaște efortul minim cu care se poate ajunge la fiecare din vecinii din E, NE, N, NV, și V ai unei celule, atunci putem cu ușurință, pe baza unor comparații, să deducem din ce parte este cel mai avantajos să venim în respectiva celulă și cu ce efort minim.

Mai concret, vom construi o matrice cu aceleași dimensiuni ca și matricea Alt, pe care o vom denumi Eff. În această matrice, Eff[i,j] reprezintă efortul minim necesar pentru a ajunge de pe un punct oarecare de pe linia 1 în celula (i,j). Deducem că Eff[1,j]=0, ∀ 1 ≤ jN. Noi trebuie să completăm matricea Eff, apoi să căutăm minimul dintre toate elementele de pe linia M (care este chiar efortul minim căutat) și să reconstituim traseul de urmat.

Ca să vedem cum anume se face completarea matricei, facem mai întâi observația că, odată ce am ajuns pe o linie, putem fie să coborâm direct pe linia imediat inferioară, fie să ne deplasăm câțiva pași numai spre stânga sau numai spre dreapta, apoi să coborâm pe linia următoare. În orice locație (X,Y) a matricei putem veni dinspre E, NE, N, NV, sau V. Pentru acești cinci vecini presupunem deja calculate eforturile minime necesare, respectiv Eff[X,Y+1], Eff[X-1,Y+1], Eff[X-1,Y], Eff[X-1,Y-1], Eff[X,Y-1]. Atunci, în funcție de direcția din care venim, efortul depus până la punctul (X,Y) va fi:

dinspre est: Alt[X,Y+1] - Alt[X,Y]|; (1)
dinspre nord-est: Alt[X-1,Y+1] - Alt[X,Y]|; (2)
dinspre nord: Alt[X-1,Y] - Alt[X,Y]|; (3)
dinspre nord-vest: Alt[X-1,Y-1] - Alt[X,Y]|; (4)
dinspre vest: Alt[X,Y-1] - Alt[X,Y]|; (5)

În principiu, nu avem decât să calculăm minimul dintre aceste expresii ca să aflăm valoarea lui Eff[X,Y]. În felul acesta, matricea Eff se va completa pe linie, de sus în jos. Totuși, apare o problemă: pentru a-l afla pe </tt>Eff[X,Y]</tt> avem nevoie de Eff[X,Y-1] (dacă ne deplasăm spre est), iar pentru a-l afla pe Eff[X,Y-1] avem nevoie de Eff[X,Y] (dacă ne deplasăm spre vest)! Bineînțeles, avem sentimentul că ne învârtim după propria coadă. Totuși, dezlegarea nu e complicată, ținând cont de observația făcută mai sus, că pe aceeași linie deplasarea se face într-o singură direcție. Este suficient să parcurgem fiecare linie de două ori: prima oară o parcurgem de la stânga la dreapta, în ipoteza că deplasarea pe linia respectivă se face spre est, apoi încă o dată de la dreapta la stânga, în ipoteza că deplasarea pe linia respectivă se face spre vest. La prima parcurgere, vom minimiza efortul pentru fiecare căsuță cu expresia (5), iar la a doua - cu expresia (1). Minimizarea cu expresiile (2), (3) și (4) se poate face la oricare din parcurgeri, deoarece elementele liniei superioare nu se mai modifică.

După cum am spus, efortul minim se obține căutând minimul de pe ultima linie a matricei Eff (aceasta deoarece nu contează în ce punct de pe ultima linie este sosirea). Punctul în care se atinge acest minim este tocmai punctul de sosire. Reconstituirea efectivă a drumului se face în sens invers: se pleacă din punctul de sosire (i_{k},j_{k}) și se caută un punct vecin lui pe una din cele cinci direcții permise, (i_{{k-1}},j_{{k-1}}) astfel încât

{\mathit  {Eff}}[i_{k},j_{k}]={\mathit  {Eff}}[i_{{k-1}},j_{{k-1}}]+|Alt[i_{k},j_{k}]-Alt[i_{{k-1}},j_{{k-1}}]|

Cu alte cuvinte, se testează pentru care din expresiile (1) - (5) se verifică egalitatea. Se reia, recursiv, același procedeu pentru locația (i_{{k-1}},j_{{k-1}}).

Iată cum se completează matricea Eff pentru exemplul dat și cum se reconstituie drumul:

Alt={\begin{pmatrix}10&7&2&5\\13&20&25&3\\2&4&2&20\\5&10&9&11\end{pmatrix}}

{\mathit  {Eff}}={\begin{pmatrix}0&0&0&0\\3&10&15&1\\6&4&2&18\\5&10&9&11\end{pmatrix}}

Minimul de pe linia a 4-a a matricei Eff este Eff[4,1]=5, deci sosirea se face în colțul de SV. Din ce parte am ajuns aici ? Se testează toți vecinii și se constată că Eff[4,1] = Eff[3,2] + |Alt[4,1] - Alt[3,2]|, deci s-a venit de la locația (3,2). Apoi se constată că:

  • Eff[3,2] = Eff[3,3] + |Alt[3,2] - Alt[3,3]|;
  • Eff[3,3] = Eff[2,4] + |Alt[3,3] - Alt[2,4]|;
  • Eff[2,4] = Eff[1,3] + |Alt[2,4] - Alt[1,3]|;

Din aceste relații rezultă că traseul urmat este (1,3) → (2,4) → (3,3) → (3,2) → (4,1).

Pentru o mai mare ușurință a implementării, se vor adăuga două coloane fictive la matricea Alt: coloanele 0 și N+1. Facem acest lucru pentru a ne putea referi la celula (X,Y-1) atunci când (X,Y) este o celulă din prima coloană (respectiv la celula (X,Y+1) atunci când (X,Y) este o celulă de pe ultima coloană) fără a primi un mesaj de eroare. Trebuie însă să fim atenți ca nu cumva noile coloane adăugate să perturbe datele de ieșire și să rezulte că traseul optim trece prin coloana 0 sau N+1. Pentru a scăpa de grija celulelor de pe aceste două coloane și a ne asigura că ele nu vor putea fi selectate pentru traseul optim, le vom atribui altitudini foarte mari. Deoarece diferența maximă de nivel la fiecare pas este 255, rezultă că efortul total maxim ce se poate obține este 255 x 99 = 25.245. Așadar, o altitudine a coloanelor laterale de 30.000 este suficientă.

#include <stdio.h>
#include <math.h>
#define NMax 101
#define Infinity 30000
typedef int Matrix[NMax][NMax+1];

Matrix Alt, Eff;
int M, N;
FILE *OutF;

void ReadData(void)
{ FILE *F=fopen("input.txt", "rt");
  int i,j;

  fscanf(F, "%d %d\n", &M, &N);
  for (i=1; i<=M; i++)
    for (j=1; j<=N; j++)
      fscanf(F, "%d", &Alt[i][j]);
  fclose(F);
}

void Optimize(int X1, int Y1, int X2, int Y2)
/* Testeaza daca in (X1,Y1) se poate ajunge
   cu efort mai mic dinspre (X2,Y2) */
{
  if (Eff[X2][Y2]+abs(Alt[X1][Y1]-Alt[X2][Y2])<Eff[X1][Y1])
    Eff[X1][Y1]=Eff[X2][Y2]+abs(Alt[X1][Y1]-Alt[X2][Y2]);
}

void Traverse(void)
{ int i,j;

  for (j=1; j<=N;) Eff[1][j++]=0;
  for (i=1; i<=M; i++)
    Eff[i][0]=Eff[i][N+1]=Infinity; /* Bordeaza matricea */
  for (i=2; i<=M; i++)
    {
      for (j=1; j<=N; j++)
        {
          Eff[i][j]=Infinity;
          Optimize(i, j, i-1, j);       /* De la N  */
          Optimize(i, j, i-1, j-1);     /* De la NV */
          Optimize(i, j, i-1, j+1);     /* De la NE */
          Optimize(i, j, i, j-1);       /* De la V  */
        }
      for (j=N; j; j--)
        Optimize(i, j, i, j+1);         /* De la E  */
    }
}

void GoBack(int X, int Y)
/* Reconstituie drumul */
{
  if (X>1)
    if (Eff[X][Y]==Eff[X][Y-1]
                   +abs(Alt[X][Y-1]-Alt[X][Y]))
    GoBack(X, Y-1);
    else if (Eff[X][Y]==Eff[X-1][Y-1]
                        +abs(Alt[X-1][Y-1]-Alt[X][Y]))
    GoBack(X-1, Y-1);
    else if (Eff[X][Y]==Eff[X-1][Y]
                        +abs(Alt[X-1][Y]-Alt[X][Y]))
    GoBack(X-1, Y);
    else if (Eff[X][Y]==Eff[X-1][Y+1]
                        +abs(Alt[X-1][Y+1]-Alt[X][Y]))
    GoBack(X-1, Y+1);
    else if (Eff[X][Y]==Eff[X][Y+1]
                        +abs(Alt[X][Y+1]-Alt[X][Y]))
    GoBack(X, Y+1);
  if (X>1) fprintf(OutF, "->");
  fprintf(OutF,"(%d,%d)", X, Y);
}

void WriteSolution(void)
{ int j,k;

  OutF=fopen("output.txt", "wt");
  /* Cauta punctul de sosire */
  fputs("(a)\n",OutF);
  for (j=2, k=1; j<=N; j++)
    if (Eff[M][j]<Eff[M][k]) k=j;
  fprintf(OutF, "%d\n", Eff[M][k]);
  fputs("TRASEU: ",OutF);
  GoBack(M, k);
  fprintf(OutF,"\n");
  fclose(OutF);
}

void main(void)
{
  ReadData();
  Traverse();
  WriteSolution();
}


Problema 6

Propunem în continuare o problemă care s-a dat la Olimpiada Națională de Informatică, Suceava 1996, la clasa a XII-a. Menționăm că un singur concurent a reușit să o ducă la bun sfârșit în timpul concursului. Problema se numește „Cartierul Enicbo”.

ENUNȚ: În orașul Acopan s-a construit un nou cartier. Noul cartier are patru bulevarde paralele și un număr de N străzi perpendiculare pe ele. Există deci în total 4N intersecții. Furgoneta oficiului poștal trebuie să distribuie poșta în fiecare zi; în acest scop, furgoneta pleacă de la oficiul poștal aflat la intersecția bulevardului 1 cu strada 1 și, urmând rețeaua stradală, trece exact o dată prin fiecare intersecție astfel încât să încheie traseul în punctul de plecare.

Conducerea oficiului poștal roagă participanții la olimpiadă să o ajute să afle în câte moduri distincte se poate stabili traseul furgonetei.

Intrarea: Programul va citi de la tastatură valoarea lui N (2 ≤ N ≤ 200).

Ieșirea: Pe ecran se va afișa soluția (numărul de trasee distincte pentru valoarea respectivă a lui N).

Exemplu: Pentru N=3 există 4 soluții (se citește de la tastatură numărul 3 și se afișează pe ecran numărul 4). Iată soluțiile efective:

Psycho-fig53.png

Timp de execuție: 30 secunde pentru un text

Timp de implementare: 1h 30 min.

Complexitate cerută: O(N^{2})

REZOLVARE: Primul lucru care ne vine în gând este „se cere numărul de cicluri hamiltoniene într-un graf, deci problema e exponențială”. Rezolvarea backtracking nu e deloc greu de implementat, dar nu are nici o șansă să meargă pentru valori mari ale lui N. Afirmația de mai sus este corectă, dar incompletă; din această cauză concluzia este falsă. Se scapă din vedere faptul că graful nu este oarecare, ci are un aspect foarte particular.

Și în această problemă vom încerca să utilizăm soluțiile locale (pentru valori mici ale lui N) pentru aflarea soluției globale. Respectiv, vom rezolva problema pentru N=2, apoi o vom extinde pentru N=3, 4 și așa mai departe. Pentru început, însă, încercăm să simplificăm enunțul, reducând problema la una echivalentă, dar mai simplă.

Să considerăm o posibilă soluție pentru N=5:

Psycho-fig54.png

În loc să lucrăm cu segmente în această rețea, vom lucra cu ochiuri. Furgoneta parcurge un ciclu, deci închide în circuitul ei un număr de ochiuri. Am marcat aceste ochiuri cu un „X” în figura de mai sus. Așadar, oricărui drum al furgonetei i se poate atașa o matrice cu 3 linii și N-1 coloane, în care unele celule sunt bifate cu „X”, iar altele nu. Să vedem în primul rând care este corespondența între numărul de circuite hamiltoniene și numărul de matrice de acest tip.

Se observă că pentru orice circuit există un altul căruia îi este atașată aceeași matrice. Circuitul pereche este tocmai circuitul parcurs în sens invers, care închide în interior aceleași ochiuri de rețea:

Psycho-fig55.png

Acest lucru se întâmplă deoarece transformarea graf-matrice ignoră sensul de parcurgere a circuitului hamiltonian. De aici rezultă că pentru a calcula numărul de circuite hamiltoniene trebuie să calculăm numărul de matrice și să-l înmulțim cu 2.

În continuare, să analizăm câteva proprietăți ale matricelor în discuție.

1. Elementele bifate cu „X” în matrice formează o singură figură conexă.

Demonstrație: dacă figura nu ar fi conexă, adică dacă ar exista mai multe figuri, ele nu ar putea fi înconjurate de furgonetă într-un singur drum. De remarcat că toate pătratele înconjurate de furgonetă trebuie bifate cu X, deci furgoneta nu poate înconjura pătrate nebifate. De aceea, traseul de mai jos (care prezintă o porțiune oarecare de circuit) este imposibil.

Psycho-fig56.png

Conexitatea se referă numai la vecinătatea pe latură, nu și pe colț. Spre exemplu, figura de mai jos este incorectă, deoarece, pentru a o înconjura, furgoneta trebuie să treacă de două ori prin punctul încercuit:

Psycho-fig57.png

2. Elementele bifate cu „X” formează o structură aciclică.

Demonstrație: dacă structura ar fi ciclică, ar rezulta că elementele bifate cu „X” închid între ele elemente nebifate, pe care furgoneta însă nu poate să le ocolească. Iată un exemplu de ciclicitate:

Psycho-fig58.png

Practic, situația de mai sus obligă furgoneta să facă două drumuri: unul pe exterior și unul în jurul ochiului marcat cu „?”.

3. Nici un nod interior al rețelei nu poate avea toate cele patru ochiuri vecine marcate cu „X”.

Demonstrație: dacă ar exista un asemenea nod, el nu ar putea fi parcurs de furgonetă, deci ciclul nu ar mai fi hamiltonian. Este cazul nodului încercuit în figura următoare:

Psycho-fig59.png

4. Structura elementelor bifate cu „X” în cadrul matricei este arborescentă.

Demonstrația rezultă imediat din punctele anterioare: figura este conexă și aciclică.

5. Numărul de celule bifate este P = 2N-1.

Demonstrația se face prin inducție matematică. Să presupunem că structura noastră ar avea un singur pătrat bifat. Atunci structura ar avea patru laturi „la vedere”. Traseul furgonetei care ocolește structura ar avea patru laturi. O structură de două pătrate (desigur lipite) va avea șase laturi la vedere:

Psycho-fig60.png

Să ne imaginăm acum că orice structură cu k pătrate are S_{k} laturi la vedere. Trebuie să demonstrăm că toate structurile cu k+1 pătrate au același număr de laturi la vedere și să aflăm efectiv acest număr, S_{{k+1}}. Cel de-al k+1-lea pătrat trebuie alipit la structura deja existentă în așa fel încât să nu se închidă nici un ciclu. El se va lipi deci de o latură la vedere a unui pătrat din structură. În acest fel, va dispărea o latură la vedere, dar vor apărea trei în loc. Numărul de laturi la vedere va crește prin urmare cu 2. Această cifră nu depinde de locul în care este alipit al k+1-lea pătrat, nici de forma structurii deja existente, deci am demonstrat că toate structurile arborescente cu k pătrate au același număr de laturi la vedere. Pentru a afla efectiv acest număr, pornim de la relațiile recurente stabilite prin inducție și eliminăm recurența:

{\begin{aligned}S_{{k+1}}&=S_{k}+2\\S_{1}&=4\end{aligned}}{\Biggr \}}\implies S_{k}=2k+2

Deoarece numărul total de noduri al rețelei este de 4N, rezultă că structura noastră trebuie să aibă 4N laturi la vedere. Notând cu P numărul de pătrate bifate din matrice și rezolvând ecuația de mai jos, rezultă valoarea lui P:

2P+2=4N\implies P=2N-1=2(N-1)+1

Cum numărul de coloane al matricei este N-1, deducem că în medie pe fiecare coloană se vor afla două pătrate bifate, cu excepția uneia pe care se vor afla trei pătrate bifate. La nivel local, proprietatea este de asemenea respectată: numărul de pătrate bifate din primele k coloane ale matricei este 2k, existând posibilitatea să mai fie un pătrat suplimentar. De exemplu, în figura dată mai sus pentru N=5, în primele două coloane se află patru elemente „X”, deci o medie de două pătrate pe fiecare coloană. În primele trei coloane există șapte elemente „X”, adică o medie de două pătrate pe coloană și un surplus de un pătrat. Lăsăm ca temă cititorului să demonstreze că, în primele k coloane există întotdeauna fie 2k, fie 2k+1 pătrate. Orice număr mai mare duce la ciclicitatea figurii, orice număr mai mic duce la neconexitatea ei.

Pe fiecare coloană există opt combinații posibile de elemente bifate și nebifate, pe care le vom codifica cu numere de la 0 la 7, conform unei numărători binare:

Psycho-fig61.png

Să vedem acum care dintre aceste combinații rămân valabile. O coloană de tipul 0 nu poate exista, deoarece ea ar „rupe” matricea în două bucăți separate, deci proprietatea de conexitate nu ar fi respectată.

Dacă pe coloana k se află o combinație de tipul 3, ce s-ar putea afla pe coloana k+1 ?

Psycho-fig62.png

Pentru ca punctul A să se afle pe traseul furgonetei, este obligatoriu să bifăm pătratul de sub el. Pentru a menține conexitatea figurii apărute, trebuie bifat și pătratul din centrul coloanei k+1. Cea de-a treia celulă a coloanei k+1 nu poate fi bifată, deoarece punctul B ar fi înconjurat din patru părți de celule bifate, lucru care s-a stabilit că este imposibil. Se vede că singura combinație posibilă pentru coloana k+1 este 6. Ce combinație putem pune pe coloana k+2 ? Printr-un raționament analog, deducem că numai combinația 3:

Psycho-fig63.png

Iată că, pentru a putea respecta condițiile de corectitudine a matricei, am fi nevoiți să continuăm la nesfârșit cu coloane cu combinațiile 3-6-3-6 etc. Deci niciuna din aceste combinații nu poate apărea în matrice.

În continuare, vom defini mai multe șiruri de forma S_{k}(i,t), unde:

  • k este numărul unei coloane;
  • i este un număr de combinație (respectiv 1, 2, 4, 5 sau 7);
  • t este un număr care poate avea valoarea 0 sau 1.

S_{k}(i,t) semnifică „numărul de matrice (corecte) cu k coloane astfel încât pe coloana cu numărul k să se afle combinația i, iar surplusul de pătrate bifate peste media de două pătrate pe fiecare coloană să fie t”. De exemplu, S_{7}(5,1) reprezintă numărul de matrice corecte (care respectă regulile de construcție) cu 7 coloane, astfel încât pe ultima coloană să se afle combinația 5 și să existe un surplus de 1 pătrat (adică numărul total de pătrate să fie 2 x 7 + 1 = 15).

Facem observația că pe a N-1-a coloană se pot afla doar combinațiile 5 sau 7 (pentru a acoperi colțurile de NE și SE ale grafului), iar surplusul de pătrate trebuie să fie 1 (deoarece în N-1 coloane trebuie să se afle P=2(N-1)+1 pătrate bifate). Deci scopul nostru este să calculăm suma S_{{N-1}}(5,1)+S_{{N-1}}(7,1) și să o înmulțim cu 2 ca să aflăm numărul de cicluri hamiltoniene.

De asemenea, remarcăm că șirurile S_{k}(1,1), S_{k}(2,1) și S_{k}(4,1) nu sunt definite. Aceasta deoarece combinațiile 1, 2 și 4 au un singur pătrat bifat pe coloană, adică mai puțin decât media de două pătrate. Este imposibil ca după adăugarea unei asemenea coloane să mai existe un surplus. (deoarece ar rezulta că în primele k-1 coloane exista un surplus de două pătrate). La polul opus, șirul S_{k}(7,0) nu este definit, deoarece combinația 7 are toată coloana bifată, adică peste medie, deci nu se poate să nu apară un surplus de pătrate bifate.

Mai trebuie stabilite formulele de recurență între șirurile S_{k}(1,0), S_{k}(2,0), S_{k}(4,0), S_{k}(5,0), S_{k}(5,1) și S_{k}(7,1). Termenii inițiali ai recurenței sunt:

  • S_{1}(1,0)=0 deoarece matricea nu poate începe cu combinația 1
  • S_{1}(2,0)=0 deoarece matricea nu poate începe cu combinația 2
  • S_{1}(4,0)=0 deoarece matricea nu poate începe cu combinația 4
  • S_{1}(5,0)=1 deoarece există o singură matrice de o coloană cu combinația 5
  • S_{1}(5,1)=0 deoarece combinația 5 are două pătrate, deci nu există surplus
  • S_{1}(7,1)=1 deoarece există o singură matrice de o coloană cu combinația 7

Pentru a stabili relația de recurență pentru șirul S_{k}(1,0), ne întrebăm: cărei coloane îi poate urma coloana k de tip 1 astfel încât să nu mai existe surplus ? Dacă observăm că pe coloana k avem un singur element bifat (deci sub medie), rezultă că pe coloana k-1 exista un surplus de un pătrat. Deci coloana k-1 putea fi de tipul 5 sau 7, acestea fiind singurele tipuri de coloană după care poate exista un surplus. Rezultă formula:

S_{k}(1,0)=S_{{k-1}}(5,1)+S_{{k-1}}(7,1)

Printr-o simetrie perfectă se calculează aceeași formulă și pentru șirul S_{k}(4,0):

S_{k}(4,0)=S_{{k-1}}(5,1)+S_{{k-1}}(7,1)

La șirul S_k(2,0), mai trebuie făcută observația că o coloană de tip 2 nu poate urma unei coloane de tip 5, deoarece se strică conexitatea figurii. Rezultă:

S_{k}(2,0)=S_{{k-1}}(7,1)

Șirul S_{k}(5,0) provine din adăugarea unei coloane de tipul 5 după o coloană de tipul 1, 4 sau 5. Coloana k-1 nu poate fi de tipul 2 deoarece figura rezultată nu este conexă, nici de tipul 7 deoarece ar rezulta că în primele k-2 coloane media de celule bifate este mai mică decât 2.

S_{k}(5,0)=S_{{k-1}}(1,0)+S_{{k-1}}(4,0)+S_{{k-1}}(5,0)

Șirul S_{k}(5,1) provine din adăugarea unei coloane de tipul 5 după o coloană de tipul 5 sau 7, deoarece tipul de coloană 5 are două pătrate bifate, deci conservă surplusul:

S_{k}(5,1)=S_{{k-1}}(5,1)+S_{{k-1}}(7,1)

În sfârșit, o coloană de tip 7 poate urma oricărui tip de coloană pentru care surplusul este 0, adică:

S_{k}(7,1)=S_{{k-1}}(1,0)+S_{{k-1}}(2,0)+S_{{k-1}}(4,0)+S_{{k-1}}(5,0)

Acestea sunt formulele de recurență. Rezultatul care trebuie afișat pe ecran este 2[S_{{N-1}}(5,1)+S_{{N-1}}(7,1)], deoarece după N-1 coloane surplusul trebuie să fie 1, iar colțurile matricii trebuie să fie bifate. Se observă că S_{k}(1,0)=S_{k}(4,0)=S_{k}(5,1). Practic, problema se reduce la trei șiruri. Notăm:

{\begin{aligned}A_{k}&=S_{k}(5,0)\\B_{k}&=S_{k}(1,0)=S_{k}(4,0)=S_{k}(5,1)\\C_{k}&=S_{k}(7,1)\implies S_{k}(2,0)=C_{{k-1}}\end{aligned}}

De aici rezultă grupul de relații:

{\begin{cases}A_{k}&=A_{{k-1}}+2B_{{k-1}}\\B_{k}&=B_{{k-1}}+C_{{k-1}}\\C_{k}&=A_{{k-1}}+2B_{{k-1}}+C_{{k-2}}=A_{k}+C_{{k-2}}\end{cases}}

și

{\begin{cases}A_{1}&=1\\B_{1}&=0\\C_{1}&=1\end{cases}}

Noi avem nevoie de valoarea

2(B_{{N-1}}+C_{{N-1}})=2B_{N}

Programul de mai jos nu face decât să implementeze calculul acestor șiruri recurente. Trebuie avut grijă însă cu reprezentarea internă a numerelor, deoarece pentru N=200 valorile ajung la 81 de cifre. Este deci necesară reprezentarea numerelor ca șiruri de cifre.

#include <stdio.h>
#include <mem.h>

typedef int Huge[85];
Huge A,B,C,C2,HTemp;
int N,k;

void Atrib(Huge H, int V)
/* H <- V */
{
  memset(H,0,sizeof(Huge));
  H[0]=1;
  H[1]=V;
}

void Add(Huge A, Huge B)
/* A <- A+B */
{ int i,T=0;

  if (B[0]>A[0])
    { for (i=A[0]+1;i<=B[0];) A[i++]=0;
      A[0]=B[0];
    }
    else for (i=B[0]+1;i<=A[0];) B[i++]=0;
  for (i=1;i<=A[0];i++)
    { A[i]+=B[i]+T;
      T=A[i]/10;
      A[i]%=10;
    }
  if (T) A[++A[0]]=T;
}

void WriteHuge(Huge H)
{ int i;

  for (i=H[0];i;printf("%d",H[i--]));
  printf("\n");
}

void main(void)
{
  printf("N=");scanf("%d",&N);
  Atrib(A,1);
  Atrib(B,0);
  Atrib(C,1);
  Atrib(C2,0);
  for (k=2;k<=N;k++)
    { memmove(HTemp,C,sizeof(Huge));
      Add(A,B);Add(A,B);  /* A(k) = A(k-1) + 2*B(k-1) */
      Add(B,C);           /* B(k) = B(k-1) + C(k-1)   */
      memmove(C,A,sizeof(Huge));
      Add(C,C2);          /* C(k) = A(k) + C(k-2)     */
      memmove(C2,HTemp,sizeof(Huge)); /* noul C(K-2) */
    }
  Add(B,B);               /* Rezultatul este 2*B(n)   */
  WriteHuge(B);
}