In primul rand, numarul maxim de dame este $N$ pentru $N = 1$ si {$N ≥ 4$}, si $N-1$ pentru {$N = 2, 3$}. Putem codifica solutia ca o permutare de la $1$ la {$N$}, astfel asigurand ca nu exista doua dame pe aceeasi linie sau coloana. O solutie clasica care foloseste metoda backtracking si face verificarea daca o dama este atacata sau nu in $O(1)$ va obtine $30$ de puncte.
Verificarea in $O(1)$ se face pastrand doi vectori pentru fiecare diagonala in functie de orientare, in care se marcheaza daca o diagonala este ocupata. O "imbunatatire" la backtracking este randomizarea ordinii in care se incearca completarea solutiei la fiecare pas. O astfel
de solutie merge usor si pentru $N = 200$ si ar fi obtinut cel putin $60$ de puncte.

Exista mai multe metode prin care s-ar fi putut obtine $100$ de puncte. O solutie greedy este urmatoarea: se incepe cu o solutie oarecare si cat timp exista doua dame care, daca s-ar interschimba coloanele lor, se imbunatateste solutia, se aplica interschibarea. Daca

Exista mai multe metode prin care s-ar fi putut obtine $100$ de puncte. O solutie greedy este urmatoarea: se incepe cu o solutie oarecare si cat timp exista doua dame care, daca s-ar interschimba coloanele lor, se imbunatateste solutia, se aplica interschimbarea. Daca

nu s-a obtinut o solutie buna, se reinitializeaza solutia initiala si se reaplica algoritmul. In practica, complexitatea algoritmului tinde la {$O(N log N)$}, desi teoretic este {$O(N^3^)$}. De asemenea pe masura ce $N$ este mai mare, numarul necesar de reinitializari ale algoritmului tinde catre {$0$}. Mai multe detalii gasiti "aici":http://www.cit.gu.edu.au/~sosic/nqueens.html
O alta solutie , matematica, se bazeaza pe un sablon de construire a solutiei in functie de restul lui $N$ la {$12$}.

Daca se deplaseaza inspre $N$ sau {$S$}, cautarea se va face in {$vx$}, altel, in {$vy$}. Diferenta dintre cele doua valori returnate de cautarile binare furnizeaza numarul de celule afectate prin care Chidil trece la acea mutare.

Pentru un timp de executie bun, se recomanda folosirea functiei $sort()$ din STL pentru sortare si a containerului $pair<int, int>$ pentru pastrarea coordonatelor in cei doi vectori.

Pentru un timp de executie bun, se recomanda folosirea functiei $sort()$ din STL pentru sortare si a containerului @pair<int, int>@ pentru pastrarea coordonatelor in cei doi vectori.

h2. Grupuri

* $A{~i~} = A{~i-1~} + A{~i-3~} + 2$
* $B{~i~} = B{~i-1~} + A{~i-2~}$

Mai facem urmatoarea observatie: {$A{~i~} - B{~i-1~} = (A{~i-1~} + A{~i-3~} + 2) - (B{~i-2~} + A{~i-3~}) = A{~i-1~} - B{~i-2~} + 2$}, ceea ce inseamna ca {$A{~i~} - B{~i-1~} = 2 * (i - 1)$} (demonstratie prin inductie, tinand cont de faptul ca {$A{~2~} + B{~1~} = 2$}).

Mai facem urmatoarea observatie: {$A{~i~} - B{~i-1~} = (A{~i-1~} + A{~i-3~} + 2) - (B{~i-2~} + A{~i-3~}) = A{~i-1~} - B{~i-2~} + 2$}, ceea ce inseamna ca {$A{~i~} - B{~i-1~} = 2 * (i - 1)$} (demonstratie prin inductie, tinand cont de faptul ca {$A{~2~} - B{~1~} = 2$}).

In sfarsit, sa calculam sirul {$T{~i~} = A{~i~} + B{~i~}$}.
{$T{~i~} = A{~i~} + B{~i~} = A{~i-1~} + A{~i-3~} + 2 + B{~i-1~} + A{~i-2~} = (A{~i-1~} + A{~i-3~}) + (B{~i-1~} + B{~i-3~}) + (A{~i-2~} - B{~i-3~}) + 2 = T{~i-1~} + T{~i-3~} + (A{~i-2~} - B{~i-3~}) + 2$}. Dupa cum am observat mai devreme $A{~i-2~} - B{~i-3~} = 2 * (i - 3)$ => {$T{~i~} = T{~i-1~} + T{~i-3~} + 2 * (i - 2)$}, ceea ce ne propusesem sa demonstram.

Pentru a afla si minimul pe portiuni se procedeaza similar.

In plus, pentru o oferta vom procesa atat perechea ({$DX, DY$}), cat si ({$DY, DX$}), daca si numai
daca {$DX$} diferit de {$DY$}. Altfel, vom proceda doar ({$DX, DY$}).
 
 

In plus, pentru o oferta vom procesa atat perechea ({$DX, DY$}), cat si ({$DY, DX$}), daca si numai daca {$DX$} diferit de {$DY$}. Altfel, vom procesa doar ({$DX, DY$}).

h2. Camera