#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 | #8161736 | Utilizator | |
Fișier | metrou.c | Dimensiune | 4.12 KB |
Data încărcării | 02 Februarie 2018, 15:29 | Scor / rezultat | 0 puncte |
metrou.c: In function 'main': metrou.c:176:15: warning: unused variable 'j' [-Wunused-variable] int n, i, j; ^ metrou.c:174:21: warning: unused variable 'C' [-Wunused-variable] GRAF ** graf, * C; ^ metrou.c: In function 'readValues': metrou.c:56:11: warning: ignoring return value of 'fscanf', declared with attribute warn_unused_result [-Wunused-result] fscanf( entryValue, "%d %d", &(*n), &m ); ^ metrou.c:60:15: warning: ignoring return value of 'fscanf', declared with attribute warn_unused_result [-Wunused-result] fscanf( entryValue, "%d", &vec[i].profit ); ^ metrou.c:66:15: warning: ignoring return value of 'fscanf', declared with attribute warn_unused_result [-Wunused-result] fscanf( entryValue, "%d %d", &i, &j); ^ metrou.c: In function 'main': metrou.c:191:15: warning: 'ok' may be used uninitialized in this function [-Wmaybe-uninitialized] if( ok ) ^
Test | Timp | Mesaj evaluare | Scor posibil | Scor obținut | ||
---|---|---|---|---|---|---|
0 | Depășit | Limita de timp depășită | 10 | 0 | ||
1 | Depășit | Limita de timp depășită | 10 | 0 | ||
2 | Depășit | Limita de timp depășită | 10 | 0 | ||
3 | Depășit | Limita de timp depășită | 10 | 0 | ||
4 | Depășit | Limita de timp depășită | 10 | 0 | ||
5 | Depășit | Limita de timp depășită | 10 | 0 | ||
6 | Depășit | Limita de timp depășită | 10 | 0 | ||
7 | Depășit | Limita de timp depășită | 10 | 0 | ||
8 | Depășit | Limita de timp depășită | 10 | 0 | ||
9 | Depășit | Limita de timp depășită | 10 | 0 | ||
Punctaj total | 0 |
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ă.