(Categoria _Competitii_, autor(i) _Adrian Diaconu si Cosmin Negruseri_)

h2. Sah

h2. "Sah":problema/sah

Prima observatie ar fi ca pentru a ne asigura ca intr-o regiune numarul de casute albe este egal cu numarul de celule negre este suficient ca aria regiunii sa fie para.

Plecand de la aceasta observatie si de la faptul ca $N$ este mereu par propunem urmatoarea impartirea tablei si voi demonstra apoi ca indeplineste conditiile din enunt. Impartim tabla in benzi de latime $2$ (pentru a asigura paritatea ariilor). Apoi prima banda o lasam intreaga, iar pentru urmatoarele banda $i$ se va inmparti in $i-1$ si {$N-i+1$}. Astfel se vor creea $N-1$ regiuni. Se observa ca toate dreptunghiurile difera intre ele prin lungime deoarece se folosesc toate numerele de la $1$ la $N$ mai putin {$N/2$}.

Plecand de la aceasta observatie si de la faptul ca $N$ este mereu par propunem urmatoarea impartire a tablei si voi demonstra apoi ca indeplineste conditiile din enunt. Impartim tabla in benzi de latime $2$ (pentru a asigura paritatea ariilor). Apoi prima banda o lasam intreaga, iar pentru urmatoarele banda $i$ se va imparti in $i-1$ si {$N-i+1$}. Astfel se vor creea $N-1$ regiuni. Se observa ca toate dreptunghiurile difera intre ele prin lungime deoarece se folosesc toate numerele de la $1$ la $N$ mai putin {$N/2$}.

Pentru a demonstra ca $N-1$ este numarul maxim de regiuni care se poate creea vom presupune ca se poate imparti tabla in $N$ regiuni. Vom considera ca se folosesc cele mai mici arii posibile, dar acestea trebuie sa fie toate pare. Suma ariilor va fi $2+4+6+..+2*N= 2*(N*(N+1)/2)=N*N+N$ ceea ce ar depasi tabla noastra.

h2. Plimbare

h2. "Plimbare":problema/plimbare

Evident ca o conditie necesara ca un graf turneu (asa se numesc grafurile ca cel mentionat in enunt in care exista exact un arc intre oricare doua noduri) sa aiba un circuit hamiltonean ar fi ca graful sa fie tare conex, daca nu ar fi tare conex atunci evident nu poate exista un circuit intre doua noduri aflate in doua componente tari conexe diferite. Aceasta conditie este si suficienta asa cum va reiesi din algoritmul pe care il vom explica mai jos.

Daca folosim metoda de determinare a componentelor tari conexe folosind un algoritm eficient de complexitate {$O(N + M)$}, atunci algoritmul are complexitatea $O(N^2^)$ pentru ca la fiecare inserare facem $O(n)$ pasi. Un algoritm mai eficient nu putem obtine deoarece {$M = N(N-1)/2$}, deci si citirea datelor e {$O(N^2^)$}. $N$ a fost fixat la $100$ pentru ca am vrut sa punem accent asupra ideii de gasire a circuitului si nu asupra algoritmului de determinare eficienta a componentelor tari conexe.

h2. TreiD

h2. "TreiD":problema/TreiD

Aceasta problema e similara cu problema "Bmatrix":http://infoarena.devnet.ro/index.php?page=read&conid=arhiva&tid=bmatrix din arhiva si a fost propusa pentru a favoriza utilizatorii inraiti :).

Aceasta problema e similara cu problema "Bmatrix":problema/bmatrix din arhiva si a fost propusa pentru a favoriza utilizatorii inraiti :).

Trei dreptunghiuri pot avea ca amplasare relativa doar 6 pozitii diferite:
${@+@}------{@+@}    {@+@}------{@+@}    {@+@}------{@+@}$
${@|@}      {@|@}    {@|@}      {@|@}    {@|@}  {@|@}   {@|@}$