| Fişierul intrare/ieşire: | identice.in, identice.out | Sursă | ONI 2017, clasa a 10-a |
| Autor | Gheorghe Manolache | Adăugată de |  Bogdan Ciobanu •bciobanu |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 36864 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Identice
Mihai a construit o matrice pătratică A de dimensiune N cu valori în mulţimea {0,1}. El preferă acele matrice care au toate elementele identice şi de aceea a calculat pentru matricea A, numărul K de submatrice care au toate elementele identice. Acum, Mihai vrea să transforme matricea A într-o matrice cu toate elementele identice. Pentru aceasta, el a selectat un număr natural nenul D, şi defineşte operaţia ZET care constă în alegerea unei submatrice pătratice de dimensiunea D din matricea precedentă în care schimbă toate elementele 0 în 1 şi invers. El vrea să aplice operaţia ZET iniţial pentru matricea A, apoi repetă operaţia pentru matricea obţinută la momentul anterior, de un număr minim de ori, notat R, până când matricea obţinută are toate elementele identice, sau dacă nu este posibil, R va avea valoarea -1.
Cerinţă
Mihai vă roagă să calculaţi valorile K şi R. Pentru a preciza tipul cerinţei, Mihai foloseşte un cod T care dacă are valoarea 1, atunci solicită calcularea valorii K, iar dacă T are valoarea 2, atunci solicită calcularea valorii R.
Date de intrare
Pe prima linie a fişierului identice.in se vor afla numerele naturale T, N şi D, cu semnificaţia de mai sus, separate prin câte un spaţiu. Pe următoarele N linii se vor afla câte N valori de 0 şi 1, elementele liniilor matricei A, fără spaţii între ele.
Date de ieşire
Pe prima linie a fişierului identice.out se va afla un număr natural, respectiv valoarea K pentru T = 1 sau valoarea R pentru T = 2.
Restricţii
- 1 < D < N ≤ 1000
- Pentru calcularea valorii K, submatricele pot fi pătratice sau dreptunghiulare, cu diferite dimensiuni (inclusiv 1), cu elementele identice.
- Se acordă 40% din punctaj pentru determinarea corectă a lui K iar pentru determinarea corectă a lui R se acordă 60% din punctajul total.
Exemplu
| identice.in | identice.out | Explicaţie |
|---|---|---|
| 1 4 2 0011 0011 1100 1100 | 36 | T = 1, deci se calculează K = 36 Sunt 18 submatrice cu toate elementele 0 şi 18 cu toate elementele 1. |
| 2 4 2 0011 0011 1100 1100 | 2 | T = 2, deci se calculează R = 2, deoarece sunt necesare 2 aplicări ale operaţiei ZET. |
