Cerința

Considerăm codificarea binară a caracterelor, în care fiecărui simbol îi revine reprezentarea pe 8 biți a codului său ASCII. De exemplu, caracterului ’A’, având codul ASCII 65, îi va corespunde reprezentarea binară 01000001.

Scrieți un program care citește din fișierul convert_submatrix.in un șir s format din n ≤ 100 caractere și construiește o matrice M cu n linii și 8 coloane, linia i a matricii reprezentând codificarea binară a caracterului de pe poziția i din șir. Se cere determinarea dimensiunii celei mai mari submatrice pătratice a lui M, care conține elemente cu aceeași valoare (fie 0, fie 1). Valoarea determinată se scrie în fișierul convert_submatrix.out.

Date de intrare

Fișierul de intrare convert_submatrix.in conține pe prima linie șirul s format din cel mult 100 de caractere.

Date de ieșire

Fișierul de ieșire convert_submatrix.out va conține pe prima linie numărul rez, reprezentând dimensiunea celei mai mari submatrici pătratice a lui m conținând elemente cu aceeași valoare (fie 0, fie 1).

Restricții și precizări

• lungimea șirului: 1 ≤ n ≤ 100
• șirul poate să conțină: ABCDEFGHIJKLMNOPQRSTUVXYZabcdefghijklmnopqrstuvxyz0123456789 `~,./;:][}{+_=-|!#$%^&*()

Exemplul 1:

convert_submatrix.in

IDEEA

convert_submatrix.out

3

Explicație

Matricea corespunzătoare șirului citit este:

$$\begin{pmatrix} 0&1&0&0&1&0&0&1\\ 0&1&0&0&0&1&0&0\\ 0&1&0&0&0&1&0&1\\ 0&1&0&0&0&1&0&1\\ 0&1&0&0&0&0&0&1 \end{pmatrix}$$

Se observă că dimensiunea celei mai mari submatrici pătratice a lui m conținând elemente cu aceeași valoare este 3.

Exemplul 2:

convert_submatrix.in

AAAyyyy

convert_submatrix.out

4

Explicație

Matricea corespunzătoare șirului citit este:

$$\begin{pmatrix} 0&1&0&0&0&0&0&1\\ 0&1&0&0&0&0&0&1\\ 0&1&0&0&0&0&0&1\\ 0&1&1&1&1&0&0&1\\ 0&1&1&1&1&0&0&1\\ 0&1&1&1&1&0&0&1\\ 0&1&1&1&1&0&0&1\\ \end{pmatrix}$$

Se observă că dimensiunea celei mai mari submatrici pătratice a lui m conținând elemente cu aceeași valoare este 4.

#include <bits/stdc++.h>

using namespace std;

ifstream cin("convert_submatrix.in");
ofstream cout("convert_submatrix.out");

char s[101];
int m[101][10], maxi = 1;

bool inmat(int i, int j){
    return i < strlen(s) && j <= 8;
}

int ok(int i1, int j1, int i2, int j2){
    int cnt = 0;
    if(i2-i1 == j2-j1 && inmat(i2,j2)){
        for(int i = i1; i <= i2; ++i)
            for(int j = j1; j <= j2; ++j)
                cnt+=m[i][j];
        if(cnt == 0 || cnt == (i2-i1+1)*(j2-j1+1))
            return i2-i1+1;
    }
    return -1;
}

int main(){
    cin.getline(s, 101);
    int i = 0;
    while(s[i]){
        int x = s[i];
        int j = 8;
        while(x){
            m[i][j--] = x % 2;
            x/=2;
        }
        i++;
    }
    for(int i = 0; i < strlen(s); ++i)
        for(int j = 1; j <= 8; ++j)
            for(int t = 0; t <= 7; ++t)
                    maxi = max(ok(i,j,i+t,j+t), maxi);
    cout << maxi;
    return 0;
}