Editing 2343 - Bec


= Enunț =
Într-o pădure sunt plantați <code>N*M</code> copaci, pe <code>N</code> rânduri şi <code>M</code> 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ă <code>K</code> 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 <code>K-1</code> becuri şi să păstreze doar becul care luminează numărul maxim <code>C</code> de copaci. Dacă mai multe becuri dintre cele <code>K</code> luminează <code>C</code> copaci, pădurarul îl va păstra pe cel mai util adică care are cel mai mic consum de energie electrică.

= Cerința =
Să se scrie un program care să determine: 

<code>1.</code> numărul maxim <code>X</code> de copaci ce pot fi luminați de unul dintre cele <code>K</code> becuri

<code>2.</code> poziția (rândul <code>R</code> şi coloana <code>C</code>) becului cel mai util păstrat de pădurar.

= Date de intrare =
Fișierul de intrare <code>bec.in</code> conține:

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

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

= Restricții și precizări =

* <code>2 ≤ N ≤ 150</code>; <code>2 ≤ M ≤ 150</code>
* <code>1 ≤ K ≤ N</code>; <code>1 ≤ K ≤ M</code>; <code>1 ≤ K ≤ 100</code>
* <code>1 ≤ A ≤ N</code>; <code>1 ≤ B ≤ M</code>; <code>1 ≤ C ≤ 10000</code>  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ă <code>50%</code> din punctaj pentru rezolvarea corectă a cerinței <code>1</code> și <code>50%</code> din punctaj pentru rezolvarea corectă a cerinței <code>2</code>.

= Exemplul 1: =
<code>bec.in</code>
 1 5 4 3
 2 3 80
 4 2 100
 4 3 70
<code>bec.out</code>
 14 

=== Explicație ===
<code>P=1</code> . 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).

== Încărcare soluție ==

=== Lipește codul aici ===
<syntaxhighlight lang="python" line="1">
import math

A = [[0] * 151 for _ in range(151)]
n, m, k, p = map(int, input().split())
X = [0] * 101
Y = [0] * 101
C = [0] * 101

def cmmdc(a, b):
    while b != 0:
        r = a % b
        a = b
        b = r
    return a

for i in range(1, k + 1):
    X[i], Y[i], C[i] = map(int, input().split())
    A[X[i]][Y[i]] = 1

c = 0
xmin = 0
cmin = 10000
cmax = 0

for x in range(1, k + 1):
    c = 0
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if A[i][j] == 0 and cmmdc(abs(X[x] - i), abs(Y[x] - j)) == 1:
                c += 1
    if c > cmax:
        cmax = c
        xmin = x
        cmin = C[x]
    elif c == cmax and C[x] < cmin:
        xmin = x
        cmin = C[x]

if p == 1:
    print(cmax)
else:
    print(X[xmin], Y[xmin])


</syntaxhighlight>