# PBinfo #2343 – bec – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: deivid

## Enunț

Enunț
Într-o pădure sunt plantați N*M copaci, pe N rânduri şi M coloane, fiecare copac aflându-se la egală distanţă de copacii vecini. Întrucât în pădure este cam întuneric, pădurarul (care supraveghează pădurea) montează K becuri (câte un bec într-un copac). Aceste becuri au consum diferit de energie electrică. Fiecare bec luminează doar o parte dintre copaci. Un copac este luminat de un bec dacă, trasând o linie dreaptă de la el la bec, niciun alt copac sau bec nu se află pe acea linie. 
Energia electrică fiind scumpă, pădurarul va trebui să renunţe la K-1 becuri şi să păstreze doar becul care luminează numărul maxim C de copaci. Dacă mai multe becuri dintre cele K luminează C copaci, pădurarul îl va păstra pe cel mai util adică care are cel mai mic consum de energie electrică. 



quick image uploader


Cerința
Să se scrie un program care să determine: 
1. numărul maxim X de copaci ce pot fi luminați de unul dintre cele K becuri
2. poziția (rândul R şi coloana C) becului cel mai util păstrat de pădurar. 

Date de intrare
Fișierul de intrare bec.in conține:

pe prima linie, patru numere naturale P N M K, separate prin câte un spaţiu, reprezentând: cerința P ce trebuie rezolvată (1 sau 2), numărul N de rânduri,  numărul M de coloane, şi  numărul K de becuri
pe fiecare din următoarele K linii, câte trei numere naturale A B C, separate prin câte un spaţiu, reprezentând rândul A şi coloana B în care se află fiecare bec şi consumul C de energie electrică a acestuia.


Date de ieșire
Dacă P=1, atunci fișierul de ieșire bec.out va conține pe prima linie numărul X ( răspunsul la cerința 1). Altfel, dacă P=2, atunci fişierul de ieşire bec.out va conţine pe prima linie cele două numere naturale R C (răspunsul la cerința 2) separate prin câte un spațiu, cu semnificația din enunț. 

Restricții și precizări

2 ≤ N ≤ 150; 2 ≤ M ≤ 150
1 ≤ K ≤ N; 1 ≤ K ≤ M; 1 ≤ K ≤ 100
1 ≤ A ≤ N; 1 ≤ B ≤ M; 1 ≤ C ≤ 10000  pentru fiecare bec
nu există două becuri asezate pe același rând  și aceeași coloanâ
nu există două becuri cu același consum de energie electrică
se acordă 50% din punctaj pentru rezolvarea corectă a cerinței 1 și 50% din punctaj pentru rezolvarea corectă a cerinței 2.

Exemplul 1:
bec.in

1 5 4 3
2 3 80
4 2 100
4 3 70
bec.out

14 
Explicație
P=1 . Se rezolvă cerința 1.
Numerotăm copacii ca în tabloul alăturat. Primul bec, situat în rândul 2 şi coloana 3 (consum energie 80) luminează 14 copaci (nu îi luminează pe cei numerotați cu 5, 12 şi 16). 
Al doilea bec, situat în rândul 4 şi coloana 2 (consum energie 100) luminează 13 copaci (nu îi luminează pe cei numerotați cu 2, 6, 7 şi 13). 
Al treilea bec, situat în rândul 4 şi coloana 3 (consum energie 70) luminează 14 copaci (nu le luminează pe cei numerotați cu 3, 5 şi 12).

Exemplul 2:
bec.in

2 5 4 3
2 3 80
4 2 100
4 3 70
bec.out

4 3 
Explicație
P=2. Se rezolvă cerința 2.
Becurile ce luminează numărul maxim de copaci (X=14) sunt: 1 (consum de energie 80) și 3 (consum de energie 70). Becul 3 are consumul de energie mai mic decât cel al primului bec (70<80) și se află în rândul R=4 şi coloana C=3

## Cod sursă C++

```cpp
#include<fstream>
#include <cmath>
using namespace std;
ifstream f("bec.in");
ofstream g("bec.out");
int n,a[151][151],k,m,cer;
void citeste()
{
    int i,x,y,c;
    f>>cer>>n>>m>>k;
    for(i=1; i<=k; i++)
    {
        f>>x>>y>>c;
        a[x][y]=c;
    }
    f.close();
}
int cmmdc(int x, int y)
{
    if (x*y==0) return x+y;
    if(x>y) return cmmdc(x%y, y);
    else return cmmdc(x,y%x);
}
int nrr(int x, int y)
{
    int p=0,i,j;
    for(i=1; i<=n; i++)
        for(j=1; j<=m; j++)
            if ((a[i][j]==0)&& (cmmdc(abs(x-i), abs(y-j))==1)) p++;
    return p;
}
int main()
{
    citeste();
    int i,j, max=0, cmin, x,i0=0,j0=0;
    for(i=1; i<=n; i++)
        for(j=1; j<=m; j++)
            if(a[i][j])
            {
                x=nrr(i,j);
                if (max==0)
                {
                    max=x;
                    cmin=a[i][j];
                    i0=i;
                    j0=j;
                }
                else if (max<x)
                {
                    max=x;
                    cmin=a[i][j];
                    i0=i;
                    j0=j;
                }
                else if((max==x)&&(cmin>a[i][j]))
                {
                    cmin=a[i][j];
                    i0=i;
                    j0=j;
                }
            }
    if(cer==1)g<<max<<endl;
    else g<<i0<<' '<<j0<<endl;
    g.close();
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/2343)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/2343/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-2343/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)