Pe o tablă triunghiulară de latură N, trebuiesc aşezate cât mai multe regine, astfel încât acestea să nu se atace.
O tablă triunghiulară, de latură N, are N linii. Pe linia i sunt i locuri în care reginele pot sta, iar locurile sunt aşezate sub formă de triunghi, ca în figura de mai jos. Fiind vorba de o tablă mai specială şi reginele sunt speciale, în sensul că ele se pot deplasa (ataca) în 6 direcţii.
În figura de mai jos este reprezentată o tablă de latură 6, cu o regină pe linia 5, coloana 4. Numerotarea liniilor şi coloanelor începe de la 1 (din vârful tablei în jos – pentru linii şi de la stânga la dreapta pentru coloane).
Cerinţă
Determinaţi numărul maxim de regine ce pot fi aşezate pe o tablă de dimensiune N şi o aşezare posibilă a lor (oricare dintre soluţiile cu număr maxim).
Date de intrare
Pe prima linie a fişierului regine.in se află un număr natural N, reprezentând dimensiunea tablei.
Date de ieşire
Fişierul regine.out va conţine pe prima linie un singur număr întreg X, reprezentând numărul maxim de regine ce pot fi aşezate. Pe următoarele X linii se vor scrie câte 2 numere separate de un singur spaţiu, reprezentând linia şi respectiv coloana reginelor.
Restricţii
• 1 < N < 1 001
• dacă un test are numărul corect de regine, dar configuraţia reginelor nu este validă, se acorda 30% din punctajul testului.
Exemple
regine.in
regine.out
Explicaţii
3
2
2 1
3 3
Putem aşeza maxim 2 regine, pe linia 2, coloana 1 şi pe linia 3, coloana 3.
