Simulare🎅🏼🎄 | lumini

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 $(x_R, x_G, x_B)$. 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) * 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 $(2^2 + 0^2 + 0^2) * 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 este $(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 în cealaltă), toată 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ță

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 \leq 1000$
• $1 \leq C \leq 2$
• Prima cerință valorează $30$ de puncte, iar a doua cerință $70$.
• Pentru a doua cerință, pentru $20$ din cele $70$ de puncte, $N, M \leq 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