3463 - Lumini 2

Cerința

Se dă o instalație de N * M lumini. Fiecare lumină este dată prin culoare, în format RGB. Astfel, un element din matrice poate fi considerat un triplet (xR , xG , xB). Fiecare valoare este de la 0 la 255.

Dispersia unei culori se definește ca numărul

([xG/xR]^2+[xB/xG]^2+[xR/xB]^2)⋅1000 (Întâi se calculează partea întreagă, urmând apoi celelalte operații în ordinea cunoscută). Dacă numitorul unei fracții este 0, fracția este nulă. De exemplu, pentru (64, 128, 0), dispersia este (22 + 02 + 02) ∗ 1000 = 4 ∗ 1000 = 4000.

Se știe că dintr-o lumină în alta se poate ajunge dacă sunt adiacente (în una din cele patru direcții) și diferența dispersiilor celor două elemente din matrice, în modul, este mai mică sau egală cu un număr întreg P.

Se știe că formatul RGB este aditiv și culoarea negru = (0,0,0). Pentru fiecare lumină, poate exista alta lumină în matrice astfel încât adunate să dea culoarea negru. Se știe că dacă aceste lumini sunt conectate (adică se poate ajunge direct sau indirect din una in cealaltă), toata instalația se blochează.

De exemplu, dacă adunăm (0, 128, 64) cu (128, 128, 128) vom avea ca rezultat: (128, 0, 196) – adică se adună fiecare indice cu fiecare, iar dacă rezultatul este mai mare decât 255, se scade 256. 1) Câte perechi există în matrice, pentru care conexiunea lor ar determina culoarea negru? 2) Pentru o astfel de instalație dată, care este numărul maxim P, pentru care instalația nu se blochează?

Date de intrare

Pe prima linie din fișierul lumini.in se află trei numere naturale N, M, C. Ultimul număr reprezintă indicele cerinței care trebuie rezolvate. Pe următoarele N linii ale fișierului se găsesc câte 3 * M numere, separate prin câte un spațiu, care definesc fiecare lumină din matrice. Astfel, dintr-un triplet, primul număr este intensitatea R, al doilea G, și al treilea B.

Date de ieșire

Fișierul de ieșire lumini.out va conţine pe prima linie, numărul de perechi formate, dacă trebuie rezolvată prima cerință. Dacă trebuie rezolvată a doua, se va afișa, P-ul găsit.

În cazul în care datele introduse de la tastatură nu îndeplinesc cerințele enunțate, pe ecran se va afișa mesajul "Datele de intrare nu corespund restricțiilor impuse."

Restricții și precizări

• N, M ≤ 1000
• 1 ≤ C ≤ 2
• Prima cerință valoreaza 30 de puncte, iar a doua cerință 70.
• Pentru a doua cerință, pentru 20 din cele 70 de puncte, N, M ≤ 50

Exemplu 1

Intrare

3 2 1
0 64 64 64 64 0
128 128 128 192 192 192
0 192 192 192 192 0

Iesire

2

Rezolvare

<syntaxhighlight lang="python" line> import math

def citire_date():

   with open("lumini.in", "r") as f:
       N, M, C = map(int, f.readline().split())
       matrice = []
       for _ in range(N):
           linie = []
           for _ in range(M):
               r, g, b = map(int, f.readline().split())
               linie.append((r, g, b))
           matrice.append(linie)
   return N, M, C, matrice

def dispersie(rgb):

   r, g, b = rgb
   sum_rgb = r + g + b
   if sum_rgb == 0:
       return 0
   return int(((r / sum_rgb) ** 2 + (g / sum_rgb) ** 2 + (b / sum_rgb) ** 2) * 1000)

def perechi_conexe(N, M, matrice):

   directii = [(-1, 0), (1, 0), (0, -1), (0, 1)]
   vizitat = [[False] * M for _ in range(N)]
   
   def dfs(x, y):
       stack = [(x, y)]
       vizitat[x][y] = True
       while stack:
           cx, cy = stack.pop()
           for dx, dy in directii:
               nx, ny = cx + dx, cy + dy
               if 0 <= nx < N and 0 <= ny < M and not vizitat[nx][ny]:
                   if dispersie(matrice[cx][cy]) == dispersie(matrice[nx][ny]):
                       vizitat[nx][ny] = True
                       stack.append((nx, ny))
   
   componente = 0
   for i in range(N):
       for j in range(M):
           if not vizitat[i][j]:
               dfs(i, j)
               componente += 1
   return componente

def numar_maxim_P(N, M, matrice):

   P_max = 0
   for i in range(N):
       for j in range(M):
           for di, dj in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
               ni, nj = i + di, j + dj
               if 0 <= ni < N and 0 <= nj < M:
                   r1, g1, b1 = matrice[i][j]
                   r2, g2, b2 = matrice[ni][nj]
                   if r1 + r2 <= 255 and g1 + g2 <= 255 and b1 + b2 <= 255:
                       P_max = max(P_max, r1 + r2 + g1 + g2 + b1 + b2)
   return P_max

def scrie_rezultate(rezultat):

   with open("lumini.out", "w") as f:
       f.write(f"{rezultat}\n")

def rezolva():

   N, M, C, matrice = citire_date()

   # Verificarea restrictiilor
   assert 1 <= N <= 1000, "N trebuie sa fie intre 1 si 1000"
   assert 1 <= M <= 1000, "M trebuie sa fie intre 1 si 1000"
   assert 1 <= C <= 2, "C trebuie sa fie 1 sau 2"

   if C == 1:
       rezultat = perechi_conexe(N, M, matrice)
   elif C == 2:
       rezultat = numar_maxim_P(N, M, matrice)

   scrie_rezultate(rezultat)

if __name__ == "__main__":

   rezolva()

</syntaxhighlight>