플린코

플린코(Plinko)는 거의 수직으로 세운 판에 못이 여러 줄로 어긋나게 박혀 있는 게임입니다. 참가자는 판 위쪽의 다섯 칸 중 하나를 골라 칩을 떨어뜨리고, 칩이 판을 따라 튕겨 내려가는 모습을 지켜봅니다. 칩은 못에 부딪힐 때마다 왼쪽이나 오른쪽으로 튑니다. 공정한 플린코 판이라면 양쪽으로 갈 확률이 정확히 50%씩입니다(단, 판의 양쪽 가장자리에서는 한 방향으로만 갈 수 있습니다). 칩은 결국 맨 아래 줄에 도달하며, 도착한 열에 따라 상품이 정해집니다.

당신은 정직하지 못한 플린코 대회의 참가자이고, 모든 판이 조작되어 있다는 사실을 알고 있습니다. 각 못에서 칩이 오른쪽 또는 왼쪽으로 갈 확률이 항상 공정하지는 않습니다. 다행히 각 판의 못마다 칩이 오른쪽으로 갈 확률(백분율)이 적힌 설계도를 손에 넣었습니다. 이제 특정 칸에 칩을 떨어뜨렸을 때 그 칩이 지정된 열에 도착할 확률을 계산하는 프로그램만 있으면 됩니다.

공정한 플린코 게임의 확률은 다음과 같은 모습입니다.

	a chip starts in one of five lettered
	columns at the top:
	                           prob. chip will go right
	# A # B # C # D # E #            at each peg:
	#                   #       
	# *   *   *   *   * #  =======> 1/1 1/2 1/2 1/2 0/1
	#                   #
	#   *   *   *   *   #  =======> 1/2 1/2 1/2 1/2
	#                   #
	# *   *   *   *   * #  =======> 1/1 1/2 1/2 1/2 0/1
	#                   #
	# A * B * C * D * E #  =======> 1/2 1/2 1/2 1/2
	#####################

	a chip ends at the bottom

다음은 A 열에 떨어뜨린 칩이 지나갈 수 있는 한 가지 경로입니다.

	# | # B # C # D # E #      prob. chip will go right:
	#  \                #
	# * \ *   *   *   * #  =======> 1/1 1/2 1/2 1/2 0/1
	#   /               #
	#  /*   *   *   *   #  =======> 1/2 1/2 1/2 1/2
	#  \                #
	# * \ *   *   *   * #  =======> 1/1 1/2 1/2 1/2 0/1
	#    \              #
	# A * | * C * D * E #  =======> 1/2 1/2 1/2 1/2
	#####################

이 경로가 정확히 이대로 나올 확률은 얼마일까요? 첫 번째 이동(오른쪽)의 확률은 1/1, 두 번째 이동(왼쪽)의 확률은 1/2, 세 번째 이동(오른쪽)의 확률은 1/1, 마지막 이동(오른쪽)의 확률은 1/2였습니다. 따라서 이 경로가 나올 확률은 다음과 같습니다.

1/1 * 1/2 * 1/1 * 1/2 = 1/4 = 25%

하지만 칩이 맨 아래 줄의 B 열에 도착하는 경로는 이것 말고도 더 있으며, 칩이 그 자리에 도착할 전체 확률을 구하려면 그 경로들도 모두 함께 고려해야 합니다.

'A'와 'E' 표시 바로 아래에 있는 못은 특별한 값을 가진다는 점에 주의하세요. 이 두 열은 판의 가장자리에 있어서 칩이 갈 수 있는 방향이 하나뿐입니다. 조작된 판이라 하더라도 이 규칙만은 반드시 지킵니다.

입력의 첫 줄에는 분석해야 할 플린코 판의 개수를 나타내는 정수 $n$이 주어집니다. 그다음 줄부터 판들의 정보가 이어집니다. 각 판은 네 줄로 이루어지며, 각 줄은 그 줄에 있는 못들이 위에 떨어진 칩을 오른쪽으로 보낼 확률을 분수로 나타냅니다(각 분수의 분자와 분모는 모두 한 자리 숫자입니다). 위 그림처럼 못이 다섯 개인 줄과 네 개인 줄이 번갈아 나옵니다. 각 판 다음에는 세 줄이 이어지며, 각 줄에는 떨어뜨리는 칩 세 개 각각에 대한 시작 열과 도착 열의 문자가 주어집니다.

각 판마다 먼저 data set #X 형식의 머리글을 출력합니다. 여기서 X는 첫 번째 판이면 1, 두 번째 판이면 2와 같이 판의 순번입니다. 그런 다음 각 (시작 열, 도착 열) 쌍에 대해 Y->Z P paths, H% chance 형식으로 출력합니다. Y와 Z는 입력으로 주어진 시작 열과 도착 열이고, P는 두 열을 잇는 서로 다른 경로의 수이며, H는 시작 열에 떨어뜨린 칩이 맨 아래 줄의 도착 열에 도달할 확률(백분율)입니다. 확률의 소수 부분은 버리고(내림) 정수 부분만 출력합니다.