#1199
Metrou
Această problemă este dedicată celor care așteaptă metroul cu cea mai mare ardoare: locuitorii din Drumul Taberei.
Se dă planul unei rețele de metrou cu N
stații și M
tuneluri bidirecționale între stații. Două stații de metrou se numesc vecine dacă există un tunel între ele în acest plan. Fiecare stație i
are asociat un profit p[i]
dat.
Henry a fost recent promovat dintr-un post de angajat al departamentului de curățenie pe postul de project manager al firmei. Deoarece nu există fonduri pentru construirea întregii rețele de metrou, Henry trebuie să aleagă o submulțime de stații care vor fi construite, astfel încât oricare două stații alese să nu fie vecine în planul inițial. Pentru a-și păstra poziția în companie, suma profiturilor stațiilor alese în această submulțime trebuie să fie maximă.
Dându-se N
, M
, profiturile aduse de fiecare din cele N
stații și planul inițial al rețelei, să se determine suma maximă a profiturilor stațiilor pe care le poate alege Henry astfel încât oricare două stații alese să nu fie vecine în planul inițial.
ONI 2015, Clasele XI-XII
Problema | Metrou | Operații I/O |
metrou.in /metrou.out
|
---|---|---|---|
Limita timp | 0.5 secunde | Limita memorie |
Total: 64 MB
/
Stivă 16 MB
|
Id soluție | #52653010 | Utilizator | |
Fișier | metrou.cpp | Dimensiune | 869 B |
Data încărcării | 06 Octombrie 2024, 02:12 | Scor / rezultat | 30 puncte |
Test | Timp | Mesaj evaluare | Scor posibil | Scor obținut | ||
---|---|---|---|---|---|---|
0 | 0.044 secunde | Raspuns gresit. | 10 | 0 | ||
1 | 0 secunde | OK. | 10 | 10 | ||
2 | 0 secunde | OK. | 10 | 10 | ||
3 | 0 secunde | OK. | 10 | 10 | ||
4 | 0 secunde | Raspuns gresit. | 10 | 0 | ||
5 | 0.004 secunde | Raspuns gresit. | 10 | 0 | ||
6 | 0.004 secunde | Raspuns gresit. | 10 | 0 | ||
7 | 0.02 secunde | Raspuns gresit. | 10 | 0 | ||
8 | 0.02 secunde | Raspuns gresit. | 10 | 0 | ||
9 | 0.044 secunde | Raspuns gresit. | 10 | 0 | ||
Punctaj total | 30 |
www.pbinfo.ro permite evaluarea a două tipuri de probleme:
Problema Metrou 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ă.