Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | spiridusi.in, spiridusi.out | Sursă | ONI 2015 Clasele 11-12 |
| Autor | Vlad Gavrila | Adăugată de |  Andrei Stanciu •assa98 |
| Timp execuţie pe test | 0.2 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Spiridusi
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.
Cerinta
Date de intrare
Fişierul de intrare spiridusi.in ...
Date de ieşire
În fişierul de ieşire spiridusi.out ...
Restricţii
- ... ≤ ... ≤ ...
Exemplu
| spiridusi.in | spiridusi.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
