Mai mulți elfi sunt aranjați într-un
șir. Liderul lor va fi ales de un elf experimentat
printr-o procedură ciudată.
Un elf experimentat se află în fața lor. El va alege ca, la fiecare comandă a sa, jumătate dintre elfi (cea din stânga sau cea din dreapta) să părăsească șirul. Dacă numărul elfilor este impar, atunci și elful din mijlocul șirului va părăsi șirul. În momentul în care rămâne un singur elf, acesta va deveni lider. Elful experimentat dorește să știe dacă există o secvență de comenzi care va duce la alegerea unui anumit elf ca lider al grupului, precum și care este succesiunea de comenzi necesară pentru atingerea acestui scop. Mai mult, el dorește să știe care sunt elfii care nu au șansa de a ajunge lideri, indiferent de succesiunea de comenzi aleasă. Elfii din șir sunt numerotați de la 1 la n (numărul total al elfilor din șir) începând cu partea stângă.
Fișierul de intrare INPUT.TXT conțține
pe prima linie numărul n al elfilor
din șir. Cea de-a doua linie conține
numărul de ordine al elfului despre
care se dorește a se ști dacă poate
ajunge sau nu lider.
Fișierul de ieșire OUTPUT.TXT trebuie
să conțină pe prima linie numărul
k al elfilor care nu pot ajunge lideri.
Fiecare dintre următoarele k linii va conține câte un număr care va reprezenta numărul de ordine al unui elf care nu poate deveni lider. Următoarea linie a fișierului va conține cuvântul DA dacă elful specificat poate ajunge lider sau cuvântul NU în caz contrar. În cazul în care elful poate ajunge lider, pe cea de-a doua linie va fi descrisă o succesiune de comenzi care va duce la alegerea elfului respectiv. O comandă de "eliminare" a jumătății stângi va fi notată prin S, iar o comandă de "eliminare" a jumătății drepte va fi notată prin D. Nu vor exista spații între caracterele care descriu comenzile.
INPUT.TXT
7 3 OUTPUT.TXT 3 2 4 6 DA DS
|