4. Potyczki Informatyczne Nowej Generacji

Zadanie eliminacyjne w konkursie WIPING4 organizowanym przez
Wydział Informatyki Zachodniopomorskiego Uniwersytetu Technologicznego w Szczecinie

Słowa Fibonacciego

Zapewne zetknąłeś się już nieraz z pojęciem ciągu Fibonacciego. Dzisiaj pokażemy ci, czym są słowa Fibonacciego - to ciągi znaków, budowane według rekurencyjnej zasady, niesłychanie podobnej do tej, jakiej używa się w ciągu. Różnica jest taka, że zamiast dodawania liczb używa się łączenia (kontatenacji) łańcuchów, a pierwsze dwa słowa (nazywane tutaj X i Y) są parametrami algorytmu.

Postać n-tego słowa Fibonacciego określa następująca reguła:

Operator ⋅ oznacza tu konkatenację łańcuchów.

Innymi słowy, n-te słowo Fibonacciego (dla n > 1) powstaje z konkatenacji dwóch słów poprzedzających.

Twoim zadaniem jest napisanie programu, który będzie generował wybrane słowa Fibonacciego na podstawie ciągów znaków określających dwa pierwsze słowa, jednak wyprowadzeniu na standardowe wyjście podlegać będą jednak tylko te słowa, których numer jest potęgą trzeciej danej programu i który to numer nie jest większy niż dana czwarta.

Wejś›cie

• cztery wiersze tekstu zawierające kolejno:
   
  • X – zerowe słowo Fibonacciego
  • Y – pierwsze słowo Fibonacciego
  •  n – całkowita podstawa potęgi (n > 0)
    
  • m – maksymalny numer słowa (0 < m < 100)
    

Wyjś›cie

• k wierszy zawierających kolejne słowa Fibonacciego, wygenerowane według założeń zadania

Przykł‚ad

Wejś›cie: 

ab
cd
2
10

Wyjście:

cd
cdab
cdabcdcdab
cdabcdcdabcdabcdcdabcdcdabcdabcdcdabcdabcdcdabcdcdabcdabcdcdabcdcdab

Informacje dodatkowe

• program zostanie uruchomiony 10 razy dla różnych zestawów danych
  

• każde poprawne rozwią…zanie daje 10% punktacji zadania
• zadanie ma wartość‡ punktową… 2,0