#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 | #52925451 | Utilizator | |
Fișier | metrou.cpp | Dimensiune | 5.08 KB |
Data încărcării | 13 Octombrie 2024, 11:43 | Scor / rezultat | 100 puncte |
metrou.cpp: In function 'void newChain(int)': metrou.cpp:63:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] for(int j=0; j<v[i].size(); ++j) ^ metrou.cpp:89:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] for(int j=0; j<v[x].size(); ++j) ^ metrou.cpp: In function 'int solveChain()': metrou.cpp:134:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] for(int i=0; i<v[x].size(); ++i) ^ metrou.cpp: In function 'int solve()': metrou.cpp:175:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] for(int j=0; j<v[i].size(); ++j) ^ metrou.cpp:194:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] for(int j=0; j<v[nod].size(); ++j) ^ metrou.cpp: In function 'int main()': metrou.cpp:234:38: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result] freopen("metrou.in", "r", stdin); ^ metrou.cpp:235:40: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result] freopen("metrou.out", "w", stdout); ^ metrou.cpp:237:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result] scanf("%d%d", &n, &m); ^ metrou.cpp:239:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result] scanf("%d", &p[i]); ^ metrou.cpp:243:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result] scanf("%d%d", &a, &b); ^
Test | Timp | Mesaj evaluare | Scor posibil | Scor obținut | ||
---|---|---|---|---|---|---|
0 | 0.076 secunde | OK. | 10 | 10 | ||
1 | 0 secunde | OK. | 10 | 10 | ||
2 | 0 secunde | OK. | 10 | 10 | ||
3 | 0 secunde | OK. | 10 | 10 | ||
4 | 0 secunde | OK. | 10 | 10 | ||
5 | 0.008 secunde | OK. | 10 | 10 | ||
6 | 0.008 secunde | OK. | 10 | 10 | ||
7 | 0.028 secunde | OK. | 10 | 10 | ||
8 | 0.044 secunde | OK. | 10 | 10 | ||
9 | 0.076 secunde | OK. | 10 | 10 | ||
Punctaj total | 100 |
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ă.