2005 ASIA PROGRAMMING CONTEST – MANILA

October 29, 2005

 

 

Problem H 

 

Counting Symbols

 

Input File: h.in

 

 

A newly discovered language has an alphabet of 5 symbols.  A sentence in this language is a finite sequence of symbols k_{1 …} k_i … k_m where k_i  is in the set {L,I,N,U,X}. 

 

In this language, the allowable sentences can be described by the following rules:

 

L must be followed by I or U

I must be followed by N or L or X

N must be followed by U or I

U must be followed by N or X

X must be followed by L

 

The sentence LINUXLUX is allowable (i.e., in the language) while the sentence LINUXILL is not allowable (i.e., not in the language).

 

Among the allowable sentences of length n beginning with letter k₁, .., k_p, how many times did each of the  symbols L,I,N,U,X appear in the n^th position?

 

Input:

Input consists of multiple test cases.  An integer value corresponding to the value of n in the problem followed by starting symbols of the sentences describe each test case.  Your program should be able to handle sentences of length 30 and execute in reasonable time (less than 10 seconds).

 

Output:

 

The output is presented in multiple lines for each test case. The first two lines describe the test case. The succeeding lines are the symbol frequency counts.

 

Sample Input:

 

1

4 LINX

10 LINUX

 

 

Sample Output:

 

Symbol Count for Sentences of Length=1.

Sentences starting with ‘’

L:0

I:0

N:0

U:0

X:0

Symbol Count for Sentences of Length=4.

Sentences start with ‘L’, ‘I’, ‘N’, ‘X’

L:7

I:7

N:6

U:7

X:6

Symbol Count for Sentence of Length=10.

Sentences start with ‘L’, ‘I’, ‘N’, ‘U’, ‘X’

L:512

I:512

N:512

U:512

X:512