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

  • ... ≤ ... ≤ ...

Exemplu

robotics.inrobotics.out
This is some
text written on
multiple lines.
This is another
text written on
multiple lines.

Explicaţie

...

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?