Echipajul navei Enterprise, a descoperit pe planeta Marte, zona în care sunt amplasate b baze militare care adăpostesc navele de luptă ale marțienilor. Echipajul navei a reușit să cartografieze zona și a împărțit harta planetei în n x m zone de latură 1, dispuse pe n linii (numerotate de sus în jos de la 1 la n) și m coloane (numerotate de la stânga la dreapta de la 1 la m). Astfel fiecare zonă poate fi identificată prin numărul liniei și al coloanei pe care se află. În fiecare astfel de zonă se află o bază a marțienilor ce adăpostește un număr de nave. Căpitanul navei Enterprise, Jean-Luc Picard a elaborat o strategie de atac terestru a acestor baze militare.
Nava Enterprise poate ateriza într-o zonă în care nu se află o bază marțiană și poate lansa un singur atac (deoarece după primul atac bazele marțiene își vor activa scuturile de protecție). La un atac se vor emite simultan 2 raze laser care vor distruge toate navele marțiene existente în bazele aflate pe direcția acestor raze, în ambele sensuri. Razele sunt emise din centrul zonei în care a aterizat Enterprise și fac unghiuri de 45^o, respectiv 135^o cu linia pe care se află Enterprise.

Cerința

Scrieți un program care, cunoscând configurația bazelor marțiene, determină numărul maxim de nave marțiene pe care Enterprise le poate distruge la un singur atac, precum și linia și coloana zonei în care poate ateriza nava Enterprise astfel încât să distrugă un număr maxim de nave; dacă există mai multe zone în care poate ateriza convenabil pentru Enterprise este să aleagă zona pentru care linia este maximă; dacă există mai multe zone pe linia maximă, se va alege cea pentru care coloana este maximă.

Date de intrare

Fișierul de intrare nave.in conține pe prima linie trei numere naturale n, m și b, separate prin câte un spațiu, reprezentând numărul de linii, numărul de coloane ale hărții planetei Marte, respectiv numărul de baze marțiene. Pe fiecare dintre următoarele b linii este descrisă câte o bază marțiană sub forma a trei numere naturale separate prin câte un spațiu lin col nr, reprezentând linia și coloana pe care se află baza marțiană, respectiv numărul de nave aflate în baza marțiană respectivă.

Date de ieșire

Fișierul de ieșire nave.out va conține pe prima linie trei numere naturale nrmax, linmax, colmax, separate prin câte un spațiu, reprezentând numărul maxim de nave marțiene pe care Enterprise le poate distruge la un singur atac, precum și linia și coloana zonei în care poate ateriza nava Enterprise astfel încât să distrugă un număr maxim de nave; dacă există mai multe zone în care poate ateriza convenabil pentru Enterprise este să aleagă zona pentru care linia este maximă; dacă există mai multe zone pe linia maximă, se va alege cea pentru care coloana este maximă.

Restricții și precizări

1 ≤ n, m ≤ 100
n x m ≤ b²
b ≤ n * m / 2
1 ≤ lin ≤ n; 1 ≤ col ≤ m; 1 ≤ nr ≤ 1000

Exemplu

nave.in

nave.out

29 4 2

Explicație

Harta zonei unde se găsesc bazele marțiene este:

Dacă nava Enterprise aterizează în zona situată pe linia 4 și coloana 2, va distruge un număr maxim de nave (29).

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

#include <fstream>
#define NMAX 102

using namespace std;
ifstream fin("nave.in");
ofstream fout("nave.out");
int n, m;
int nrmax, linmax, colmax;
int a[NMAX][NMAX];
int dl[]={1,-1, 1,-1};
int dc[]={1, 1,-1,-1};
void citire();
void bordare();
int cate(int lin, int col);

int main()
{int i, j, nr;
 citire();
 bordare();
 for (i=1; i<=n; i++)
     for (j=1; j<=m; j++)
         if (a[i][j]==0)
             {
              nr=cate(i,j);
              if (nr>=nrmax) {nrmax=nr; linmax=i; colmax=j;}
             }
fout<<nrmax<<' '<<linmax<<' '<<colmax<<'\n';
fout.close();
return 0;
}

void citire()
{int i, lin, col, nr, b;
 fin>>n>>m>>b;
 for (i=0; i<b; i++)
     {fin>>lin>>col>>nr;
      a[lin][col]=nr;}
}

void bordare()
{int i;
 for (i=0; i<=m+1; i++) a[0][i]=a[n+1][i]=-1;
 for (i=0; i<=n+1; i++) a[i][0]=a[i][m+1]=-1;
}

int cate(int lin, int col)
{int k,i,j, rez=0;
 for (k=0; k<4; k++)
     {
     i=lin; j=col;
     while (a[i][j]!=-1)
           {rez+=a[i][j]; i+=dl[k]; j+=dc[k];  }
     }
 return rez;
}

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 #2898 nave

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