Stackol | Topcoder Archive

Problem Statement

Stackol is a programming language for printing strings. A program is a string containing 'A', 'B' or 'C' as characters (quotes for clarity). A program is evaluated from i = 0 to length(program)-1 using the following rules:

For i = 0 to length(program)-1 :
    If (i==0) or (program[i-1]!='B') then
        push program[i] to the top of stack1.
    Else
        push program[i] to the top of stack2.
    EndIf
    If (program[i]=='C') then 
        printAndEmptyStack(stack1)
        printAndEmptyStack(stack2)
    EndIf
EndFor

printAndEmptyStack(stack) is defined as follows:

While (stack is not empty):
    If (top character in stack) is 'A' or 'B' then
        Print (top character in stack)
    EndIf
    Remove the top character from the stack.
EndWhile

We will consider a valid program to be one that ends with 'C'. We are interested in counting the total number of valid programs that can generate a given output string that contains only 'A' or 'B' characters. Since we would also like the program lengths to be reasonably small we will count only the programs that contain at most k 'C' characters.

The output is given in fragments described by String[] outputFragments. In order to generate the output, concatenate the elements of outputFragments. Return the total number of programs that can generate the given output using at most k 'C' characters modulo 1000000007.

Definition

Class:: Stackol
Method:: countPrograms
Parameters:: String[], int
Returns:: int
Method signature:: int countPrograms(String[] outputFragments, int k)
(be sure your method is public)

Constraints

The total number of characters in outputFragments will be between 1 and 2500, inclusive.
outputFragments will contain between 1 and 50 elements, inclusive.
Each element of outputFragments will contain between 1 and 50 characters, inclusive.
Each element of outputFragments will contain only 'A' or 'B' characters.
k will be between 1 and 10, inclusive.

Examples

```
{"A"}
```
```
2
```
```
Returns: 3
```
The 3 programs that produce "A" as output are: CAC ACC AC
```
{"AAAA","BABA"}
```
```
1
```
```
Returns: 0
```
There is no program that produces the given output.
```
{"AB"}
```
```
2
```
```
Returns: 1
```
The only possible program that can generate "AB" using at most two 'C' characters is: ACBC.

{"AAABABABAABA", "AA", "BBAB"}

Returns: 94

```
{"AAAAAAAAAAAA","B"}
```
```
4
```
```
Returns: 120
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.