Fişierul intrare/ieşire:dame.in, dame.outSursăpreONI 2006 Runda 2
AutorMircea Bogdan PasoiAdăugată de
Timp execuţie pe test0.05 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

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.

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.

Date de Intrare

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

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.

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

Exemplu

dame.indame.out
88
1 4
2 7
3 3
4 8
5 2
6 5
7 1
8 6

Explicatii

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content