Fişierul intrare/ieşire:union.in, union.outSursăACM-ICPC Faza Nationala 2017
AutorMihai CalanceaAdăugată deklamathixMihai Calancea klamathix
Timp execuţie pe test3 secLimită de memorie131072 kbytes
Scorul tăuN/ADificultateN/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 un fals. 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.

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 ≤ 21
  • 1 ≤ N, M ≤ 20
  • 1 ≤ K ≤ 6
  • Cel putin 13 teste au K ≤ 5

Exemplu

union.inunion.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
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content