Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | taxi2.in, taxi2.out | Sursă | Algoritmiada 2016 Runda 1 Seniori |
| Autor | Adrian Budau, Mihai Calancea | Adăugată de |  Mihai Calancea •klamathix |
| Timp execuţie pe test | 0.4 sec | Limită de memorie | 54096 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Taxi2
Ne aflăm în anul 2050, iar metroul din Drumul Taberei a fost inaugurat recent. Firmele de Taxi consideră că viaţa bucureştenilor a devenit acum prea bună, aşa că au hotărât să-i pedepsească mărind costurile unei călătorii cu taxi-ul. Mai exact, un client care face o comandă telefonică trebuie acum să plătească taxi-ul şi pentru distanţa pe care acesta o parcurge de la locaţia sa iniţială până la adresa clientului. Mai mult, dacă la un moment dat există M comenzi telefonice care trebuie satisfăcute şi M taximetrişti liberi, dispeceratul va cupla taximetriştii cu comenzile astfel încât distanţa totală parcursă de către cei M taximetrişti până la adresele corespunzătoare să fie maximă. Noi dorim să studiem costurile unui asemenea cuplaj, în funcţie de poziţiile iniţiale ale taximetriştilor şi ale clienţilor.
Bucureştiul a devenit între timp un arbore neorientat cu N noduri şi distanţe pozitive pe muchii (o transformare tragică, dar care nu a înrăutăţit neaparat traficul). Fiecare dintre cei M taximetrişti se poate afla în oricare din cele N noduri. Acelaşi lucru este valabil pentru fiecare dintre cei M clienţi. Un nod poate găzdui un număr nelimitat de taximetrişti şi/sau clienţi. Astfel, există în total N2M configuraţii diferite ale poziţiilor taxi/client. Dacă un taximetrist care se află în nodul X este cuplat cu o comandă din nodul Y, costul călătoriei sale va fi egal cu distanţa dintre nodurile X şi Y. Întrebarea noastră este următoarea: Dacă S ar fi suma cuplajelor de cost maxim pentru toate cele N2M configuraţii posibile, ce valoare ar avea S modulo 109 + 7?
Date de intrare
Fişierul de intrare taxi2.in ...
Date de ieşire
În fişierul de ieşire taxi2.out ...
Restricţii
- ... ≤ ... ≤ ...
Exemplu
| taxi2.in | taxi2.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
