Detalii evaluare #48765845

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

Detalii

Problema modernizare Operații I/O modernizare.in/modernizare.out
Limita timp 2 secunde Limita memorie Total: 16 MB / Stivă 1 MB
Id soluție #48765845 Utilizator Benchea Matei (matei__b)
Fișier modernizare.cpp Dimensiune 1.78 KB
Data încărcării 05 Februarie 2024, 00:00 Scor / rezultat 50 puncte

Evaluare


Mesaj compilare

modernizare.cpp:6:22: warning: missing terminating ' character [enabled by default]
 #define mod 1'000'000'007

                      ^

Rezultat evaluare

Test Timp Mesaj evaluare Scor posibil Scor obținut
0 0 secunde OK. 10 10 Exemplu
1 0 secunde Raspuns gresit. 10 0
2 0 secunde OK. 10 10
3 0.004 secunde Raspuns gresit. 10 0
4 0.004 secunde Raspuns gresit. 10 0
5 0.06 secunde OK. 10 10
6 0.052 secunde Raspuns gresit. 10 0
7 0 secunde Raspuns gresit. 10 0
8 0 secunde OK. 10 10
9 0.028 secunde OK. 10 10
Punctaj total 50

Cum funcționează evaluarea?

www.pbinfo.ro permite evaluarea a două tipuri de probleme:

  • probleme la care rezolvarea presupune scrierea unui program complet
  • probleme la care rezolvarea presupune scrierea unei secvențe de program - câteva instrucțiuni, o listă de declarații, una sau mai multe funcții, etc.

Problema modernizare face parte din prima categorie. Soluția propusă de tine va fi evaluată astfel:

  • Programul sursă este compilat folosind compilatorul corespunzător. Dacă în urma compilării se obțin erori sau avertismente, acestea sunt afișate în această pagină.
  • Dacă programul a fost compilat, executabilul obținut va fi rulat, furnizându-i-se unul sau mai multe seturi de date de intrare, în concordanță cu restricțiile specifice problemei. Pentru fiecare set de date se obține un anumit punctaj, în raport cu corectitudinea soluției tale.

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ă.