동전 던지기
시간 제한1초메모리 제한256 MB
두 사람이 길이 20 이하의 H/T 문자열을 하나씩 고르고, 공정한 동전을 던져 둘 중 하나 또는 둘 다 처음 나타날 때까지 진행할 때 앨리스 승리, 밥 승리, 무승부 확률을 각각 구한다.
문제
Alice와 Bob은 각각 앞면과 뒷면만으로 이루어진 문자열을 하나씩 골랐다. 그다음 공정한 동전을 던져, 연속된 던지기 결과가 두 문자열 중 하나 이상과 일치할 때까지 반복한다. Alice의 문자열이 먼저 나타나면 Alice가 이기고, Bob의 문자열이 먼저 나타나면 Bob이 이긴다. 두 문자열이 동시에 나타날 수도 있다. 이 경우에는 무승부다.
두 문자열이 주어졌을 때, 이 세 가지 결과가 나올 확률은 각각 얼마인가?
입력
첫째 줄에 Alice의 문자열이, 둘째 줄에 Bob의 문자열이 주어진다. 두 문자열은 H와 T로만 이루어져 있고, 길이는 1 이상 20 이하다.
출력
출력은 세 줄로 이루어지며, 각 줄에는 실수 하나가 들어간다. 차례대로 Alice가 이길 확률, Bob이 이길 확률, 무승부가 될 확률이다.
정답과의 차이가 이하이면 정답으로 인정된다.