Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学《ACM-ICPC竞赛训练》暑期课面向全球招生。容量有限,报名从速!
Language:
Rhyme Schemes
Time Limit: 1000MSMemory Limit: 10000K
Total Submissions: 1815Accepted: 1008Special Judge

Description

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
Then spies of all factions will want 'em
Our codes will all fail
And they'll read our email
`Til we've crypto that's quantum and daunt 'em

Jennifer and Peter Shor (http://www.research.att.com/~shor/notapoet.html)

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

Input will consist of a sequence of integers N, one per line, ending with a 0 (zero) to indicate the end of the data. N is the number of lines in a poem.

Output

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 as a decimal integer with at least 12 correct significant digits (use double precision floating point for your computations).

Sample Input

1
2
3
4
20
30
10
0

Sample Output

1 1
2 2
3 5
4 15
20 51724158235372
30 846749014511809120000000
10 115975

Source

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator