시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 6 6 6 100.000%

문제

외로운 토끼들이 모여서 재미있는 게임을 하기로 결정했다.

게임은 총 N (N ≥ 2)개의 칸이 가로로 놓여진 곳에서 진행되며, 왼쪽부터 오른쪽까지 0번부터 N-1번의 번호가 매겨져 있다. 각각의 칸은 흰색, 검정색, 빨간색 중의 하나로 칠해져 있다.

총 r마리의 토끼가 모여서 게임을 하려고 한다. 각각의 토끼는 게임을 시작할 칸을 무작위로 고르며, 두 토끼가 같은 칸에 있는 경우는 없다. 시작 칸으로 골라질 r개의 칸은 모두 같은 확률로 골라진다.

게임판의 크기는 칸의 개수와 같으며 (처음에는 N)이다. 다음을 게임판의 크기가 2보다 큰 동안 반복한다.

  • 모든 토끼는 인접한 칸으로 이동한다. 각각의 칸은 최대 2개의 인접한 칸을 가지고 있으며, 다음과 같은 규칙을 이용해 토끼가 이동할 칸을 정한다.
    • 0번 칸에 있는 토끼는 항상 1번 칸으로 이동한다.
    • 게임판의 크기를 size라고 했을 때, size-1이나 size-2에 있는 토끼는 항상 왼쪽에 있는 칸으로 이동한다.
    • 나머지 토끼는 현재 자신이 있는 칸의 색상에 따라서 이동할 칸을 결정한다.
      • 흰색: 왼쪽 칸으로 이동한다
      • 검정색: 오른쪽 칸으로 이동한다
      • 빨간색: 아직 한 번도 이동한 적이 없다면, 왼쪽 칸으로 이동한다. 그 외의 경우에는 현재 칸에 오기 전에 있었던 칸으로 이동한다.
  • 모든 토끼의 이동이 끝난 후에, 한 마리보다 많은 토끼가 있는 칸에 있는 토끼는 게임에서 제외된다.
  • 가장 오른족 칸은 게임판에서 사라진다. 즉, 게임판의 크기가 1 감소한다. 위의 규칙에 의하면 가장 오른쪽 칸은 항상 비어있게 된다.

게임이 끝났을 때, 게임판에 남아있는 토끼는 0, 1, 2마리 중 하나이다. 게임이 끝났을 때, 게임판에 남아있을 수 있는 토끼의 수의 기댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 게임판의 색상이 주어진다. 게임판의 크기(N)는 2보다 크거나 같고, 17보다 작거나 같으며, W는 흰색, B는 검정색, R은 빨간색을 나타낸다.

둘째 줄에는 토끼의 수 r (1 ≤ r ≤ N)이 주어진다.

출력

게임판에 남아있을 수 있는 토끼의 수의 기댓값을 출력한다. 정답과의 절대/상대 오차는 10-9까지 허용한다.

예제 입력

WRBRW
4

예제 출력

0.8

예제 입력 2

WWB
2

예제 출력 2

1.3333333333333333

예제 입력 3

WW
1

예제 출력 3

1.0

예제 입력 4

BBBBBBBBBB
4

예제 출력 4

0.9523809523809523

예제 입력 5

RRBRRWRRBRRW
8

예제 출력 5

0.9696969696969697

힌트

출처