dame

Dame

== include(page="template/taskheader" task_id="dame") ==

==Include(page="template/taskheader" task_id="dame")==

Poveste ...

==Include(page="template/raw")==
 
Bronzarel s-a apucat serios de informatica si cu ajutorul lui Zaharel spera sa devina un mare programator. Printre primele problemele pe care le-a rezolva, a fost problema clasica a damelor: dandu-se o tabla de sah $N*N$ sa se determine toate modurile in care se poate amplasa un numar maxim de dame pe tabla astfel incat sa nu se atace intre ele (doua dame se ataca intre ele daca sunt pe aceeasi linie, aceeasi coloana sau aceeasi diagonala). Fiindca rezultatul este calculabil doar pentru valori mici ale lui $N$, Bronzarel a scris repede un program care foloseste "backtracking", metoda lui preferata. Vazandu-l foarte multumit de el, Zaharel ii zice sa faca un program care determina doar o modalitate de amplasare, dar pentru valori mai mari ale lui $N$. Se pare ca aceasta problema il depaseste pe Bronzarel, metoda lui favorita fiind nefolositoare de data aceasta.

h2. Cerinta

...

Scrieti un program in locul lui Bronzarel care sa determine un mod in care se pot amplasa un numar maxim de dame pe o tabla de sah $N*N$.

h2. Restrictii

h2. Date de Intrare

...

Prima linie din fisierul de intrare $dame.out$ va contine numarul natural $N$.

h2. Date de intrare

h2. Date de Iesire

...

Pe prima linie din fisierul de iesire $dame.out$ se va scrie numarul $Max$, reprezentand numarul maxim de dame care se pot amplasa pe tabla. Urmatoarele $Max$ linii vor contine perechi de numere naturale reprezentand linia si coloana pe care se va afla o dama.

h2. Date de iesire

h2. Restrictii si observatii

...

* $1 ≤ N ≤ 1.000$
* Liniile si coloanele tablei sunt numerotate de la 1 la &N&
* Pentru $30%$ din teste $N ≤ 25$ iar pentru $60%$ din teste $N ≤ 200$

h2. Exemplu

| dame.in | dame.out |
| linia1
linia2
linia3
| linia1
linia2
|

table(example). |_. dame.in |_. dame.out |_. Explicatie |
|8 |8
 1 4
 2 7
 3 3
 4 8
 5 2
 6 5
 7 1
 8 6 | !task/dame?! |

== include(page="template/taskfooter" task_id="dame") ==
 

==Include(page="template/taskfooter" task_id="dame")==