
ZOJ Problem Set  2711
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) . Let us call the word w regular if the following conditions are satisfied:
Regular words in some sense generalize regular brackets sequences (if we consider twoletter alphabet and put similar conditions on regular words, they represent regular brackets sequences). Given n , find the number of regular words. Input There are mutiple cases in the input file. Each case contains n (0 <= n <= 60 ). There is an empty line after each case. Output Output the number of regular words of length 3n . There should be am empty line after each case.Sample Input 2 3 Sample Output 5 42 Source: Andrew Stankevich's Contest #10 