Fișierul intrare/ieșire | identice.in, identice.out | Sursă | ONI 2017, clasa a 10-a |
---|---|---|---|
Autor | Gheorghe Manolache | Adăugată de | Tinca Matei • TincaMatei |
Timp de execuție pe test | 0.2 sec | Limită de memorie | 32768 KB |
Scorul tău | N/A | Dificultate | N/A |
Vezi soluțiile trimise | Statistici
Identice (clasa a 10-a)
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. |