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 |
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 , împărţită în pătrate cu latura egală cu , reprezentată sub forma unui tablou bidimensional cu linii şi 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 robotul primeşte comanda de a se poziţiona într-un pătrat specificat prin coordonatele .
În funcţie de traiectoria de deplasare roboţii folosiţi sunt de două tipuri. La momentul de timp robotul de tip vopseşte pătratele aflate la coordonatele: şi , iar robotul de tip vopseşte pătratele aflate la coordonatele: şi . Pentru vopsirea unui pătrat se consumă un litru de vopsea. Pe tablă sunt aşezaţi roboţi.
Cerinţe
Cunoscând pentru cei roboţi coordonatele iniţiale se cere să se determine:
- Cantitatea totală de vopsea care a fost folosită de roboţi după 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 cu două traiectorii paralele a doi roboţi de tip , iar colţurile dreptunghiului sunt 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 , şi , cu semnificaţiile din enunţ, despărţite prin câte un singur spaţiu.
Pe fiecare dintre următoarele linii se află câte trei valori naturale nenule , şi , despărţite prin câte un spaţiu, unde: reprezintă coordonatele iniţiale unde se poziţionează robotul , iar 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 nenul ce reprezintă cantitatea totală de vopsea care este folosită de roboţi după unităţi de timp.
A doua linie conţine un număr natural nenul 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 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 robotul se poziţionează în pătratul specificat prin coordonatele ş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.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 |
Explicaţie
- În primul exemplu:
- Cantitatea de vopsea care este folosită de roboţi după unităţi de timp este .
- Nu se pot forma dreptunghiuri.
- În al doilea exemplu:
- Cantitatea de vopsea care este folosită de roboţi după unităţi de timp este .
- Singurele dreptunghiuri corect formate după au colţurile în pătratele de coordonate:
- , respectiv
- .
- Observăm faptul că primul dreptunghi se formează după (timpul minim)