시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
4 초 256 MB 302 39 28 18.421%

문제

하얀 구슬, 초록 구슬 접시, 자리 열 여섯 개, 정사각형 접시가 있고, 4x4 형태로 구슬이 들어갈 자리가 16개 있습니다. 구슬은 하얀 구슬과 초록 구슬 두 종류가 있습니다. 이것들을 이용해서 할 수 있는 action은 6가지가 있습니다.

  • (W) 하얀 구슬을 접시 가운데에 떨어뜨린다.
  • (G) 초록 구슬을 접시 가운데에 떨어뜨린다.

접시 가운데에 구슬을 떨어뜨리면, 16칸의 자리 중 한 곳 들어가게 됩니다. 만약 가운데 4개 중 4개의 자리가 전부 비어있다면 25% 확률에 따라 어딘가 하나에 들어가게 됩니다. 3개의 자리가 비어있다면, 이미 채워진 한 자리의 대각선 맞은 편에 100% 확률로 들어가게 됩니다. 2개의 자리가 비어있다면, 50% 확률로 남은 두 자리 중 하나에 들어가고, 한 자리가 비어있다면, 역시 남은 한 자리에 100% 확률로 들어갑니다.

가운데 4개 칸이 모두 가득 차 있을 경우 남은 빈 칸중 한 곳에 동일한 확률로 들어가게 됩니다.

남은 action 4가지는 접시를 기울이는 것입니다.

  • (L) 접시를 왼쪽으로 기울인다.
  • (R) 접시를 오른쪽으로 기울인다.
  • (T) 접시를 위쪽으로 기울인다.
  • (B) 접시를 아래쪽으로 기울인다.

접시를 기울이면, 중력에 의해 구슬이 움직입니다. 예를 들어, 왼쪽으로 접시를 기울이면, 각 구슬이 더 이상 왼쪽에 빈칸이 없을 때까지 왼쪽에 붙게 됩니다.

E = empty, W = white, G = green

ex1)

EWEE
WEGW
GWGE
EEEE

ex1을 왼쪽으로 기울인 결과)

WEEE
WGWE
GWGE
EEEE

ex1을 오른쪽으로 기울인 결과)

EEEW
EWGW
EGWG
EEEE

ex1을 위쪽으로 기울인 결과)

WWGW
GWGE
EEEE
EEEE

ex1을 아래쪽으로 기울인 결과)

EEEE
EEEE
WWGE
GWGW

N개의 action과 접시 상태 하나가 주어집니다. 빈 접시에서 시작해서, N번의 action 후에 입력으로 주어진 접시 상태와 동일한 모양이 나올 확률을 계산하세요.

입력

입력 파일의 첫 번째 줄에 테스트 케이스의 수를 의미하는 자연수 T가 주어진다. 그 다음에는 T개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 줄은 action의 개수 N (0 ≤ N ≤ 16)과 N개의 action들이 주어진다.

이 후 4줄에 걸쳐 얻고자 하는 접시 상태가 입력된다.

출력

각 테스트 케이스마다 한 줄에 걸쳐 정답을 출력한다. 절대오차나 상대오차가 10-6미만인 경우 정답으로 인정된다.

예제 입력

2
2 W T
EWEE
EEEE
EEEE
EEEE
3 G R B
EEEE
EEEE
EEEE
EEEG

예제 출력

0.5
1

힌트

출처

Contest > Coder's High > Coder's High 2014 B번