수열 생성기
시간 제한2초메모리 제한512 MB
길이가 같은 H/T 패턴 여러 개가 주어질 때, 그중 하나가 처음 연속으로 나올 때까지 던진 동전 횟수의 기대값을 구합니다.
문제
바이너리 카지노에서 가장 인기 있는 게임 중 하나는 "바이너리 생성기"라는 게임이다. 여러 명의 플레이어가 동전 하나로 이 게임을 한다. 각 플레이어는 먼저 주어진 길이의 앞면과 뒷면 수열을 하나씩 고른다. 그다음 플레이어나 카지노가 동전을 던지기 시작하고, 자신이 고른 수열이 던진 결과에 연속된 부분 수열로 가장 먼저 나타나는 플레이어가 이긴다.
당신은 플레이어들이 고른 모든 수열이 똑같이 좋기 때문에 어떤 수열을 고르든 상관없다고 믿는다. 하지만 돈을 전부 잃고 나서 그 믿음이 흔들리기 시작했다. 당신이 틀렸다는 것을 증명하는 프로그램을 작성하시오. 같은 길이의 앞면과 뒷면 수열 목록이 주어질 때, 플레이어들이 고른 수열 중 하나가 던진 수열에 연속된 부분 수열로 나타날 때까지 동전을 던져야 하는 횟수의 기댓값을 구하시오. 동전을 던지는 횟수의 기댓값은, 어떤 플레이어의 승리로 이어지는 모든 가능한 던짐 수열에 대해 각 수열의 확률을 가중치로 한 던짐 수열 길이의 평균이다.
입력
입력의 첫째 줄에는 두 정수 W와 B(1 ≤ W ≤ 10, 1 ≤ B ≤ 30)가 주어진다. W는 플레이어 수열의 개수이고 B는 플레이어 수열의 길이이다. 다음 W개 줄에는 각각 B개의 문자로 이루어진 수열이 하나씩 주어진다. 각 문자는 앞면을 뜻하는 "H" 또는 뒷면을 뜻하는 "T"이다.
출력
동전을 던지는 횟수의 기댓값을 한 개의 수로 출력한다. 출력값이 정답과 0.1 이내로 차이가 나면 정답으로 인정된다.