Soluții trimise

Rezumat problemă

Primăria din Iași a hotărât să modernizeze șoselele din localitate. O șosea este o porțiune de drum care unește două intersecții. Firma constructoare a făcut un studiu pentru a determina costurile pentru fiecare șosea. Fondurile sunt limitate, astfel că în prima fază vor fi modernizate doar drumurile din apropierea Palas-ului, care se află la intersecția cu numărul 1. Mai precis: orice șosea modernizată trebuie sa fie cel puțin la fel de aproape de Palas ca orice șosea ce nu va fi modernizată.

Lungimea drumului dintre două intersecții a și b este numărul cel mai mic de intersecții ce trebuie parcurse pentru a ajunge de la a la b. Șoseaua (a, b) este mai aproape de Palas față de șoseaua (c, d) dacă lungimea drumului de la Palas până la cea mai apropiată intersecție dintre a și b este mai mică decât până la cea mai apropiată intersecție dintre c și d. Dacă lungimile drumurilor până la cele mai apropiate intersecții sunt egale, se compară lungimile drumurilor până la celelalte două intersecții. De exemplu dacă pentru șoselele (4, 7) și (3, 5) avem distanțele de la Palas până la intersecțiile: 3, 4, 5, 7 egale cu: 10, 10, 10, 11 în această ordine, atunci (3, 5) e mai aproape de Palas față de (4, 7) deoarece distanțele minime sunt ambele egale cu 10 dar distanța până la intersecția 3 este tot 10, mai mică față de distanța până la intersecția 7 care este 11. Dacă nu există cale de acces de la Palas la o intersecție a atunci șoselele legate de a nu vor fi modernizate.

Cunoscând: N – numărul de intersecții din oraș codificate prin numere naturale din mulțimea 1..N, M – numărul de șosele și șoselele împreună cu costul de modernizare, și F – fondurile de care dispune primăria, să se afle K – numărul maxim de șosele care pot fi modernizate.

Olimpiada Municipală Iași, clasele XI-XII

ID   Utilizator Problema Data încărcării Stare
Kristensen Chelcea Nectarie Ioan (Kristensen_Chelcea_Nectarie_Io) modernizare 02 Martie 2025, 21:11 Evaluare finalizată 0
Kristensen Chelcea Nectarie Ioan (Kristensen_Chelcea_Nectarie_Io) modernizare 02 Martie 2025, 21:10 Evaluare finalizată 100
Kristensen Chelcea Nectarie Ioan (Kristensen_Chelcea_Nectarie_Io) modernizare 02 Martie 2025, 21:10 Evaluare finalizată E.C
Kristensen Chelcea Nectarie Ioan (Kristensen_Chelcea_Nectarie_Io) modernizare 02 Martie 2025, 21:07 Evaluare finalizată 0
Kristensen Chelcea Nectarie Ioan (Kristensen_Chelcea_Nectarie_Io) modernizare 02 Martie 2025, 21:06 Evaluare finalizată E.C
Dumea Dragoș (DumeaDragos) modernizare 24 Februarie 2025, 16:56 Evaluare finalizată 70
Dumea Dragoș (DumeaDragos) modernizare 24 Februarie 2025, 16:54 Evaluare finalizată 70
Dumea Dragoș (DumeaDragos) modernizare 24 Februarie 2025, 16:53 Evaluare finalizată 70
Dumea Dragoș (DumeaDragos) modernizare 24 Februarie 2025, 16:51 Evaluare finalizată 40
Dumea Dragoș (DumeaDragos) modernizare 24 Februarie 2025, 16:50 Evaluare finalizată E.C
Dumea Dragoș (DumeaDragos) modernizare 24 Februarie 2025, 16:45 Evaluare finalizată 70
Dumea Dragoș (DumeaDragos) modernizare 24 Februarie 2025, 16:41 Evaluare finalizată 70
Dumea Dragoș (DumeaDragos) modernizare 24 Februarie 2025, 16:37 Evaluare finalizată 60
Dumea Dragoș (DumeaDragos) modernizare 24 Februarie 2025, 16:33 Evaluare finalizată 60
Dumea Dragoș (DumeaDragos) modernizare 24 Februarie 2025, 16:31 Evaluare finalizată 40
Dunel Stefan (Lithium_N) modernizare 18 Februarie 2025, 08:33 Evaluare finalizată 100
Mateiu Ianis Cristian Vasile (KRISTY) modernizare 16 Februarie 2025, 15:53 Evaluare finalizată 100
Mateiu Ianis Cristian Vasile (KRISTY) modernizare 16 Februarie 2025, 15:51 Evaluare finalizată 60
Mateiu Ianis Cristian Vasile (KRISTY) modernizare 16 Februarie 2025, 15:49 Evaluare finalizată 90
Morar Andrei HCC_cyber_gorilla (justmorii) modernizare 16 Februarie 2025, 09:48 Evaluare finalizată 100
Morar Andrei HCC_cyber_gorilla (justmorii) modernizare 16 Februarie 2025, 09:45 Evaluare finalizată 60
Morar Andrei HCC_cyber_gorilla (justmorii) modernizare 16 Februarie 2025, 09:41 Evaluare finalizată 50
Moldovan Laura (laura2019) modernizare 15 Februarie 2025, 19:41 Evaluare finalizată 100
Moldovan Laura (laura2019) modernizare 15 Februarie 2025, 19:37 Evaluare finalizată 50
Moldovan Laura (laura2019) modernizare 15 Februarie 2025, 19:32 Evaluare finalizată 50
Ilincă Andrei (Andrew_Waltz) modernizare 14 Februarie 2025, 22:50 Evaluare finalizată 60
Ilincă Andrei (Andrew_Waltz) modernizare 14 Februarie 2025, 22:49 Evaluare finalizată 0
Ilincă Andrei (Andrew_Waltz) modernizare 14 Februarie 2025, 22:49 Evaluare finalizată 0
Ilincă Andrei (Andrew_Waltz) modernizare 14 Februarie 2025, 22:49 Evaluare finalizată 0
Ilincă Andrei (Andrew_Waltz) modernizare 14 Februarie 2025, 22:46 Evaluare finalizată 60
Ilincă Andrei (Andrew_Waltz) modernizare 14 Februarie 2025, 22:44 Evaluare finalizată 60
Ilincă Andrei (Andrew_Waltz) modernizare 14 Februarie 2025, 22:43 Evaluare finalizată 60
Ilincă Andrei (Andrew_Waltz) modernizare 14 Februarie 2025, 22:36 Evaluare finalizată 40
Ilincă Andrei (Andrew_Waltz) modernizare 14 Februarie 2025, 22:35 Evaluare finalizată 40
Enache Raluca (EnacheMaricela) modernizare 14 Februarie 2025, 21:09 Evaluare finalizată 10
Enache Raluca (EnacheMaricela) modernizare 14 Februarie 2025, 21:04 Evaluare finalizată 0
Enache Raluca (EnacheMaricela) modernizare 14 Februarie 2025, 21:04 Evaluare finalizată 0
Enache Raluca (EnacheMaricela) modernizare 14 Februarie 2025, 21:03 Evaluare finalizată E.C
Laslau Antonio Luca (antonio2006) modernizare 13 Februarie 2025, 20:05 Evaluare finalizată 70
Laslau Antonio Luca (antonio2006) modernizare 13 Februarie 2025, 20:05 Evaluare finalizată 60
Laslau Antonio Luca (antonio2006) modernizare 13 Februarie 2025, 20:04 Evaluare finalizată E.C
Laslau Antonio Luca (antonio2006) modernizare 13 Februarie 2025, 20:04 Evaluare finalizată 60
Laslau Antonio Luca (antonio2006) modernizare 13 Februarie 2025, 20:03 Evaluare finalizată 60
Laslau Antonio Luca (antonio2006) modernizare 13 Februarie 2025, 19:52 Evaluare finalizată 70
Laslau Antonio Luca (antonio2006) modernizare 13 Februarie 2025, 19:36 Evaluare finalizată 40
Laslau Antonio Luca (antonio2006) modernizare 13 Februarie 2025, 19:34 Evaluare finalizată 0
Laslau Antonio Luca (antonio2006) modernizare 13 Februarie 2025, 19:24 Evaluare finalizată 40
Laslau Antonio Luca (antonio2006) modernizare 13 Februarie 2025, 19:23 Evaluare finalizată 30
Laslau Antonio Luca (antonio2006) modernizare 13 Februarie 2025, 19:20 Evaluare finalizată 40
Laslau Antonio Luca (antonio2006) modernizare 13 Februarie 2025, 19:19 Evaluare finalizată 40
Du-te sus!