当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

3266:Hamlet’s gambling

题目描述
“There are a thousand Hamlets in a thousand people's eyes. ”
    ----W. William Shakespeare


Lotus is a big fan of Shakespeare. Her favorite tragedy written by Shakespeare is Hamlet, one of the most popular works in English language. However, since Lotus is really a merciful and kindhearted girl, she doesn’t like the scene of the final match, in which Hamlet fenced against Laertes. Once she had a dream of Hamlet. In that dream, Hamlet fought with Laertes in another way: flipping coins.

It sounds like gambling. In order to flip the coin in an absolutely fair way, Hamlet got a monkey to do this job instead of people. Before the monkey started to flip, Hamlet and Laertes respectively wrote down an arbitrary sequence of results (we call it a “pattern”). For example, Hamlet wrote down “Head, Tail, Head” while Laertes wrote down “Head, Head, Tail, Tail”.It was guaranteed that the pattern of Hamlet’s did not occur within the pattern of Laertes’, nor did the pattern of Laertes’ occur within the pattern of Hamlet’s. Then the monkey began to flip the coin over and over and generated a sequence of results, like “Head, Head, Tail, Head, Tail …” At any time, if the monkey obtained Hamlet’s pattern, it stopped flipping and Hamlet won. Otherwise, if the monkey obtained Laertes’s pattern, it also stopped flipping and Laertes won.

One example of the gambling is like following: Hamlet’s pattern was “HHT” (H=Head, T=Tail) and his rival’s pattern was “HTTT”. The monkey flipped the coin and obtained “H, T, H, T, T, H, T, T, T”. At that time, Laertes’ pattern appeared at the end of the sequence, so the monkey stopped and the judge declared that Laertes won the game.

Now your task is to decide that in Lotus’ gambling, who has the higher probability to win the game. Pay attention that since the monkey has no bias, the probabilities to get head or tail in one flip are always equal.
输入解释
The input contains several test cases. The first line of each case contains two positive integers N and M (0<N, M<=100000). N is the length of Hamlet’s pattern and M is the length of Laertes’. The second line contains a string of length N, representing the pattern of Hamlet’s. The third line contains a string of length M, representing the pattern of Laertes’. All the strings only contain uppercase letters ‘H’ and ‘T’. The input ends by a line of two zeros.
输出解释
For each test case, output a single line to show your answer. If Hamlet has a better chance to win, output the word “Hamlet”. If Laertes has a better chance, output the word “Laertes”. If they have the same probability to win the game, output the word “Equal”.
输入样例
1 1
H
T
1 2
T
HH
0 0
输出样例
Equal
Hamlet

提示
For the first sample case, to end the game, one flip is enough. If it is head, Hamlet wins. Otherwise Laertes wins. As a result, both of them has 1/2 probability to win.

For the second sample case, if the first flip is tail, Hamlet wins. Otherwise if the second flip is tail, also Hamlet wins. Otherwise Laertes wins. 
So the probability that Hamlet wins the game is 3/4, while the probability that Laertes wins is 1/4. Hamlet has a better chance.
来自杭电HDUOJ的附加信息
Recommend lcy

该题目是Virtual Judge题目,来自 杭电HDUOJ

源链接: HDU-3266

最后修改于 2020-10-25T23:01:48+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
2000/1000MS(Java/Others) 32768/32768K(Java/Others)