În urma bombardamentelor din 11 septembrie 2001, clădirea Pentagonului a suferit daune la unul din pereții clădirii. Imaginea codificată a peretelui avariat se reprezintă sub forma unei matrice cu m linii și n coloane, ca în figura de mai jos:

1110000111
1100001111
1000000011
1111101111
1110000111

unde 1 reprezintă zid intact, iar 0 zid avariat. Sumele alocate pentru refacerea Pentagonului vor fi donate celor care vor ajuta americanii să refacă această clădire prin plasarea, pe verticală, a unor blocuri de înălțimi k, k=1, …, m, și lățime 1, în locurile avariate.

Cerința

Pentru o structură dată a unui perete din clădirea Pentagonului, determinaţi numărul minim al blocurilor, de înălţimi k=1, k=2, …, k=m, necesare refacerii clădirii.

Date de intrare

Fișierul de intrare pentagon.in conține pe prima linie dimensiunile m şi n ale peretelui clădirii, iar pe următoarele m linii câte o secvență de caractere 1 sau 0 de lungime n.

Date de ieșire

Fișierul de ieșire pentagon.out va conține pe câte o linie, ordonate crescător după k, perechi de forma k nr, unde k este înălțimea blocului, iar nr este numărul de blocuri de înălțime k, separate prin câte un spaţiu.

Restricții și precizări

1 ≤ m, n ≤ 200
nu se vor afișa blocurile de înălțime k, a căror număr este zero (0).

Exemplu

pentagon.in

pentagon.out

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema pentagon:

type corp=array[1..200] of string[200];
var c:corp;
    f:text;
    s:array[1..200] of integer;
    m,n,i:integer;

Procedure numara;
var i,j:integer;
    cod:boolean;
    nr:integer;
begin
     for j:=1 to n do
         begin
         nr:=0;
         cod:=c[1,j]='1';
         for i:=1 to m do
             if c[i,j]='1' then
                begin
                if not cod then
                       begin
                       cod:=true;
                       inc(s[nr]);
                       nr:=0;
                       end
                end
                else
                begin
                  if cod then
                         begin
                         nr:=1;
                         cod:=false;
                         end
                         else
                      inc(nr);
                end;
         if not cod then
                       begin
                       cod:=true;
                       inc(s[nr]);
                       end
         end;
end;
begin
assign(f,'pentagon.in');
reset(f);
readln(f,m,n);
for i:=1 to m do
    readln(f,c[i]);
close(f);
numara;
assign(f,'pentagon.out');
rewrite(f);
for i:=1 to m do
    if s[i]<>0 then
       writeln(f,i,' ',s[i]);
close(f);
end.

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #2607 pentagon

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2607 pentagon de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #2607 pentagon