2343 - Bec

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ă.

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).

Încărcare soluție

Lipește codul aici

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])