Rezolvare PBinfo #3376

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.