Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | dame2.in, dame2.out | Sursă | Summer Challenge 2007, runda 3 |
| Autor | Cosmin Silvestru Negruseri | Adăugată de |  Adrian Diaconu •DITzoneC |
| Timp execuţie pe test | 0.1 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Dame 2
Avem o tabla de sah (8 X 8) din care au fost distruse unele patratele. Pe patratele care nu sunt distruse trebuie plasat un numar minim de dame astfel incat fiecare patratel care nu e distrus sa fie atacat si oricare doua dame nu trebuie sa se atace intre ele. O dama ataca o patratica daca se afla pe aceeasi linie, coloana sau diagonala (chiar daca intre ele exista patratele distruse).
Cerinta
Calculati numarul minim de dame necesar si gasiti o pozitionare a acestora minim lexicografica.
Date de intrare
Fisierul de intrare dame2.in va contine 8 linii cu cate 8 caractere. Caracterul i de pe linia j va fi 0 in cazul in care patratica nu a fost distrusa si va fi 1 in caz contrar.
Date de iesire
Pe prima linie a fisierului de intrare dame2.out se va afisa X numarul minim de dame necesar. Urmatoarea linie va contine X perechi de numere a b semnificand ca trebuie pozitionata o dama pe linia a si coloana b.
Restrictii
- O pozitionare a1 b1 a2 b2 ... aX bX este mai mica lexicografic decat c1 d1 c2 d2 ... cX dX daca stringul obtinut prin concatenare este mai mic lexicografic.
h2. Exemplu
| dame2.in | dame2.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicatie
...
