#2152
Arhipelag
În regiunea Ionia a lumii grecești antice, regiune ce corespunde teritoriului actual al Mării Egee, există mai multe insule. Harta mării este reprezentată de o matrice de dimensiuni N•M
, având valori de 1
și 0
, iar fiecare element din matrice reprezintă o zonă de dimensiune 1•1
din mare. Liniile matricei sunt numerotate de la 1
la N
, de sus în jos, iar coloanele de la 1
la M
, de la stânga la dreapta. Astfel, colțul din stânga sus al matricei este asociat zonei (1,1)
, iar colțul din dreapta jos corespunde zonei (N,M)
.
Un element care conține valoarea 0
reprezintă faptul că în acea zonă se află apă. O insulă este determinată
de un dreptunghi format în totalitate din valori de 1
. Se garantează faptul că toate zonele care conțin valoarea 1
formează dreptunghiuri valide și că oricare două insule sunt separate de apă.
Ionienii, fiind oameni practici, doresc construirea unui far-bibliotecă (așezat pe o platformă 1•1
), într-o zonă acoperită de apă. Poziția platformei va fi aleasă într-o celulă C
astfel încât suma distanțelor dintre toate insulele și C
să fie minimă. Distanța dintre o celulă C
și o insulă este definită ca fiind minimul dintre distanțele Manhattan dintre C
și fiecare celulă care aparține insulei (distanța poate trece atât prin alte insule, cât și prin zone acoperite de apă). Distanța Manhattan dintre două celule aflate pe linia x1
și coloana y1
, respectiv pe linia x2
și coloana y2
, este definită ca |x1 – x2| + |y1 – y2|
, unde |x|
reprezintă valoarea absolută a lui x
.
Problema | Arhipelag | Operații I/O |
![]() arhipelag.in /arhipelag.out
|
---|---|---|---|
Limita timp | 0.3 secunde | Limita memorie |
Total: 32 MB
/
Stivă 8 MB
|
Id soluție | #41325316 | Utilizator | |
Fișier | arhipelag.cpp | Dimensiune | 3.02 KB |
Data încărcării | 19 Ianuarie 2023, 11:30 | Scor / rezultat | 5 puncte |
arhipelag.cpp: In function 'int main()': arhipelag.cpp:63:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] for(int j=0;j<ult[i].size();j++){ ^ arhipelag.cpp:69:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] for(int j=0;j<inceput[i].size();j++){ ^ arhipelag.cpp:86:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] for(int j=0;j<ult[i].size();j++){ ^ arhipelag.cpp:92:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] for(int j=0;j<inceput[i].size();j++){ ^
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 | Raspuns gresit. | 5 | 0 | ||
3 | 0.004 secunde | Raspuns gresit. | 10 | 0 | ||
4 | 0.004 secunde | Raspuns gresit. | 10 | 0 | ||
5 | 0.008 secunde | Raspuns gresit. | 10 | 0 | ||
6 | 0.008 secunde | Raspuns gresit. | 10 | 0 | ||
7 | 0.088 secunde | Raspuns gresit. | 5 | 0 | ||
8 | 0.088 secunde | Raspuns gresit. | 10 | 0 | ||
9 | 0.088 secunde | Raspuns gresit. | 10 | 0 | ||
10 | 0.088 secunde | Raspuns gresit. | 10 | 0 | ||
11 | 0.088 secunde | Raspuns gresit. | 10 | 0 | ||
Punctaj total | 5 |
www.pbinfo.ro permite evaluarea a două tipuri de probleme:
Problema Arhipelag 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ă.