| Fişierul intrare/ieşire: | roboti2.in, roboti2.out | Sursă | ONI 2015, clasa a 9-a |
| Autor | Sofia Viteleanu | Adăugată de |  Tatomir Alex •atatomir |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 12288 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Roboti2
O firmă de construcţii imobiliare a achiziţionat recent un teren dreptunghiular de dimensiuni N×M. Terenul este împărţit în parcele de dimensiune 1×1. Pe unele dintre cele N×M parcele sunt plantaţi copaci. Firma doreşte construirea unui grandios complex comercial şi este necesară defrişarea întregului teren. În acest scop sunt utilizaţi roboţi, fiecare robot având baza un pătrat de latură L. Suprafaţa defrişată de fiecare robot la un moment dat este chiar aria de acoperire a robotului, L×L. Fiecare robot pătrunde prin colţul stânga sus de coordonate (1, 1), se poate deplasa doar în dreapta şi în jos şi poate părăsi suprafaţa numai prin colţul dreapta jos, de coordonate (N, M).
Cerinta
Cunoscând dimensiunile N, M ale terenului şi coordonatele parcelelor în care sunt plantaţi copaci se cere:
1. Numărul minim de roboţi necesari defrişării întregului teren.
2. Să se răspundă la Q interogări de forma k, unde k este un număr natural. Pentru fiecare interogare de această formă va trebui determinată latura minimă a unui robot astfel încât să fie necesari pentru defrişare cel mult k roboţi.
Date de intrare
Fişierul de intrare roboti2.in conţine:
- Pe prima linie un număr natural p reprezentând varianta cerinţei de rezolvare. Pentru toate testele de intrare, numărul p poate avea doar valoarea 1 sau valoarea 2.
- Pe a doua linie se află 3 numere naturale N, M, T separate prin câte un spaţiu reprezentând numărul liniilor, numărul coloanelor terenului dreptunghiular, respectiv numărul copacilor plantaţi.
- Următoarele T linii conţin fiecare câte două numere naturale x, y separate prin câte un spaţiu, reprezentând linia, respectiv coloana parcelei în care este plantat un copac.
- În cazul cerinţei 1, ultima linie conţine un singur număr natural L, reprezentând latura unui robot.
- În cazul cerinţei 2, penultima linie va conţine un număr natural Q, iar ultima linie Q numere naturale k 1, k 2, ..., k Q separate prin câte un spaţiu, reprezentând numărul maxim de roboţi ce pot fi utilizaţi în fiecare dintre cele Q interogări.
Date de ieşire
- Dacă valoarea lui p este 1, se va rezolva numai cerinţa 1. În acest caz, în fişierul de ieşire roboti2.out se va scrie un singur număr natural n 1, reprezentând numărul minim de roboţi utilizaţi.
- Dacă valoarea lui p este 2, se va rezolva numai cerinţa 2. În acest caz, în fişierul de ieşire roboti2.out se vor scrie Q linii. Fiecare linie i va conţine câte un număr natural n i, reprezentând latura minimă a unui robot astfel încât pentru defrişare să fie utilizaţi cel mult k i roboţi.
Restricţii
- 2 ≤ N, M, L ≤ 150
- 1 ≤ Q ≤ 150
- 1 ≤ k i ≤ 150, 1 ≤ i ≤ Q
- 1 ≤ T ≤ 1000
- Latura robotului nu poate fi mai mare decât dimensiunile terenului
- Pe tot parcursul deplasării, fiecare robot se va afla în interiorul suprafeţei terenului.
- În orice moment în interiorul suprafeţei terenului se va afla cel mult un robot.
Exemplu
| roboti2.in | roboti2.out | Explicatie |
|---|---|---|
| 1 6 8 8 4 1 5 3 3 5 2 6 5 5 4 7 3 8 6 8 4 | 1 | p = 1 Dacă roboţii au latura 4, pentru defrişarea întregului teren este necesar un singur robot. Atenţie! Pentru acest test se rezolvă doar cerinţa 1. |
| 2 6 8 8 4 1 5 3 3 5 2 6 5 5 4 7 3 8 6 8 2 1 3 | 4 1 | p = 2 Prima valoare din fişierul de ieşire reprezintă latura minimă pe care o pot avea roboţii astfel încât pentru defrişarea întregului teren să fie necesar un singur robot, conform primei interogări. A doua valoare din fişierul de ieşire reprezintă latura minimă pe care o pot avea roboţii astfel încât pentru defrişarea întregului teren să fie necesari cel mult trei roboţi, conform celei de-a doua interogări. Atenţie! Pentru acest test se rezolvă doar cerinţa 2. |
