Regular Words
Time Limit : 2000/1000ms (Java/Other) Memory Limit : 65536/32768K (Java/Other)
Total Submission(s) : 0 Accepted Submission(s) : 0
Problem Description
Consider words of length 3n over alphabet {A, B, C} . Denote the number of occurences of A in a word a as A(a) , analogously let the number of occurences of B be denoted as B(a), and the number of occurenced of C as C(a) . <br><br>Let us call the word w regular if the following conditions are satisfied: <br><br>A(w)=B(w)=C(w) ; <br>if c is a prefix of w , then A(c)>= B(c) >= C(c) . <br>For example, if n = 2 there are 5 regular words: AABBCC , AABCBC , ABABCC , ABACBC and ABCABC . <br><br>Regular words in some sense generalize regular brackets sequences (if we consider two-letter alphabet and put similar conditions on regular words, they represent regular brackets sequences). <br><br>Given n , find the number of regular words.
Input
There are mutiple cases in the input file. <br><br>Each case contains n (0 <= n <= 60 ). <br><br>There is an empty line after each case.
Output
Output the number of regular words of length 3n . <br><br>There should be am empty line after each case.
Sample Input
2<br><br>3<br>
Sample Output
5<br><br>42<br>
Source
Andrew Stankevich's Contest #10