robotics

Robotics

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 |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

| 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
|

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") ==