50136. Build Strings

I'm a slow walker, but I never walk backwards.

Task Description

Write a program to generate strings according to three constraints. First the first letter of this string must be a given letter $C$. Next the length of the string must be a given $L$. Finally, the distance between a letter and the letter after it must be no more than $K$. For example, if $C$ is 'a' and $K$ is 4, then the second letter of this string can only be one from the set {'b', 'c', 'd', 'e'}. Note that the distance between the letters is circular. That is if $C$ is 'w' and $K$ is 5, the second letter be one from {'x', 'y', 'z', 'a', 'b'} in a wrapped around manner. The same rule applied to every letter in the string, e.g., between the second and the third letter etc.

Write a program to generate strings recursively, and print the first $N$ strings in dictionary order. All letters are in lowercase.

Input Format

The input contains only one test case. There are one character $C$ and three integers $K$, $L$, and $N$ in one line. $C$ is the leading character of strings, $K$ is the maximum distance between consecutive letters, $L$ is the length of the strings, and $N$ is the number of strings you need to print.

  • $0 \lt K \lt 26$
  • $0 \lt L \lt 1024$
  • $0 \lt N \leq K^{L-1}$

Output Format

Output contains $N$ lines. There is a string in each line.

Subtasks

  • 10 points: $K$ is 1, and there will be no wrapped around manner. $N$ is so large that you need to print all possible strings.
  • 30 points: There will be no wrapped around manner. $N$ is so large that you need to print all possible strings.
  • 30 points: There will be no wrapped around manner, but you need to print only the first $N$ strings.
  • 30 points: There could be wrapped around manner, and you need to print only the first $N$ strings.

Sample Input 1

f 1 8 1

Sample Output 1

fghijklm

Sample Input 2

m 2 4 8

Sample Output 2

mnop
mnoq
mnpq
mnpr
mopq
mopr
moqr
moqs

Sample Input 3

t 3 3 5

Sample Output 3

tuv
tuw
tux
tvw
tvx

Sample Input 4

w 4 3 7

Sample Output 4

wab
wac
wad
wae
wxa
wxb
wxy

Discussion