Ne aflăm în secţia de vopsitorie a uzinei Toyota Motor unde inginerii japonezi prezintă ultimul tip de robot industrial de vopsire. În dorinţa de a evidenţia calitatea şi viteza de execuţie a roboţilor, inginerii folosesc pentru demonstraţie o tablă de dimensiunea n×n, împărţită în pătrate cu latura egală cu 1, reprezentată sub forma unui tablou bidimensional cu n linii şi n coloane.
Un robot utilizat pentru vopsire are două braţe telescopice care se deplasează de-a lungul unei axe. Fiecare braţ poate vopsi într-o unitate de timp un singur pătrat. La momentul de timp t=0 robotul primeşte comanda de a se poziţiona într-un pătrat specificat prin coordonatele (x,y).
În funcţie de traiectoria de deplasare roboţii folosiţi sunt de două tipuri. La momentul de timp t robotul de tip 1 vopseşte pătratele aflate la coordonatele: (x-t,y+t) şi (x+t,y-t), iar robotul de tip 2 vopseşte pătratele aflate la coordonatele: (x+t,y+t) şi (x-t,y-t). Pentru vopsirea unui pătrat se consumă 1 litru de vopsea.
Pe tablă sunt aşezaţi m roboţi.

Cerinţă

Cunoscând pentru cei m roboţi coordonatele iniţiale (xi,yi), i=1,…,m, se cere să se determine:
a) Cantitatea totală de vopsea care a fost folosită de roboţi după t unităţi de timp
b) Numărul minim de unităţi de timp necesare formării primului dreptunghi cu arie nenulă. Un dreptunghi corect format este rezultatul intersecţiei a două traiectorii paralele a doi roboţi de tip 1 cu două traiectorii paralele a doi roboţi de tip 2, iar colţurile dreptunghiului sunt 4 pătrate care au fost vopsite de doi roboţi de tipuri diferite.

Date de intrare

Fişierul de intrare robotics.in conţine pe prima linie trei valori naturale nenule n m t, cu semnificaţiile din enunţ, despărţite prin câte un singur spaţiu.
Pe fiecare dintre următoarele m linii se află câte trei valori naturale nenule xi yi zi, despărţite prin câte un spaţiu, unde: xi, yi reprezintă coordonatele iniţiale unde se poziţionează robotul i, iar zi reprezintă tipul robotului.

Date de ieşire

Fişierul de ieşire robotics.out va avea două linii.
Prima linie conţine un număr natural C nenul ce reprezintă cantitatea totală de vopsea care este folosită de roboţi după t unităţi de timp.
A doua linie conţine un număr natural nenul Tmin ce reprezintă numărul minim de unităţi de timp necesare formării primului dreptunghi de arie nenulă.

Restricţii

• 1 ≤ t < n ≤ 1 000
• 1 ≤ m ≤ 2*n
• 1 ≤ x, y ≤ n
• Coordonatele celor m roboţi sunt distincte două câte două.
• Doi roboţi nu se pot afla pe aceeaşi traiectorie la un moment dat.
• La momentul t=0 robotul se poziţionează în pătratul specificat prin coordonatele (x,y) şi vopseşte o singură dată acest pătrat.
• Doi roboţi de tipuri diferite care ajung în acelaşi timp pe un pătrat pot vopsi simultan pătratul.
• Dacă braţul unui robot părăseşte tabla dreptunghiulară, braţul îşi încetează activitatea.
• Pentru rezolvarea corectă a primei cerinţe se acordă 20 de puncte, iar pentru cerinţa a doua se acordă 80 de puncte.

Exemple

robotics.in	robotics.out	Explicaţii
13 3 6 3 5 1 7 5 2 7 9 1	29 0	Cantitatea de vopsea care este folosită de roboţi după t unităţi de timp este 29. Nu se pot forma dreptunghiuri.
19 9 4 4 5 1 4 14 2 2 11 1 14 7 2 5 10 2 14 13 1 7 4 2 7 10 1 12 13 2	75 3	Cantitatea de vopsea care este folosită de roboţi după t unităţi de timp este 75. Singurele dreptunghiuri corect formate după t=4 au colţurile în pătratele de coordonate: (2,7),(6,11),(10,7),(6,3), respectiv (8,9),(13,14),(17,10),(12,5). Observăm faptul că primul dreptunghi se formează după t=3 (timpul minim)

autor: Prof. Eugen Nodea

propunător: Prof. Emanuela Cerchez

Colegiul Naţional ″Emil Racoviţă″

emanuela.cerchez@gmail.com