A kétségbeesett villanyszerelő

A Cseh Műszaki Egyetem nemcsak mérnök informatikusokat, hanem villanyszerelőket is képez, akik néha kihívást jelentő problémákkal találják szembe magukat.

Egy villanyszerelő azt a megbízást kapta, hogy egy nagyon magas épületbe új elektromos kábelezést vezessen be. Mielőtt belefogna a munkájába, meg kell állapítania a régi kábelek állapotát. W kábelvégződés van a földszinten, és másik W a 42. emeleten. A villanyszerelő biztosan tudja, hogy az alsó végződések mindegyike pontosan egy felső végződéshez csatlakozik. Nincs azonban semmilyen jelzés, így nincs információja arról, hogy melyik kábel melyik.

A legfőbb probléma az, hogy a liftek még nem működnek (hiszen még nincsenek rákapcsolva az elektromos hálózatra). Így aztán mindenképpen jó lenne a felfelé és lefelé megtett utak számát minimalizálnunk.

A villanyszerelő rendelkezésére állnak olyan csatlakozók, amelyekkel tetszőleges számú kábelvégződést lehet összekapcsolni (természetesen ugyanazon az emeleten). Ezután elsétálhat a kábelek másik végéhez, és kimérheti, hogy mely kábelek vannak összekötve. Ha például a villanyszerelő csak két kábelt köt össze, akkor könnyedén meghatározható ez a pár a túlvégen. A két összekötött kábelt azonban sajnos lehetetlen megkülönböztetni egymástól.

A feladatod, hogy írj egy programot, amely meghatározza a legjobb módját az összes kábel megjelölésének. Megengedett, hogy egyszerre tetszőleges számú kábel legyen összekötve egymással, és hogy tetszőleges számú összekötött kábelcsoport legyen (mindig van elég csatlakozó). A villanyszerelő tetszőleges számú mérést végezhet minden emeleten. Végül a következő feltételeknek kell megfelelni:

1. A villanyszerelő a munka végén visszatér a földszintre.
2. A kábelek alsó végződéseinek mindegyike megjelölésre kerül különböző számokkal 1-től W-ig.
3. A felső végződések mindegyike megjelölésre kerül különböző számokkal 1-től W-ig.
4. Minden kábel ugyanazzal a számmal rendelkezik mindkét végén.

A bemenet specifikációja

A bemenet számos tesztesetet tartalmaz. Minden teszteset egyetlen sorból áll, amelyben a W egész szám, a kábelek száma szerepel (1 ≤ W ≤ 200). A bemenetet egy nullát tartalmazó sor zárja.

A kimenet specifikációja

A programodnak minden tesztesetre egyetlen sort kell a kimenetre írnia, amely az „Electrician needs X trips.” mondatot tartalmazza, ahol X azon alkalmak lehető legkisebb száma, ahányszor a villanyszerelőnek fel kell másznia a 42. emeletre, majd vissza kell onnan térnie.

Ha egyáltalán nem lehetséges a kábelek megjelölése, akkor ehelyett a „Bad luck!” mondatot kell kiírni.

Példa bemenet

1. 2
2. 3
3. 0

letöltés szöveges állományként

A példa bemenethez tartozó kimenet

1. Bad luck!
2. Electrician needs 1 trips.

letöltés szöveges állományként