10778번 - Bowling 서브태스크다국어

Byteasar is a fan of both bowling and statistics. He has written down the results of a few past bowling games. Unfortunately, some characters in the notes are blurry, and thus unreadable. Byteasar asks you to write a program to calculate the number of distinct games which are consistent with his notes.

Rules of Bowling

A bowling game consists of n frames: n − 1 simple frames and one final frame. In a typical game n = 10. At the beginning of each frame 10 pins are put standing upright at the end of a lane and a player gets no more than two (or three for the final frame) attempts (shots) to throw a bowling ball down the lane to try to knock down as many pins as possible. Each frame is denoted by two (for a simple frame) or three (for the final frame) characters.

For each shot the player receives as basic points the total number of pins knocked down in this shot. The player’s basic points in each frame are the sum of basic points of all the shots in this frame. If all 10 pins are knocked down in a simple frame (and therefore 10 basic points are earned), the player gets additional bonus points.

For a simple frame the rules are the following:

• If a player knocks down all 10 pins in the first shot of a frame, she gets a strike and the frame ends. As bonus points she gets the sum of basic points of her next two shots. A strike is denoted as “x-”.
• If a player knocks down all 10 pins using both shots of a frame, she gets a spare. As bonus points she gets the basic points of her next shot. A spare is denoted as “A/”, where A is a digit describing the number of pins knocked down in the first shot of the frame.
• If 9 or fewer pins are knocked down after both shots, the player gets just basic points and such a frame is denoted as “AB”, where A is the one-digit number of pins knocked down in the first shot, and B is the one-digit number of pins knocked down in the second shot (A + B < 10).

Note that bonus points are included to the score of a frame in which the strike or the spare was obtained, regardless of the fact that the exact number of bonus points depends on future shots in next frames.

For the final frame the rules are the following:

• Initially the player receives two shots in this frame. If 9 or fewer pins are knocked down in the two shots, the frame ends. Otherwise (if the first two shots are a spare or the first shot is a strike), the player receives a third shot in the frame. Whenever the player knocks down all the pins in any of the three shots, the pins are reset to the initial configuration for the next shot. The score of the final frame is the total number of pins knocked down (note that no bonus points are earned due to strikes and spares).
• Overall there are seven possible configurations of the final frame with the following outcomes (A and B stand for one-digit numbers):

Each game is described as a sequence of 2n + 1 characters. At the end of the game the total number of points after each frame may be calculated. For example, for a game of n = 10 frames described as “08x-7/2/x-x-23441/0/x”, the player’s points after respective frames were as follows:

The first line of input contains one integer q (1 ≤ q ≤ 25), specifying the number of test cases to consider. The following 3q lines of input contain descriptions of test cases. Each test case is described by three lines of input.

The first line of a test case description contains one integer n (2 ≤ n ≤ 10), specifying the number of frames. The second line contains a sequence of 2n + 1 characters which denotes the game description from Byteasar’s notes. Blurry characters are replaced by “?” characters. The third line contains n integers, the total number of points after each frame, separated by spaces. In each number either all digits are readable, or all digits are blurry. Numbers in which all digits are blurry are replaced by “-1”.

Your program should output q lines, one line per each test case in the same order as in the input.

For each test case your program should write one integer: the number of possible distinct games corresponding to the test case. Two games are considered different if and only if they differ in at least one shot, that is, their (2n+ 1)-character game descriptions are different. You can assume that there is at least one game consistent with each test case in the input. You can assume that the result fits into 64-bit signed integer type.

In the first case, in frame 5 after the character “x” the only possible character is “-”. In frame 8 the player got 8 points in total. Thus there are 9 possibilities how this sum could have been obtained: 0 + 8, 1 + 7, . . . , 8 + 0. There were no bonus points in frame 9. Therefore, there were no points on the first shot of the final frame. To obtain 20 points in the last two shots, the only possibility is a spare with a following strike in the last shot of the frame. Therefore there are 9 different valid games which correspond to this input data.

In the second case, any character from 0 to 9 is consistent with the input data.