#2893
modernizare
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
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 | #48765905 | Utilizator | |
Fișier | modernizare.cpp | Dimensiune | 1.84 KB |
Data încărcării | 05 Februarie 2024, 00:07 | Scor / rezultat | Eroare de compilare |
modernizare.cpp:6:22: warning: missing terminating ' character [enabled by default] #define mod 1'000'000'007 ^ In file included from /usr/include/c++/4.8/algorithm:62:0, from /usr/include/i386-linux-gnu/c++/4.8/bits/stdc++.h:64, from modernizare.cpp:1: /usr/include/c++/4.8/bits/stl_algo.h: In instantiation of '_RandomAccessIterator std::__unguarded_partition(_RandomAccessIterator, _RandomAccessIterator, const _Tp&) [with _RandomAccessIterator = muchie*; _Tp = muchie]': /usr/include/c++/4.8/bits/stl_algo.h:2283:70: required from '_RandomAccessIterator std::__unguarded_partition_pivot(_RandomAccessIterator, _RandomAccessIterator) [with _RandomAccessIterator = muchie*]' /usr/include/c++/4.8/bits/stl_algo.h:2315:54: required from 'void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size) [with _RandomAccessIterator = muchie*; _Size = int]' /usr/include/c++/4.8/bits/stl_algo.h:5461:36: required from 'void std::sort(_RAIter, _RAIter) [with _RAIter = muchie*]' modernizare.cpp:89:19: required from here /usr/include/c++/4.8/bits/stl_algo.h:2245:19: error: passing 'const muchie' as 'this' argument of 'bool muchie::operator<(const muchie&)' discards qualifiers [-fpermissive] while (__pivot < *__last) ^
www.pbinfo.ro permite evaluarea a două tipuri de probleme:
Problema modernizare 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ă.