Se dă o matrice binară pătratică de dimensiuni cu elemente din mulțimea . Începi din celula — colțul stânga-sus — cu un șir , inițial gol, și vrei să ajungi în celula — colțul dreapta-jos. La fiecare mutare te poți deplasa în jos sau la dreapta cu o celulă. Pentru fiecare celulă prin care treci (inclusiv prima și ultima) adaugi valoarea din celula respectivă la capătul din dreapta al șirului .
Cerință
Determinați dacă este posibil ca șirul astfel obținut să fie palindrom. Dacă da, determinați o succesiune de mutări în jos și/sau la dreapta care duce din celula în celula pentru care șirul obținut este palindrom. Pentru această succesiune, determinați în ordine celulele parcurse.
Pentru că ne place de voi, am decis să vă anunțăm că matricea a fost generată aleator.
Date de intrare
Pe prima linie se află un singur număr întreg , reprezentând latura matricii.
Următoarele linii conțin câte caractere din mulțimea , neseparate prin spații, reprezentând descrierea matricii.
Se garantează că matricea este aleasă uniform aleator dintre toate matricile binare de dimensiuni .
Date de ieșire
Afișați NO
dacă nu se poate ca să fie palindrom. Altfel, afișați YES
pe prima linie, apoi, pe fiecare dintre următoarele linii, afișați două valori, și — coordonatele celei de-a -a celule parcurse.
Restricții și precizări
- pentru
# | Punctaj | Restricții |
---|---|---|
1 | 5 | |
2 | 9 | |
3 | 19 | |
4 | 27 | |
5 | 40 | Fără restricții suplimentare. |
Exemplul 1
stdin
2
01
00
stdout
YES
0 0
0 1
1 1
Explicație
Obținem șirul 010
, care este palindrom.
Exemplul 2
stdin
4
0100
1010
0100
0001
stdout
NO
Explicație
Nu se poate obține un șir palindrom.
Exemplul 3
stdin
4
0010
1001
1010
0010
stdout
YES
0 0
0 1
0 2
0 3
1 3
2 3
3 3
Explicație
Obținem șirul 0010100
, care este palindrom.