#1187
Roboti1
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 1x1
. 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)
.
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.
ONI 2015, Clasa a IX-a
Problema | Roboti1 | Operații I/O |
roboti1.in /roboti1.out
|
---|---|---|---|
Limita timp | 0.1 secunde | Limita memorie |
Total: 8 MB
/
Stivă 8 MB
|
Id soluție | #45104952 | Utilizator | |
Fișier | roboti1.cpp | Dimensiune | 1.51 KB |
Data încărcării | 02 Octombrie 2023, 20:59 | Scor / rezultat | 10 puncte |
roboti1.cpp: In function 'int nr_roboti(int)': roboti1.cpp:21:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] for(i=0;i<c.size();i++) ^
Test | Timp | Mesaj evaluare | Scor posibil | Scor obținut | ||
---|---|---|---|---|---|---|
0 | 0 secunde | OK. | 5 | 5 | ||
1 | 0 secunde | Raspuns gresit. | 5 | 0 | ||
2 | 0 secunde | OK. | 5 | 5 | ||
3 | 0 secunde | Raspuns gresit. | 5 | 0 | ||
4 | 0 secunde | Raspuns gresit. | 5 | 0 | ||
5 | 0 secunde | Raspuns gresit. | 5 | 0 | ||
6 | 0 secunde | Raspuns gresit. | 5 | 0 | ||
7 | 0 secunde | Raspuns gresit. | 5 | 0 | ||
8 | 0 secunde | Raspuns gresit. | 5 | 0 | ||
9 | 0 secunde | Raspuns gresit. | 5 | 0 | ||
10 | 0 secunde | Raspuns gresit. | 5 | 0 | ||
11 | 0 secunde | Raspuns gresit. | 5 | 0 | ||
12 | 0 secunde | Raspuns gresit. | 5 | 0 | ||
13 | 0.004 secunde | Raspuns gresit. | 5 | 0 | ||
14 | 0.012 secunde | Raspuns gresit. | 5 | 0 | ||
15 | 0.02 secunde | Raspuns gresit. | 5 | 0 | ||
16 | 0.024 secunde | Raspuns gresit. | 5 | 0 | ||
17 | 0.028 secunde | Raspuns gresit. | 5 | 0 | ||
18 | 0.048 secunde | Raspuns gresit. | 5 | 0 | ||
19 | 0.048 secunde | Raspuns gresit. | 5 | 0 | ||
Punctaj total | 10 |
www.pbinfo.ro permite evaluarea a două tipuri de probleme:
Problema Roboti1 face parte din prima categorie. Soluția propusă de tine va fi evaluată astfel:
Suma punctajelor acordate pe testele utilizate pentru verificare este 100. Astfel, soluția ta poate obține cel mult 100 de puncte, caz în care se poate considera corectă.