Dame

dame

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

== include(page="template/taskheader" task_id="dame") ==
 
Poveste ...
 
h2. Cerinta
 
...
 
h2. Restrictii
 
...
 
h2. Date de intrare
 
...
 
h2. Date de iesire
 
...
 
h2. Exemplu
 
| dame.in | dame.out |
| linia1
linia2
linia3
| linia1
linia2
|
 
== include(page="template/taskfooter" task_id="dame") ==

==Include(page="template/raw")==
 
Dame
 
 
 
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. Date de Intrare
 
Prima linie din fisierul de intrare dame.out va contine numarul natural N.
 
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. Restrictii si observatii
 
S 1 <= N <= 1.000
 
S Liniile si coloanele tablei sunt numerotate de la 1 la N
 
S Pentru 30% din teste N <= 25 iar pentru 60% din teste N <= 200
 
h2. Exemplu
 
 
|dame.in |dame.out |Explicatie |
 
|8 |8 | |
| | | |
| |1 4 | |
| | | |
| |2 7 | |
| | | |
| |3 3 | |
| | | |
| |4 8 | |
| | | |
| |5 2 | |
| | | |
| |6 5 | |
| | | |
| |7 1 | |
| | | |
| |8 6 | |
 
==Include(page="template/taskfooter" task_id="dame")==