Fişierul intrare/ieşire:robotics.in, robotics.outSursăONI 2015, clasa a 10-a
AutorEugen NodeaAdăugată deharababurelPuscas Sergiu harababurel
Timp execuţie pe test0.05 secLimită de memorie8192 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

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

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.

Exemplu

robotics.inrobotics.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

Explicaţie

  • În primul exemplu:
    • Cantitatea de vopsea care este folosită de roboţi după t unităţi de timp este 29.
    • Nu se pot forma dreptunghiuri.
  • În al doilea exemplu:
    • 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)
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?