Fişierul intrare/ieşire:identice.in, identice.outSursăONI 2017, clasa a 10-a
AutorGheorghe ManolacheAdăugată debciobanuBogdan Ciobanu bciobanu
Timp execuţie pe test0.05 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultateN/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.inidentice.outExplicaţ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.
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?