2014
11-30

# Infinite monkey theorem

Could you imaging a monkey writing computer programs? Surely monkeys are smart among animals. But their limited intelligence is no match for our human beings. However, there is a theorem about monkeys, and it states that monkeys can write everything if given enough time.
The theorem is called “Infinite monkey theorem”. It states that a monkey hitting keys at random on a typewriter keyboard for an infinite amount of time will almost surely type any given text, which of course includes the programs you are about to write (All computer programs can be represented as text, right?).
It’s very easy to prove this theorem. A little calculation will show you that if the monkey types for an infinite length of time the probability that the output contains a given text will approach 100%.
However, the time used is too long to be physically reasonable. The monkey will not be able to produce any useful programs even if it types until the death of the universe. To verify this and ensure that our human beings are not replaceable by monkeys, you are to calculate the probability that a monkey will get things right.

There will be several test cases.
Each test case begins with a line containing two integers n and m separated by a whitespace (2<=n<=26, 1<=m<=1000). n is the number of keys on the typewriter and the monkey will hit these keys m times. Thus the typewriter will finally produce an output of m characters.
The following n lines describe keys on the typewriter. Each line has a lower case letter and a real number separated by a whitespace. The letter indicates what the typewriter will produce if the monkey hits that key and the real number indicates the probability that the monkey will hit this key. Two hits of the monkey are independent of each other (Two different hits have the same probability for a same key), and sum of all the probabilities for each key is ensured to be 1.
The last line of the test case contains a word composed of lower case letters. The length of the word will be less than or equal to 10.
The input will end with a line of two zeros separated by a whitespace. This line should not be processed.

There will be several test cases.
Each test case begins with a line containing two integers n and m separated by a whitespace (2<=n<=26, 1<=m<=1000). n is the number of keys on the typewriter and the monkey will hit these keys m times. Thus the typewriter will finally produce an output of m characters.
The following n lines describe keys on the typewriter. Each line has a lower case letter and a real number separated by a whitespace. The letter indicates what the typewriter will produce if the monkey hits that key and the real number indicates the probability that the monkey will hit this key. Two hits of the monkey are independent of each other (Two different hits have the same probability for a same key), and sum of all the probabilities for each key is ensured to be 1.
The last line of the test case contains a word composed of lower case letters. The length of the word will be less than or equal to 10.
The input will end with a line of two zeros separated by a whitespace. This line should not be processed.

4 10
w 0.25
o 0.25
r 0.25
d 0.25
word
2 10
a 1.0
b 0.0
abc
2 100
a 0.312345
b 0.687655
abab
0 0

2.73%
0.00%
98.54%

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <cstdio>

#define N 1100

using namespace std;

struct TR
{
int son[26],f;bool fg;
}tr[N];

int n,q[N],m,len,cnt;
double dp[N][30][2],g[30];
char str[N];

inline void insert(char *s)
{
int now=1;
for(int i=0;i<len;i++)
{
if(!tr[now].son[s[i]-'a']) tr[now].son[s[i]-'a']=++cnt;
now=tr[now].son[s[i]-'a'];
}
tr[now].fg=true;
}

inline void build()
{
int h=1,t=2,sta; q[1]=1;
while(h<t)
{
sta=q[h++];
for(int i=0;i<26;i++)
{
int now=tr[sta].son[i],tmp;
if(sta==1) tmp=1;
else tmp=tr[tr[sta].f].son[i];
if(now==0) tr[sta].son[i]=tmp;
else
{
tr[now].f=tmp; tr[now].fg|=tr[sta].fg;
q[t++]=now;
}
}
}
}

{
memset(g,0.0,sizeof g);
double a;
for(int i=1;i<=n;i++)
{
scanf("%s%lf",str,&a);
g[str[0]-'a']=a;
}
memset(tr,0,sizeof tr);
tr[cnt=1].f=1;
scanf("%s",str);
len=strlen(str);
insert(str);
build();
}

inline void go()
{
memset(dp,0,sizeof dp);
dp[0][1][0]=1.0;
for(int i=0;i<m;i++)
for(int j=1;j<=cnt;j++)
{
if(dp[i][j][0]>0.0)
{
for(int k=0;k<26;k++)
{
if(g[k]==0.0) continue;
if(tr[tr[j].son[k]].fg) dp[i+1][tr[j].son[k]][1]+=dp[i][j][0]*g[k];
else dp[i+1][tr[j].son[k]][0]+=dp[i][j][0]*g[k];
}
}
if(dp[i][j][1]>0.0)
{
for(int k=0;k<26;k++)
{
if(g[k]==0.0) continue;
dp[i+1][tr[j].son[k]][1]+=dp[i][j][1]*g[k];
}
}
}
double ans=0.0;
for(int i=1;i<=cnt;i++) ans+=dp[m][i][1];
printf("%.2lf%%\n",ans*100.0);
}

int main()
{
return 0;
}

1. 不喜欢归不喜欢，但是请你别说8D垃圾，我承认他现在是老了，但是你没资格黑人家知道么，你要是当着劳资面说8D垃圾我一巴掌呼死你知道不

2. 不喜欢归不喜欢，但是请你别说8D垃圾，我承认他现在是老了，但是你没资格黑人家知道么，你要是当着劳资面说8D垃圾我一巴掌呼死你知道不

3. 不喜欢归不喜欢，但是请你别说8D垃圾，我承认他现在是老了，但是你没资格黑人家知道么，你要是当着劳资面说8D垃圾我一巴掌呼死你知道不

4. 不喜欢归不喜欢，但是请你别说8D垃圾，我承认他现在是老了，但是你没资格黑人家知道么，你要是当着劳资面说8D垃圾我一巴掌呼死你知道不

5. 不喜欢归不喜欢，但是请你别说8D垃圾，我承认他现在是老了，但是你没资格黑人家知道么，你要是当着劳资面说8D垃圾我一巴掌呼死你知道不

6. 不喜欢归不喜欢，但是请你别说8D垃圾，我承认他现在是老了，但是你没资格黑人家知道么，你要是当着劳资面说8D垃圾我一巴掌呼死你知道不

7. 我比較喜歡你現在這樣的博客型態，正如其他人所言，我覺得大多數人還是潛水居多，而且論壇已經太多了，倒不如專注於你現在的博客。把文章作個細項的分類，或許也可以將特定分類（例如技術層面的，如 WordPress 技巧、WordPress 主題、jQuery……

8. 我比較喜歡你現在這樣的博客型態，正如其他人所言，我覺得大多數人還是潛水居多，而且論壇已經太多了，倒不如專注於你現在的博客。把文章作個細項的分類，或許也可以將特定分類（例如技術層面的，如 WordPress 技巧、WordPress 主題、jQuery……

9. 我比較喜歡你現在這樣的博客型態，正如其他人所言，我覺得大多數人還是潛水居多，而且論壇已經太多了，倒不如專注於你現在的博客。把文章作個細項的分類，或許也可以將特定分類（例如技術層面的，如 WordPress 技巧、WordPress 主題、jQuery……

10. 我比較喜歡你現在這樣的博客型態，正如其他人所言，我覺得大多數人還是潛水居多，而且論壇已經太多了，倒不如專注於你現在的博客。把文章作個細項的分類，或許也可以將特定分類（例如技術層面的，如 WordPress 技巧、WordPress 主題、jQuery……

11. 我比較喜歡你現在這樣的博客型態，正如其他人所言，我覺得大多數人還是潛水居多，而且論壇已經太多了，倒不如專注於你現在的博客。把文章作個細項的分類，或許也可以將特定分類（例如技術層面的，如 WordPress 技巧、WordPress 主題、jQuery……

12. 我比較喜歡你現在這樣的博客型態，正如其他人所言，我覺得大多數人還是潛水居多，而且論壇已經太多了，倒不如專注於你現在的博客。把文章作個細項的分類，或許也可以將特定分類（例如技術層面的，如 WordPress 技巧、WordPress 主題、jQuery……

13. 我比較喜歡你現在這樣的博客型態，正如其他人所言，我覺得大多數人還是潛水居多，而且論壇已經太多了，倒不如專注於你現在的博客。把文章作個細項的分類，或許也可以將特定分類（例如技術層面的，如 WordPress 技巧、WordPress 主題、jQuery……

14. 学算法中的数据结构学到一定程度会乐此不疲的，比如其中的2－3树，类似的红黑树，我甚至可以自己写个逻辑文件系统结构来。