Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | fenrir.in, fenrir.out | Sursă | Algoritmiada 2015 Runda 1 |
| Autor | Mihai Calancea | Adăugată de |  Mihai Calancea •klamathix |
| Timp execuţie pe test | 0.125 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Fenrir
Pe-un picior de plai,
Pe-o gură de rai,
Iată vin în cale,
Se cobor la vale,
Douăzeci de turme de miei,
Cu douăzeci de ciobănei.
În această extindere a baladei Mioriţa ciobănaşii noştri se confruntă cu Fenrir, un personaj al mitologiei nordice, care după o uşoară confuzie geografică a ajuns, şi el, pe acelaşi picior de plai. Mai mult, acesta urmează să atace turmele la lăsarea serii. Plictisiţi de atitudinea ciobănaşului moldovean, care începuse din nou să-şi plănuiască funeraliile, ceilalţi au hotărât să adopte o poziţie mai pragmatică şi să înfrunte problema. Ei au concluzionat că problema se poate formula astfel:
Cei douăzeci de ciobănaşi au douăzeci de stâne, fiecare stână adăpostind o turmă de miei. Aceştia pot construi cărări directe, bidirecţionale, între oricare două stâne. Ei ştiu că Fenrir va lovi o singură dată, la lăsarea serii, trecând prin fiecare stână maxim o dată (fiind un animal mitologic relativ ocupat) şi nimicind turmele din stânele respective. Cunoscând acest lucru ciobănaşii vor să construiască o reţea de cărări care să le asigure o bună comunicare pe parcursul atacului, dar în acelaşi timp să nu uşureze prea mult deplasarea lui Fenrir. Mai exact, reţeaua de cărări trebuie să respecte următoarele proprietăţi
1. Trebuie să nu existe un drum format din cărări care să viziteze toate cele 20 de stâne exact o dată. Acest lucru ar garanta că Fenrir va consuma toate cele 20 de turme, ceea ce ar fi dezastruos pentru ciobănaşi. Protejând măcar o turmă pe parcursul atacului, acestia ar putea repopula şi celelalte stâne.
2. Trebuie ca oricare două stâne să fie legate, direct sau indirect, prin cărări. Mai mult, dacă ar fi să numărăm stânele vecine pentru fiecare stână, minimul acestor valori ar trebui să fie cât mai mare.
h2. Date de intrare
Fişierul de intrare fenrir.in ...
Date de ieşire
În fişierul de ieşire fenrir.out ...
Restricţii
- ... ≤ ... ≤ ...
Exemplu
| fenrir.in | fenrir.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
