#1200
Mei și Satsuki s-au întors de curând în casa de vacanță a familiei lor. Această casă este formată din N
camere, unite între ele prin N-1
culoare, astfel încât să se poată ajunge din orice cameră în orice altă cameră. Intrarea în casă se face prin camera 1
. Deoarece casa n-a fost locuită timp de mai multe luni, în fiecare cameră i
s-au stabilit s[i]
spiriduși de praf.
Cele două fete doresc să-și amenajeze un spațiu de joacă întins pe mai multe camere. Ele vor să stabilească două camere a
și b
(nu neapărat distincte), astfel încât drumul cel mai scurt de la intrarea în casă până în camera b
trece prin camera a
. Fetele vor merge apoi din camera a
în camera b
pe drumul cel mai scurt (fără a trece de două ori prin aceeași cameră), gonind spiridușii de praf aflați în fiecare cameră prin care trec, inclusiv pe cei din camerele a
și b
. După ce fetele ajung în camera b
, ele consideră că toate camerele din care au gonit spiridușii de praf au fost alese pentru spațiul de joacă.
Fetele au stabilit pentru fiecare cameră i
un coeficient p[i]
care reprezintă cât de plăcută ar fi camera i
pentru spațiul lor de joacă. În plus, ele au convenit că nu vor goni în total mai mult de C
spiriduși ai prafului din camerele prin care trec.
Cunoscând valorile lui N
și C
, numărul de spiriduși ai prafului s[i]
, coeficienții p[i]
pentru fiecare cameră i
, cât și modul în care sunt unite camerele prin culoare, să se determine suma maximă a coeficienților p
ai camerelor alese pentru un spațiu de joacă ce respectă condițiile impuse de Mei și Satsuki.
ONI 2015, Clasele XI-XII
ID | Utilizator | Problema | Data încărcării | Stare | ||
---|---|---|---|---|---|---|
Spiridusi | 10 Octombrie 2022, 20:18 | Evaluare finalizată | 100 |