|
|||
A hídn ember szeretne átkelni egy hídon éjszaka. Legfeljebb két ember kelhet át egyszerre, akiknél lennie kell egy elemlámpának. Az n embernél csak egy elemlámpa van, így egyfajta ingázást kell végezniük, hogy visszajuttassák az elemlámpát, és ezáltal további emberek is átkelhessenek. Az egyes személyek nem feltétlenül azonos sebességgel tudnak átkelni a hídon; egy csoport sebességét a lassabb tagjának a sebessége határozza meg. A feladatod, hogy meghatározz egy olyan stratégiát, amellyel az n ember minimális idő alatt juthat át a túloldalra. A bemenet specifikációjaA bemenet egy olyan sorral kezdődik, amely egyetlen pozitív egész számból, a tesztesetek számából áll. Ezt a sort egy üres sor követi, mint ahogy egy-egy üres sor van két egymást követő teszteset között is. Minden teszteset első sorában n értéke szerepel. Ezt n sor követi, amelyek az egyes emberek átkelési idejeit tartalmazzák. Legfeljebb 1000 ember lesz, és egyiküknek sem tart tovább 100 másodpercnél a hídon való átkelés. A kimenet specifikációjaAz egyes tesztesetekhez tartozó kimeneteknek az alábbi leírást kell követniük. Két egymást követő teszteset kimenetét egy-egy üres sorral kell elválasztani. Minden tesztesetre a kimenet első sorában az n ember átkeléséhez szükséges másodpercek számának kell szerepelnie. A további sorokba egy olyan stratégiát kell kiírni, amellyel ez az idő érhető el. Mindegyik további sornak egy vagy két egész számot kell tartalmaznia, amelyek a következőnek átkelő személyt vagy személyeket adják meg. (Az egyes személyeket a bemeneten megadott átkelési idejükkel azonosítjuk. Bár több embernek is lehet ugyanaz az átkelési ideje, ennek a kétértelműségnek nincs következménye.) Ne feledjük, hogy az átkelések váltakozó irányúak, mivel mindig vissza kell juttatni az elemlámpát, hogy mások is átkelhessenek. Ha több stratégiával is elérhető a minimális idő, bármelyik megadható. Példa bemenet
A példa bemenethez tartozó kimenet
|
|||
| Debreceni Egyetem, Informatikai Kar, v. 2019.03.01. |