Compress the String

Dan is playing a game with Ben. Ben gives Dan a long string S, and Dan needs to compress S to a list or short strings: s[1], s[2], ..., s[N]. S only contains lowercase letters. Each s[i] can contain lowercase letters and digits, but only digits between i+1 and N, inclusive, are allowed for s[i]. For example, when N = 4, allowed digits for s[2] will be '3' and '4'.

In order to decompress such a list of strings into a single string, we'll apply string decompress algorithm for each string one by one, in reverse order (from s[N] to s[1]). The decompressing algorithm for a string is easy: just replace each digit in the string by the corresponding decompressed string with that digit as index. That is to say, for digit i in the string, it will be replaced by the decompressed string s[i]. Because we are applying decompressing algorithm in reverse order, s[i] will always be decompressed before it is used to replace a digit in other strings. When all the strings are decompressed, the decompressed string of s[1] will be the final result. If the decompressing result is S, we say S can be compressed to this list of strings.

Now Ben decides the number of short strings Dan can use (N), as well as the length limit for each short string. Dan needs to decide whether it is possible to compress S to N short strings under this limit.

There are multiple test cases (no more than 150). For each case, there will be three lines. The first line gives an integer N (1 ≤ N ≤ 4), which is the number of short strings Dan can use. The second line gives N integers L[1], ... L[N] (1 ≤ L[i] ≤ 4), which means the length of string s[i] should be at most L[i]. The third line gives the string S. The length of S will be between 1 and 500, inclusive. S will only contain lowercase letters.

For each case, if it is possible to compress S into N strings and the length of each string is no more than the limit, output "Yes". Otherwise, output "No".

1
1
aa
4
4 4 4 4
ttttttttttttttt

No
Yes

HANG, Hang

2011 Asia Dalian Regional Contest