== include(page="template/taskheader" task_id="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 <tex>n \times n</tex>, împărţită în pătrate cu latura egală cu <tex>1</tex>, reprezentată sub forma unui tablou bidimensional cu <tex>n</tex> linii şi <tex>n</tex> 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 <tex>t=0</tex> robotul primeşte comanda de a se poziţiona într-un pătrat specificat prin coordonatele <tex>\left ( x, y \right )</tex>.
În funcţie de traiectoria de deplasare roboţii folosiţi sunt de două tipuri. La momentul de timp <tex>t</tex> robotul de tip <tex>1</tex> vopseşte pătratele aflate la coordonatele: <tex>\left ( x-t, y+t \right )</tex> şi <tex>\left ( x+t, y-t \right )</tex>, iar robotul de tip <tex>2</tex> vopseşte pătratele aflate la coordonatele: <tex>\left ( x+t, y+t \right )</tex> şi <tex>\left ( x-t, y-t \right )</tex>. Pentru vopsirea unui pătrat se consumă un litru de vopsea. Pe tablă sunt aşezaţi <tex>m</tex> roboţi.
h2. Cerinţe
Cunoscând pentru cei <tex>m</tex> roboţi coordonatele iniţiale <tex>(x_{i}, y_{i}), i \in \left \{ 1, 2, ..., m \right \}</tex> se cere să se determine:
* Cantitatea totală de vopsea care a fost folosită de roboţi după <tex>t</tex> 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 <tex>1</tex> cu două traiectorii paralele a doi roboţi de tip <tex>2</tex>, iar colţurile dreptunghiului sunt <tex>4</tex> pătrate care au fost vopsite de doi roboţi de tipuri diferite.
Poveste şi cerinţă...
h2. Date de intrare
Fişierul de intrare $robotics.in$ conţine pe prima linie trei valori naturale nenule <tex>n</tex>, <tex>m</tex> şi <tex>t</tex>, cu semnificaţiile din enunţ, despărţite prin câte un singur spaţiu.
Pe fiecare dintre următoarele <tex>m</tex> linii se află câte trei valori naturale nenule <tex>x_{i}</tex>, <tex>y_{i}</tex> şi <tex>z_{i}</tex>, despărţite prin câte un spaţiu, unde: <tex>x_{i}, y_{i}</tex> reprezintă coordonatele iniţiale unde se poziţionează robotul <tex>i</tex>, iar <tex>z_{i}</tex> reprezintă tipul robotului.
Fişierul de intrare $robotics.in$ ...
h2. Date de ieşire
Fişierul de ieşire $robotics.out$ va avea două linii.
Prima linie conţine un număr natural <tex>C</tex> nenul ce reprezintă cantitatea totală de vopsea care este folosită de roboţi după <tex>t</tex> unităţi de timp.
A doua linie conţine un număr natural nenul <tex>T_{min}</tex> ce reprezintă numărul minim de unităţi de timp necesare formării primului dreptunghi de arie nenulă.
În fişierul de ieşire $robotics.out$ ...
h2. Restricţii
* $1 ≤ t < n ≤ 1 000$
* $1 ≤ m ≤ 2*n$
* $1 ≤ x, y ≤ n$
* Coordonatele celor <tex>m</tex> 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 <tex>t=0</tex> robotul se poziţionează în pătratul specificat prin coordonatele <tex>(x, y)</tex> ş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.
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example). |_. robotics.in |_. robotics.out |
| 13 3 6
3 5 1
7 5 2
7 9 1
| 29
0
|
| 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
|
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicaţie
* În primul exemplu:
** Cantitatea de vopsea care este folosită de roboţi după <tex>t</tex> unităţi de timp este <tex>29</tex>.
** Nu se pot forma dreptunghiuri.
!problema/robotics?robotics1.png!
* În al doilea exemplu:
** Cantitatea de vopsea care este folosită de roboţi după <tex>t</tex> unităţi de timp este <tex>75</tex>.
** Singurele dreptunghiuri corect formate după <tex>t=4</tex> au colţurile în pătratele de coordonate:
*** <tex>(2,7),\:(6,11),\:(10,7),\:(6,3)</tex>, respectiv
*** <tex>(8,9),\:(13,14),\:(17,10),\:(12,5)</tex>.
** Observăm faptul că primul dreptunghi se formează după <tex>t=3</tex> (timpul minim)
!problema/robotics?robotics2.png!
...
== include(page="template/taskfooter" task_id="robotics") ==
