Rezolvare completă PbInfo #2505 jocxzero

Pe o foaie dintr-un caiet de matematică de dimensiune N x M (N numărul de linii și M numărul de coloane) sunt completate toate pătrățelele cu X sau 0. Pentru un număr natural K dat, numim șir corect, o secvență de K elemente consecutive pe linie, coloană sau diagonale care au aceeași valoare (X sau 0). Două pătrățele de pe foaie sunt vecine pe aceeași diagonală dacă au un singur colț comun.

Exemplu din figura alăturată, pentru care N=4, M=5, K=3 conține 6 șiruri corecte de X și 5 șiruri corecte de 0.

Cerința

  1. Se dau numerele naturale N, M și K și o foaie de matematică plină cu X și 0. Determinați câte șiruri corecte de X și câte șiruri corecte de 0 se găsesc pe foaia dată.
  2. Se dau Q întrebări de forma A B, în care A este caracterul X sau 0 și B este un număr natural. Determinați în câte moduri putem tăia foaia de matematica vertical pentru a obține în subtabloul din partea stângă exact B șiruri corecte de A. Foia se poate tăia în M -1 variante: după prima coloană, a doua coloană, după a treia coloană, ș.a.m.d, până după penultima coloană.

Date de intrare

Fișierul de intrare jocxzero.in conține pe prima linie un număr natural P reprezentând cerința din problemă care trebuie rezolvată.

  • Dacă P = 1 atunci pe a doua linie se găsesc în ordine numerele naturale N, M și K, separate prin câte un spațiu, apoi pe următoarele N linii câte M caractere de X sau 0 reprezentând foaia dată.
  • Dacă P = 2 atunci pe a doua linie se găsesc în ordine numerele naturale N, M și K, separate prin câte un spațiu, apoi pe următoarele N linii câte M caractere de X sau 0 reprezentând foaia dată.

Pe linia N + 3 se găsește numărul natural Q . Pe următoarele Q linii se găsesc câte un caracter A și un număr natural B despărțite prin un spațiu.

Date de ieșire

  • Dacă P = 1 atunci fișierul de ieșire jocxzero.in conține pe o singură linie două numere naturale separate printr-un spațiu, reprezentând, în ordine, numărul de șiruri corecte de X și numărul de șiruri corecte de 0.
  • Dacă P = 2 atunci fișierul de ieșire jocxzero.out conține pe Q linii, câte un număr natural
    reprezentând răspunsul la întrebarea corespunzătoare din fișierul de intrare.

Restricții și precizări

  • 1 ≤ N ≤ 100
  • 2 ≤ M ≤ 10 000
  • 1 ≤ K ≤ 100
  • 1 ≤ Q ≤ 100 000
  • 0 ≤ B ≤ 1 000 000 000
  • În fișierele de intrare caracterul X este majusculă iar 0 este caracterul cifra zero.
  • Pentru rezolvarea corectă a cerinței 1) se acordă 40 puncte, pentru rezolvarea corectă a cerinței 2) se
    acordă 60 de puncte

Exemplu 1:

jocxzero.in

1
4 5 3
XXXX0
0XXX0
00X00
000XX

jocxzero.out

6 5

Explicație

Pe prima linie sunt 2 șiruri corecte de X, pe a doua un șir corect de X, pe diagonală avem 2 șiruri corecte de X și unul pe verticală.

Pe ultima linie avem un șir corect de 0, pe prima coloana avem un șir corect de 0, pe ultima coloană avem un șir corect de 0, pe diagonală mai avem 2 șiruri corecte de 0.

Exemplu 2:

jocxzero.in

2
4 5 3
XXXX0
0XXX0
00X00
000X0
2
0 1
X 1

jocxzero.out

2
0

Explicație

Putem tăia vertical după prima coloană, după a doua, după a treia și după a patra coloană. Dacă tăiem după prima și a doua obținem un singur șir corect de 0.

Indiferent pe unde tăiem nu putem avea un subtablou cu un singur șir corect de X.

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 jocxzero:

var  f,g:text;  c:char;
aa:array[0..102,0..10002]of byte;
sus,st,sts,stj:array[0..102,0..10002] of longint;
bb:array[0..4] of longint; sir:array[0..2,0..10002]of longint;
d:array[0..2]of longint;
i,j,n,m,k,q,a,b,p,x,max1,p1,p2:longint;
function cbinarp(a,b,u:longint):longint;
var i,j,k,ok:longint;
begin

    cbinarp:=-1; ok:=0;
    if (b<sir[a,1])and(ok=0) then begin cbinarp:=-1;ok:=1 end;
    if (b>sir[a,u])and(ok=0) then begin cbinarp:=-1;ok:=1 end;
    if (b=sir[a,1])and(ok=0) then begin cbinarp:=1;ok:=1 end;
    i:=1;j:=u;
    while (i<=j) and (ok=0) do
          begin
          k:=(i+j)div 2;
          if (sir[a,k]=b)and(sir[a,k-1]<b) then begin cbinarp:=k;ok:=1;end
                 else if sir[a,k]>=b then j:=k-1
                          else i:=k+1;
          end;
    if ok=0 then cbinarp:=-1;
end;

function cbinaru(a,b,u:longint):longint;
var i,j,k,ok:longint;
begin
    cbinaru:=-1; ok:=0;
     if (b<sir[a,1])and(ok=0) then begin  cbinaru:=-1;ok:=1;end;
     if (b>sir[a,u])and(ok=0) then begin cbinaru:=-1;ok:=1;end;
     if (b=sir[a,u])and(ok=0) then begin cbinaru:=u;ok:=1;end;
     i:=1;j:=u;
     while(i<=j) and(ok=0) do
           begin
           k:=(i+j) div 2;
           if(sir[a,k]=b) and((sir[a,k+1]>b) or(k=u)) then begin cbinaru:=k;ok:=1;end
                   else if sir[a,k]>b then j:=k-1
                            else i:=k+1;
           end;
     if ok=0 then cbinaru:=-1;
end;
begin
    assign(f,'jocxzero.in'); reset(f);
    assign(g,'jocxzero.out');rewrite(g);
    readln(f,p);
    readln(f,n,m,k);
    for j:= 1 to n do
    begin
        for i:= 1 to m do
        begin
        read(f,c);
        if c='X'then aa[j,i]:=1
            else if c='0' then aa[j,i]:=0;
        end;
        readln(f);
        end;
    {for i:=1 to n do
    begin
        for j:=1 to m do write(aa[i,j]);
        writeln
    end;}
     st[1,1]:=1;sus[1,1]:=1;sts[1,1]:=1;
     for j:=2 to m do
        begin
           if aa[1,j]=aa[1,j-1] then st[1,j]:=st[1,j-1]+1
                else st[1,j]:=1;
           sus[1,j]:=1;
           sts[1,j]:=1;
        end;
     for i:=2 to n do
        begin
            if aa[i,1]=aa[i-1,1] then sus[i,1]:=sus[i-1,1]+1
                else sus[i,1]:=1;
            st[i,1]:=1;
            sts[i,1]:=1;
        end;
     for i:=2 to n do
        for j:=2 to m do
            begin
                if aa[i,j]=aa[i,j-1] then st[i,j]:=st[i,j-1]+1 else st[i,j]:=1;
                if aa[i,j]=aa[i-1,j] then sus[i,j]:=sus[i-1,j]+1 else sus[i,j]:=1;
                if aa[i,j]=aa[i-1,j-1] then sts[i,j]:=sts[i-1,j-1]+1 else sts[i,j]:=1;
            end;
     for i:=n downto 1 do stj[i,1]:=1;
     for j:=2 to m do stj[n,j]:=1;
     for i:=n-1 downto 1 do
        for j:=2 to m do
            if aa[i,j]=aa[i+1,j-1] then stj[i,j]:=stj[i+1,j-1]+1 else stj[i,j]:=1;
     for i:= 1 to n do
        for j:=1 to m do
            begin
                x:=aa[i,j];
                if sus[i,j]>=k then inc(bb[x]);
                if st[i,j]>=k then inc(bb[x]);
                if sts[i,j]>=k then inc(bb[x]);
                if stj[i,j]>=k then inc(bb[x]);
            end;
     if p=1 then writeln(g,bb[1],' ',bb[0])
     else
     begin
        for j:=1 to m do
            begin
                d[0]:=0;d[1]:=0;
                for i:=1 to n do
                    begin
                           x:=aa[i,j];
                           if st[i,j]>=k then inc(d[x]);
                           if sus[i,j]>=k then inc(d[x]);
                           if sts[i,j]>=k then inc(d[x]);
                           if stj[i,j]>=k then inc(d[x]);
                    end;
                sir[1,j]:=sir[1,j-1]+d[1];
                sir[0,j]:=sir[0,j-1]+d[0];
            end;
        readln(f,q);
        for i:= 1 to q do
            begin
                readln(f,c,b);
                if c='X' then a:=1 else a:=0;
                p1:=cbinarp(a,b,m-1);
                p2:=cbinaru(a,b,m-1);
                if p1=-1 then writeln(g,0)
                    else writeln(g,p2-p1+1);
            end;
     end;
    close(f);
    close(g);
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 #2505 jocxzero

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2505 jocxzero 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!