시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 1024 MB | 416 | 59 | 36 | 18.090% |
하얀 구슬, 초록 구슬 접시, 자리 열 여섯 개, 정사각형 접시가 있고, 4x4 형태로 구슬이 들어갈 자리가 16개 있습니다. 구슬은 하얀 구슬과 초록 구슬 두 종류가 있습니다. 이것들을 이용해서 할 수 있는 action은 6가지가 있습니다.
접시 가운데에 구슬을 떨어뜨리면, 16칸의 자리 중 한 곳 들어가게 됩니다. 만약 가운데 4개 중 4개의 자리가 전부 비어있다면 25% 확률에 따라 어딘가 하나에 들어가게 됩니다. 3개의 자리가 비어있다면, 이미 채워진 한 자리의 대각선 맞은 편에 100% 확률로 들어가게 됩니다. 2개의 자리가 비어있다면, 50% 확률로 남은 두 자리 중 하나에 들어가고, 한 자리가 비어있다면, 역시 남은 한 자리에 100% 확률로 들어갑니다.
가운데 4개 칸이 모두 가득 차 있을 경우 남은 빈 칸중 한 곳에 동일한 확률로 들어가게 됩니다.
남은 action 4가지는 접시를 기울이는 것입니다.
접시를 기울이면, 중력에 의해 구슬이 움직입니다. 예를 들어, 왼쪽으로 접시를 기울이면, 각 구슬이 더 이상 왼쪽에 빈칸이 없을 때까지 왼쪽에 붙게 됩니다.
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 = 1)가 주어진다. 그 다음에는 T개의 테스트 케이스가 주어진다.
각 테스트 케이스의 첫 줄은 action의 개수 N (0 ≤ N ≤ 16)과 N개의 action들이 주어진다.
이 후 4줄에 걸쳐 얻고자 하는 접시 상태가 입력된다.
각 테스트 케이스마다 한 줄에 걸쳐 정답을 출력한다. 절대오차나 상대오차가 10-6미만인 경우 정답으로 인정된다.
1 2 W T EWEE EEEE EEEE EEEE
0.5
1 3 G R B EEEE EEEE EEEE EEEG
1
Contest > Coder's High > Coder's High 2014 B번