Fişierul intrare/ieşire: | regine.in, regine.out | Sursă | Lot 2005 |
Autor | Marius Andrei | Adăugată de | |
Timp execuţie pe test | 0.075 sec | Limită de memorie | 65536 kbytes |
Scorul tău | N/A | Dificultate |
Vezi solutiile trimise | Statistici
Regine
Pe o tabla triunghiulara de latura N, trebuiesc asezate cat mai multe regine, astfel incat acestea sa nu se atace.
O tabla triunghiulara, de latura N, are N linii. Pe linia i sunt i locuri in care reginele pot sta, iar locurile sunt asezate sub forma de triunghi, ca in figura de mai jos. Fiind vorba de o tabla mai speciala si reginele sunt speciale, in sensul ca ele se pot deplasa (ataca) in 6 directii.
In figura de mai sus este reprezentata o tabla de latura 6, cu o regina pe linia 5, coloana 4. Numerotarea liniilor si coloanelor incepe de la 1 (din varful tablei in jos - pentru linii si de la stanga la dreapta pentru coloane).
Cerinta
Determinati numarul maxim de regine ce pot fi asezate pe o tabla de dimensiune N si o asezare posibila a lor (oricare dintre solutiile cu numar maxim).
Date de intrare
Pe prima linie a fisierului se afla un numar natural N, reprezentand dimensiunea tablei.
Date de iesire
Fisierul va contine pe prima linie un singur numar intreg, X, reprezentand numarul maxim de regine ce pot fi asezate. Pe urmatoarele X linii se vor scrie cate 2 numere separate de un singur spatiu, reprezentand linia si respectiv coloana reginelor.
Restrictii
- 1 < N < 1 001
- daca un test are numarul corect de regine, dar configuratia reginelor nu este valida, se acorda 30% din punctajul testului.
Exemplu
regine.in | regine.out |
---|---|
3 | 2 2 1 3 3 |
Explicatii
Putem aseza maxim 2 regine: una pe linia 2, coloana 1 si una pe linia 3, coloana 3.