Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2015-04-10 09:34:26.
Revizia anterioară Revizia următoare

Fişierul intrare/ieşire:	robotics.in, robotics.out	Sursă	ONI 2015, clasa a 10-a
Autor	Eugen Nodea	Adăugată de	Puscas Sergiu •harababurel
Timp execuţie pe test	0.025 sec	Limită de memorie	8192 kbytes
Scorul tău	N/A	Dificultate	N/A

Robotics

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 \times 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 $\left ( x, y \right )$ .

Î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: $\left ( x-t, y+t \right )$ şi $\left ( x+t, y-t \right )$ , iar robotul de tip $2$ vopseşte pătratele aflate la coordonatele: $\left ( x+t, y+t \right )$ şi $\left ( x-t, y-t \right )$ . Pentru vopsirea unui pătrat se consumă un litru de vopsea. Pe tablă sunt aşezaţi $m$ roboţi.

Cerinţe

Cunoscând pentru cei $m$ roboţi coordonatele iniţiale $(x_{i}, y_{i}), i \in \left \{ 1, 2, ..., m \right \}$ se cere să se determine:

Cantitatea totală de vopsea care a fost folosită de roboţi după $t$ unităţi de timp.
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$ şi $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 $x_{i}$ , $y_{i}$ şi $z_{i}$ , despărţite prin câte un spaţiu, unde: $x_{i}, y_{i}$ reprezintă coordonatele iniţiale unde se poziţionează robotul $i$ , iar $z_{i}$ 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 $T_{min}$ ce reprezintă numărul minim de unităţi de timp necesare formării primului dreptunghi de arie nenulă.