Pracsiu Dan (dnprx) 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
$$ \left( \left[ \frac{x_G}{x_R}\right]^2 + \left[ \frac{x_B}{x_G}\right]^2 + \left[ \frac{x_R}{x_B}\right]^2 \right) \cdot 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.
Cerința
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.
Restricții și precizări
N, M ≤ 10001 ≤ 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 - Pentru citire se recomandă folosirea biblitotecii
<cstdio>din C++.
Exemplul 1:
lumini.in
3 2 1 0 64 64 64 64 0 128 128 128 192 192 192 0 192 192 192 192 0
lumini.out
2
Explicație
Se va rezolva doar prima cerință:
Primele 2 becuri sunt (0, 64, 64), (64, 64, 0). Acestea au intensitate 1000. (128, 128, 128) și (192, 192, 192) au intensitate 3000. (0, 192, 192) și (192, 192, 0) au intensitate 1000.
Exemplul 2:
lumini.in
3 2 2 0 64 64 64 64 0 128 128 128 192 192 192 0 192 192 192 192 0
lumini.out
1999
Explicație
Se va rezolva doar cerința a doua:
(0, 64, 64) + (0, 192, 192) = (0, 0, 0)
(64, 64, 0) + (192, 192, 0) = (0, 0, 0)
Deci, în total, 2 perechi formează negru.
Pentru P = 2000 se poate forma oricare dintre cele două perechi