Se dă un şir de caractere S format din litere mari şi mici ale alfabetului englez, spaţii şi caracterul ⌂ ce are codul ASCII 127. Fiecare caracter al lui S se codifică printr-o succesiune de 1 şi 0 ce reprezintă codul ASCII al caracterului în baza 2. Codul începe cu cifra 1, astfel pentru caracterul A codificarea este 1000001. Un cuvânt poate fi format din litere şi caracterul ⌂. Se consideră matricea M formată din cuvintele șirului S codificate şi memorate pe câte o linie în ordinea în care se găsesc acestea în propoziție.

Cerința

Scrieţi un program care, cunoscând S şi K, rezolvă următoarele două cerinţe:

Se dă un şir de caractere S format din litere mari şi mici ale alfabetului englez, spaţii şi caracterul ⌂ ce are codul ASCII 127. Fiecare caracter al lui S se codifică printr-o succesiune de 1 şi 0 ce reprezintă codul ASCII al caracterului în baza 2. Codul începe cu cifra 1, astfel pentru caracterul A codificarea este 1000001. Un cuvânt poate fi format din litere şi caracterul ⌂. Se consideră matricea M formată din cuvintele șirului S codificate şi memorate pe câte o linie în ordinea în care se găsesc acestea în propoziție.

Cerința

Scrieţi un program care, cunoscând S şi K, rezolvă următoarele două cerinţe:
1. determină L, latura celui mai mare pătrat din matricea M ce conține doar valori de 1;
2. determină NR, câte pătrate de latura K cu toate elementele egale cu 1 există în matricea M.

Date de intrare

Fișierul de intrare asciimat.in conţine pe prima linie cerinţa care trebuie să fie rezolvată (1 sau 2). Pe a doua linie se află șirul S, iar pe a treia linie se află valoarea K, având semnificaţia din enunţ.

Date de ieșire

Dacă cerinţa este 1, fişierul de ieşire asciimat.out va conţine o singură linie pe care va fi scris L, latura celui mai mare pătrat din matricea M ce conține doar valori de 1.
Dacă cerinţa este 2, fişierul de ieşire asciimat.out va conţine o singură linie pe care va fi scris NR, câte pătrate de latura K cu toate elementele egale cu 1 există în matricea M.

Restricții și precizări

• şirul S are cel mult 3000 de caractere
• 3 ≤ K ≤ 50
• lungimea unui cuvânt nu depăşeşte 100 de caractere
• fiecare cuvânt este codificat pe o singură linie
• fiecare literă este codificată pe 7 biţi
• liniile conţin concatenarea codurilor ASCII ale literelor unui cuvânt, astfel restul valorilor rămase libere din cadrul unei linii vor avea valoarea 0.
• numărul de cuvinte din şir nu depăşeşte valoarea 300.

Exemplul 1:

asciimat.in

1
Ana are mere
3

asciimat.out

3

Exemplul 2:

asciimat.in

2
Ana are mere
2

asciimat.out

7

Explicație

Matricea obţinută este:

1000001110111011000010000000
1100001111001011001010000000
1101101110010111100101100101

La poziția (1,8) în matrice este colţul stânga-sus al unui pătrat de latura 3 cu toate elementele egale cu 1.
Există 7 pătrate de latură 2 cu toate elementele egale cu 1.

#include <bits/stdc++.h>

using namespace std;

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

int cer , k , A[302][702] , n , m , maxi , cnt;
char s[3001];

int main()
{
    cin >> cer;
    cin.get();
    cin.getline(s , 3001);
    cin >> k;

    char *p;
    p = strtok(s , " ");
    while(p != 0)
    {
        n++;
        int c = 0;
        for(int i = 0 ; p[i] ; i++)
        {
            int x[8] = {0} , j = 0;
            int val = p[i];
            while(val)
            {
                x[++j] = val % 2;
                val /= 2;
            }
            for(int j = 7 ; j >= 1 ; j--)
                A[n][++c] = x[j];
        }
        if(c > m) m = c;
        p = strtok(NULL , " ");
    }

    for(int i = 1 ; i <= n ; i++)
        for(int j = 1 ; j <= m ; j++)
            if(A[i][j] == 1)
            {
                A[i][j] += min(A[i - 1][j - 1] , min(A[i - 1][j] , A[i][j - 1]));
                if(A[i][j] > maxi) maxi = A[i][j];
            }
    if(cer == 1) cout << maxi;
    else
    {
        for(int i = 1 ; i <= n ; i++)
        {
            for(int j = 1 ; j <= m ; j++)
                if(A[i][j] >= k) cnt++;
        }
        cout << cnt;
    }

}