| Fişierul intrare/ieşire: | boundingbox.in, boundingbox.out | Sursă | Infoarena Cup 2014 |
| Autor | Mihai Calancea | Adăugată de |  Heidelbacher Andrei •a_h1926 |
| Timp execuţie pe test | 0.35 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Boundingbox
Se dă o matrice binară A cu R linii şi C coloane. Dacă alegem aleator, cu probabilitate uniformă, o submulţime (posibil vidă) de celule numerotate cu 1, ce arie va avea în medie submatricea de arie minimă care conţine toate celulele selectate?
Date de intrare
Fişierul de intrare boundingbox.in va conţine pe prima sa linie numărul de teste T. Fiecare test va respecta următorul format: Prima linie conţine cele două numere, R şi C, iar următoarele R linii conţin câte C caractere, constituind matricea A.
Date de ieşire
În fişierul de ieşire boundingbox.out se vor afla T linii, fiecare conţinând răspunsul pentru testul corespunzător. Răspunsul va respecta formatul "X/Y", unde X şi Y sunt numere naturale prime între ele. Cu alte cuvinte, răspunsul trebuie să ia forma unei fracţii ireductibile.
Restricţii
- 1 ≤ T ≤ 1000
- 1 ≤ R * C ≤ 50
- Pentru 20% din teste, numărul celulelor de tip 1 din fiecare matrice este cel mult 12
- Pentru alte 40% din teste are loc relaţia T ≤ 100
Exemplu
| boundingbox.in | boundingbox.out |
|---|---|
| 2 2 3 101 010 1 1 0 | 5/2 0/1 |
