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.
Exemplu
| dame2.in | dame2.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicatie
...
