== include(page="template/taskheader" task_id="intrus") ==
Poveste şi cerinţă...
!>problema/intrus?example.jpeg!
Terminalul unui aeroport este o sală foarte mare având forma unui dreptunghi împărţit în pătrate cu latură unitară. Aici se află mai multe persoane, care trebuie să poarte la vedere un ecuson cu un cod de bare care poate fi citit în orice moment de camerele de supraveghere şi decodificat de calculatoarele serviciului de protecţie şi pază. Într-un pătrat cu latură unitară poate să se afle doar o singură persoană la un moment dat. Sala este reprezentată printr-o matrice cu $R$ linii şi $C$ coloane, elementele sale fiind numere naturale de cel mult $6$ cifre cu valorile: $0$ – pentru spaţiu neocupat, respectiv numere naturale nenule, care reprezintă identificatorul $(ID-ul)$ persoanelor. Printre aceste persoane există persoane infiltrate (intruşi) care au ID-uri cu valori identice cu ale altor persoane. Dacă există două sau mai multe persoane cu acelaşi $ID$, acestea sunt considerate toate suspecte. Intruşii vor să ajungă în apropierea unor $VIP$-uri (persoane importante), pentru a le înregistra discuţiile cu un microfon care poate înregistra sunete în interiorul unui pătrat cu latura $D$, în centrul căruia se află chiar el. Acest pătrat nu este cuprins neapărat integral în matricea sălii (vedeţi figura alăturată)! Prin convenţie, $ID$-urile $VIP$-urilor sunt numere prime distincte. În plus, şi un $ID$ al unui $VIP$ poate fi copiat, crescând astfel numărul suspecţilor. Un $VIP$ se caracterizează printr-un nivel de importanţă: cu cât $ID$-ul este un număr mai mare, cu atât nivelul de importanţă este mai mare (este „mai importantă”). Persoanele suspecte au asociat un „grad de periculozitate”. Acesta este cu atât mai mare cu cât numărul de $VIP$-uri aflate în $interiorul$ pătratului de latură $D$, în centrul căruia se află suspectul, este mai mare. Dacă există doi suspecţi cu acelaşi grad de periculozitate, se consideră „mai periculoasă” persoana care are în pătratul său $VIP$-ul cu $ID$-ul cel mai mare. În caz de egalitate, se consideră „mai periculoasă” persoana care este aşezată pe o linie cu un indice mai mic, iar la egalitate de indici de linii, pe o coloană cu indice mai mic. Există şi persoane suspecte cu $gradul de periculozitate 0$, dacă în interiorul pătratului în centrul căruia se plasează nu există niciun număr prim.
h2. Cerinţă
1. Să se determine numărul persoanelor suspecte aflate în sala de aşteptare.
2. Să se determine $ID$-ul şi coordonatele persoanelor suspecte, (RS ~i~ -linia suspectului $i$, CS ~i~ -coloana suspectului $i$) în ordinea descrescătoare a „gradului de periculozitate”.
h2. Date de intrare
Fişierul de intrare $intrus.in$ ...
Fişierul de intrare $intrus.in$ va conţine pe prima linie valoarea $p$, care poate fi doar $1$ sau $2$. Linia a doua va conţine valorile $R, C$ şi $D$, separate prin câte un spaţiu. Pe următoarele $R$ linii, câte $C$ numere naturale de cel mult $6$ cifre, separate prin câte un spaţiu, reprezentând elementele matricei descrise în enunţ.
h2. Date de ieşire
În fişierul de ieşire $intrus.out$ ...
Dacă $p=1$, se cere doar rezolvarea primei cerinţe. În acest caz, fişierul de ieşire $intrus.out$ va conţine o singură valoare $T$ (care poate fi şi $0$), reprezentând numărul persoanelor suspecte. Dacă $p=2$, se va rezolva numai a doua cerinţă. În acest caz fişierul de ieşie $intrus.out$ va conţine pe fiecare linie câte $3$ numere naturale nenule: ID ~i~ (ID-ul intrusului i), R ~i~ , C ~i~ (linia, respectiv coloana în care se află intrusul), separate prin câte un spaţiu. Dacă nu există niciun suspect, în prima linie a fişierului de ieşire intrus.out se va scrie $-1$.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $0 < R, C ≤ 1000$
* $3 ≤ D ≤ 9$, $D$ număr impar.
* Pentru $p=2$ se garantează că numărul suspecţilor nu depăşeşte $10%$ din totalul persoanelor aflate în sală.
h2. Exemplu
table(example). |_. intrus.in |_. intrus.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicaţie
...
table(example). |_. intrus.in |_. intrus.out |_. Explicatie |
| 1
3 4 3
1 0 7 3
5 2 3 0
3 2 0 1
| 7
| p=1, se rezolvă doar cerinţa 1. Există 2 ID-uri egale cu 2 şi 3 ID- uri egale cu 3, deci avem 5 suspecţi.
|
|2
3 4 3
1 0 7 8
5 2 3 0
3 2 0 9
| 2 2 2
2 3 2
3 2 3
3 3 1
| p=2, se rezolvă doar cerinţa 2.
Persoana cu ID-ul 2, aflată pe linia 2 şi coloana 2 are cel mai mare grad de periculozitate.
Urmează ID-ul 2 din (3, 2), 3 din (2, 3) şi 3 din (3, 1), care reprezintă o persoană suspectă,
deşi zona sa de latură D nu este cuprinsă în întregime în matricea sălii!
|
== include(page="template/taskfooter" task_id="intrus") ==
