ZOJ Problem Set - 1819
The rhyme scheme for a poem (or stanza of a longer poem) tells which lines of the poem rhyme with which other lines. For example, a limerick such as
If computers that you build are quantum
Has a rhyme scheme of aabba, indicating that the first, second and fifth lines rhyme and the third and fourth lines rhyme.
For a poem or stanza of four lines, there are 15 possible rhyme schemes:
aaaa, aaab, aaba, aabb, aabc, abaa, abab, abac, abba, abbb, abbc, abca, a bcb, abcc, and abcd.
Write a program to compute the number of rhyme schemes for a poem or stanza of N lines where N is an input value.
Input will consist of a sequence of integers N (<= 50), one per line, ending with a 0 (zero) to indicate the end of the data. N is the number of lines in a poem.
For each input integer N, your program should output the value of N, followed by a space, followed by the number of rhyme schemes for a poem with N lines.
Source: Greater New York 2003