Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | pitici.in, pitici.out | Sursă | lot 2006 |
| Autor | Dan-Ionut Fechete | Adăugată de |  Airinei Adrian •astronomy |
| Timp execuţie pe test | 0.225 sec | Limită de memorie | 20096 kbytes |
| Scorul tău | N/A | Dificultate |   4/5 |
Vezi solutiile trimise | Statistici
Pitici
In varful muntelui Acrom traiesc pe timpul verii K pitici, numerotati de la 1 la K. Pe munte exista N cabane, aflate la altitudini diferite, legate intre ele de M poteci. Cabana piticilor este numerotata cu 1, iar cabana de la poalele muntelui cu N. Fiindca iarna este prea frig, piticii se muta în cabana de la poalele muntelui, unde este mai cald. Piticii sunt disciplinati si coboara de pe munte in ordinea crescatoare a numerelor lor. Pentru a nu fi acuzati de lipsa de personalitate, fiecare pitic alege drumul cel mai scurt pana jos, drum diferit de fiecare dintre drumurile alese de piticii ce au coborat inaintea lui. Un drum al unui pitic este o succesiune de cabane x1 ×2 ... xp cu proprietatea că x1=1, xp=N si între oricare doua cabane consecutive pe drum xi ÅŸi xi+1 există o potecă ce merge in vale (adica altitudinea cabanei xi este mai mare decât altitudinea cabanei xi+1). Doua drumuri sunt diferite daca exista cel putin o cabana ce apartine unuia dintre drumuri si nu apartine celuilalt. Lungimea unui drum este suma lungimilor potecilor ce leaga cabanele situate pe acest drum.
Date de intrare
...
Date de iesire
...
Restrictii
- ... ≤ ... ≤ ...
Exemplu
| pitici.in | pitici.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicatie
...
