Fişierul intrare/ieşire:boundingbox.in, boundingbox.outSursăInfoarena Cup 2014
AutorMihai CalanceaAdăugată dea_h1926Heidelbacher Andrei a_h1926
Timp execuţie pe test0.7 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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.inboundingbox.out
2
2 3
101
010
1 1
0
5/2
0/1
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content