Rezolvare completă PbInfo #2432 Cruce

Se consideră o matrice pătratică de dimensiune N, conţinând numere naturale. Numim cruce de lăţime K reuniunea mulțimii tuturor elementelor aflate pe K linii consecutive ale matricei și a mulțimii tuturor elementelor aflate pe K coloane consecutive ale matricei. Două elemente ale matricei se consideră distincte dacă sunt situate pe poziții distincte în matrice. Se acceptă şi forma degenerată a unei cruci, în formă de T sau L, când una dintre liniile sau coloanele care formează crucea sunt chiar la marginea matricei. Vom defini valoarea unei cruci ca fiind suma elementelor din care aceasta este formată.

Cerința

Scrieți un program care, pentru o valoare K dată, determină o cruce de lățime K a cărei valoare este maximă și poziția ei în matrice. Această poziție va fi exprimată prin perechea de indici reprezentând prima linie din cele K consecutive și prima coloană din cele K consecutive din care este formată crucea.

Date de intrare

Fişierul cruce.in conţine pe prima linie numerele N şi K, iar pe următoarele N linii câte N numere întregi reprezentând în ordine, pe linii, elementele matricei. Numerele de pe aceeaşi linie sunt separate prin câte un spaţiu.

Date de ieșire

Fişierul cruce.out va conţine trei numere Vmax L C, separate prin câte un spaţiu, reprezentând valoarea maximă determinată pentru o cruce de lățime K, respectiv linia și coloana care exprimă poziția acesteia în matrice.

Restricții și precizări

  • 1 ≤ N ≤ 500
  • 1 ≤ K < N
  • Numerele din matrice sunt din intervalul [-5000, 5000]
  • Liniile şi coloanele se indexează începând cu 1.
  • Dacă există mai multe cruci de lățime K de valoare maximă, se va lua în considerare poziția cu indicele liniei mai mic, iar în caz de egalitate a liniilor poziția celei cu indicele coloanei mai mic.
  • La olimpiadă s-au oferit 10 puncte din oficiu, aici vor fi date pe exemple.

Exemplu

cruce.in

5 2
1 -2 3 -1 4
-3 2 2 -2 -1
1 2 3 4 5
1 0 -7 1 1
3 2 1 2 3

cruce.out

23 2 4

Explicație

Elementele ce formează crucea de valoare maxima sunt:

1 -2 3 -1 4
-3 2 2 -2 -1
1 2 3 4 5
1 0 -7 1 1
3 2 1 2 3


Exemplu

cruce.in

5 2
0 0 1 1 1
2 2 2 2 2
2 2 2 2 2
2 2 2 2 2
0 0 1 1 1

cruce.out

28 2 3

Explicație

Valoarea maximă a unei cruci de lățime 2 este 28.
În exemplu mai există cruci de valoare 28, dar cu indicele de început al liniei sau coloanei mai mari.
De exemplu crucea care începe de pe linia 3 și coloana 3.

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

var n,k,i,j,sl,sc,l,c,s,smaxim:longint;
a,sum:array[0..500,0..500]of longint;  lin,col:array[1..500] of longint;
f,g:text;

begin
   assign(f,'cruce.in');reset(f);
   readln(f,n,k);
   for i:=1 to n do
      for j:=1 to n do
         begin
         read(f,a[i,j]);
         a[i,0]:=a[i,0]+a[i,j]; a[0,j]:=a[0,j]+a[i,j];
         sum[i,j]:= a[i,j] + sum[i,j-1] + sum[i-1,j] - sum[i-1,j-1];
         if j=n then
            begin
            sl:=sl+a[i,0];
            if i=k then lin[1]:=sl;
            if i>k then
               begin
                  sl:=sl-a[i-k,0];
                  lin[i-k+1]:=sl;
               end;
            end;
         end;
   close(f);
   for j:=1 to k do sc:=sc+a[0,j];
   col[1]:=sc;
   for j:=k+1 to n do
      begin
         sc:=sc+a[0,j]-a[0,j-k];
         col[j-k+1]:=sc;
      end;
   smaxim:=-maxlongint;
   for i:=1 to n-k+1 do
      for j:=1 to n-k+1 do
         begin
            s:=lin[i]+col[j]-(sum[i+k-1,j+k-1]-sum[i-1,j+k-1]-sum[i+k-1,j-1]+sum[i-1,j-1]);
            if s>smaxim then
               begin
                  smaxim:=s;l:=i;c:=j;
               end;

         end;
assign(g,'cruce.out');rewrite(g);
writeln(g,smaxim,' ',l,' ',c);
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 #2432 Cruce

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