Lista de probleme 1
Filtrare
#4565
Amazon
România este formată din N orașe conectate între ele, existând un traseu unic între oricare două orașe. Un traseu este o secvență de drumuri care conectează două orașe, astfel încât niciun drum nu se repetă. În total, există N−1 drumuri bidirecționale care conectează orașele.
Fiecare drum are și un cost asociat. Echipa lui Jeffrey a creat o lista de M perechi de orașe între care se va circula foarte des pentru livrarea coletelor. Definim costul unei perechi de orașe (x, y) ca fiind suma costurilor drumurilor din traseul de la orașul x la orașul y. De asemenea, definim costul total ca fiind suma tuturor costurilor celor M perechi de orașe date.
Jeffrey poate să aplice următorul tip de operație: selectează un drum cu un cost strict pozitiv și îi scade costul cu 1. Din motive de “frugality”, această operație poate fi aplicată de cel mult K ori, unde K este un număr natural.
Se cere să găsiți costul total minim ce poate fi obținut, după aplicarea de cel mult K ori a operației menționate mai sus.
Concursul Interjudețean de Matematică și Informatică Grigore Moisil, 2023
- Fișiere
-
Moldovan Robert (use KN) (moldovan_robert_lol)
- Robert-Raul Borcani, Octavian Trifan, Daniel Todașcă
- concurs
- Clasa 11 Teoria Grafurilor Arbori cu rădăcină
- Lowest Common Ancestor
- Smenul lui Mars (Difference Arrays)
- Heavy-Light Decomposition