Poluarea Solului - READ FIRST

"O națiune ce își distruge pământurile, se distruge pe sine." - Franklin D. Roosvelt

Aceasta este problema princiapală a hackathon-ului și valorează cele mai multe puncte.
ATENȚIE: Problema va fi numită drept META-TASK în restul concursului.
ATENȚIE: Aceasta problemă valorează $700$ de puncte. La "submissions" scorul maxim este rescalat la $100$ de puncte, dar adevaratul scor va fi vizibil pe leaderboard.

Despre poluarea solului

Originea poluării solului poate fi naturală sau antropogenă și, prin urmare, s-ar putea să fi avut loc cu mult timp în urmă sau recent. Anumiți contaminanți sunt adesea asociați cu activități specifice, cum ar fi utilizarea pesticidelor în agricultură sau radionuclizii proveniți de la centralele nucleare, în timp ce mulți alți contaminanți ar putea rezulta din diverse surse de poluare. (sursa: ONU)

Solul agricol

Sursele principale ale poluării solului în zonele agricole pot fi grupate în funcție de sursele directe (poluare de la punctul de origine), cum ar fi aplicarea pesticidelor și îngrășămintelor minerale, și sursele indirecte (poluare difuză), precum inundațiile și depunerea atmosferică. Solurile poluate reprezintă, de asemenea, o sursă secundară de emisii de contaminanți către aerul înconjurător, apele de suprafață, apele subterane și, ulterior, către oceane.

Principalele surse de poluare a solului în zonele agricole pot fi grupate astfel: i) pesticide; ii) îngrășăminte minerale; iii) îngrășăminte organice (gunoi și nămol de canalizare); iv) apă reziduală pentru irigații; v) materiale plastice precum folii pentru mulci și sere, tuburi de irigații prin picurare și ambalaje goale; vi) și deșeuri rurale. Diferiți contaminanți sunt asociati cu fiecare sursă. (sursa: ONU)

Problema

Megacorporația Chert And, notorie pentru activitățiile sale în sectorul agriculturii, este acuzată de o serie de contaminări grave ale solului la una dintre fermele sale din România. Mai exact, un număr de minidepozite cu pesticide s-au spart la anumite locații și au contaminat tot terenul arabil adiacent.

Oficialii Chert And au refuzat să dea declarații legate de acest incident, și nici legat de locațiile exacte ale contaminării pe terenul de mii de hectare. Așadar, în calitate de activiști ai mediului înrăiți, și programatori deopotrivă, este scopul vostru să vă folosiți de toate mijloacele digitale pe care le aveți la dispoziție ca să alcătuiți un raport cât mai precis referitor la poluarea produsă.

Formal

Terenul agricol poate fi gândit sub forma unei matrici de $N \times N$ celule. Fiecare celulă poate fi in una dintre stările:

• celulă sursă de contaminare, adica unde s-a spart un depozit de pesticide
• celulă arabilă, adica unde se plantau diverse produse ale corporației
• alt tip de celulă, irelevant pentru problema.

O celulă este numită contaminată dacă este arabilă și este vecină cu măcar una dintre următoarele:

• vecină cu o sursă de contaminare ("vecină" = sa aibă o latură comună)
• vecină cu o altă celulă contaminată ("vecină" = sa aibă o latură comună)

Scopul vostru este să raportați pozițiile a cat mai multe celulele arabile, și pentru fiecare dacă este contaminată sau nu.

ATENTIE: Observați ca celulele tip sursă de contaminare (adica unde s-au spart depozite de pesticide) nu sunt celule arabile și nu trebuie raportate.

Output

Această problema este output only, adică trebuie doar să transmiteți comisiei datele gasite prin intermediul platformei, intr-un fisier .txt (sau print copy-paste).

Pe prima linie a fișierului de text pe care il transmiteți, trebuie să fie un număr $K$, numărul de celule arabile pe care le raportați.

Pe următoarele $K$ linii afișați triplete de forma: $i, j, status$, unde $i$ reprezintă linia, $j$ coloana celulei arabile, iar $status$ reprezintă dacă aceasta este contaminată ($status = 1$) sau nu ($status = 0$).

Obținerea datelor

Fiecare dintre celelalte task-uri ale competiției, pe lângă faptul că vă vor recompensa de asemenea cu puncte (în număr mai mic, decât la aceasta problemă), vă vor dezvălui informații despre hartă.

Mai exact, dacă un subtask la o altă problemă este rezolvat corect, în verdict veți găsi un link de Google Drive către mai multe date.

Un batch de date este compus din mai multe triplete de forma: $i, j, status$, unde $i$ reprezintă linia, $j$ coloana celulei, iar $status$ reprezintă daca aceasta este o celulă arabilă ($status = 0$) sau o sursă de contaminare ($status = 1$). Observati semnificația diferită a lui $status$ în aceasta secțiune. O celulă arabilă dintr-un batch poate să fie sau să nu fie contaminată, iar $status$ va fi tot $0$

Exemplu de fisier din Google Drive cu date:

1 2 0
56 89 1
3 4 0
123 456 0
12 345 1

Punctarea

Punctarea se face parțial, pe măsură ce raportați mai multe celule arabile.

Mai exact, se asigură faptul că există $7000$ celule arabile.

Pentru fiecare astfel de celulă distinctă raportată în input-ul vostru, veți primi:

• $0.1$ puncte dacă status-ul raportat corespunde cu cel real
• $0.05$ puncte dacă status-ul raportat nu corespunde cu cel real

Dacă raportul este perfect, veți obtine un total de $700$ de puncte la această problemă.

ATENȚIE! Dacă raportați o celulă, dar aceasta nu este arabilă, atunci punctajul pentru submisia respectiva va fi nul. Daca includeți o celulă de două ori, dar cu $status$ diferit, atunci punctajul pentru submisia respectivă va fi nul. Daca repetați un triplet de valori, acesta va fi considerat doar o dată la evaluare.

Precizări

• $N = 500$

Exemplu

În acest exemplu avem ilustrată o posibilă minifermă, în care celulele roșii reprezintă surse de contaminare, celule portocalii reprezintă celule arabile contaminate, iar celulele verzi reprezintă celule arabile necontaminate. Trebuie raportate doar celulele portocalii și verzi. Concurenții trebuie să-și dea seama despre celulele arabile dacă sunt contaminate sau nu.

O submisie pentru punctaj complet ar arăta astfel pentru exemplul ilustrat:

25
2 6 1
2 7 1
3 7 1
4 2 1
5 2 1
5 3 1
6 1 1
6 3 1
7 2 1
9 9 1
9 10 1
10 9 1
4 9 0
5 7 0
5 8 0
5 9 0
6 7 0
6 8 0
6 9 0
7 5 0
7 8 0
11 11 0