Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | union.in, union.out | Sursă | ACM-ICPC Faza Nationala 2017 |
| Autor | Mihai Calancea | Adăugată de |  Mihai Calancea •klamathix |
| Timp execuţie pe test | 1.5 sec | Limită de memorie | 131072 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Union
Dupa ce ti-ai terminat cariera de olimpic la informatica, ti-ai deschis o fabrica de matrice binare. Ce sa faci, alte aptitudini nu ti-ai dezvoltat.
Din fericire, produsele tale par sa fie de succes. Intr-atat incat au inceput sa apara falsuri despre care se pretinde ca sunt opera ta. Astazi vrei sa verifici daca o astfel de matrice este falsa sau nu. Nu tii minte exact ce matrice ai produs in seria respectiva, dar tii minte ca toate matricele produse erau create incepand cu o matrice plina de zerouri, iar apoi colorand cel mult K submatrice cu valoarea 1. Este posibil ca submatricele selectate pentru colorare sa se suprapuna sau chiar sa fie identice.
Este posibil ca matricea pe care o analizezi sa fi fost produsa dupa algoritmul mentionat?
Date de intrare
Fişierul de intrare union.in contine pe prima sa linie T, numarul de teste din fisier. Structura unui test este urmatoarea: pe prima linie se afla numerele N M K. Urmeaza N linii, fiecare continand un sir de caractere de lungime M. Caracterele sirului sunt din multimea {0, 1}.
Date de ieşire
În fişierul de ieşire union.out se va afla raspunsul pentru fiecare dintre cele T teste. Daca nu este posibil ca matricea curenta sa fie produsa conform regulilor descrise, raspunsul este -1. Altfel, veti descrie o secventa de operatii de colorare care poate obtine matricea data. Pe prima linie a solutiei veti afisa NR, numarul de operatii efectuat. Bineinteles, acesta trebuie sa fie mai mic sau egal cu K. Urmeaza NR linii care contin cate 4 numere x1 y1 ×2 y2, care descriu colturile stanga sus, respectiv colturile dreapta jos ale submatricelor alese. Indicii liniilor trebuie sa fie in intervalul [0, N - 1], iar indicii coloanelor trebuie sa se afle in intervalul [0, M - 1].
Restricţii
- 1 ≤ T ≤ 16
- 1 ≤ N ≤ 20
- 1 ≤ K ≤ 6
Exemplu
| union.in | union.out |
|---|---|
| 3 3 3 3 001 000 010 3 3 1 001 000 010 4 4 2 0110 0110 0111 0111 | 2 0 2 0 2 2 1 2 1 -1 2 0 1 3 2 2 1 3 3 |
