|시간 제한||메모리 제한||제출||정답||맞힌 사람||정답 비율|
|1 초||256 MB||1||1||1||100.000%|
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:
A/”, where A is a digit describing the number of pins knocked down in the first shot of the frame.
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:
||three consecutive strikes||30|
||two consecutive strikes and a shot with A pins knocked down||20 + A|
||a strike and a spare with A pins knocked down on its first shot||20|
||a strike and two following shots with A and B pins knocked down respectively (A + B < 10)||10 + A + B|
||a spare with A pins knocked down on the first shot and a strike||20|
||a spare with A pins knocked down on the first shot and B pins knocked down in the last shot||10 + B|
||two shots with A and B pins knocked down respectively (A+B < 10)||A + B|
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:
|Frame||Denotation||Basic Points||Bonus Points||Frame Score||Total|
||0 + 8||—||8||8|
||10||7 + 3||20||28|
||7 + 3||2||12||40|
||2 + 8||10||20||60|
||10||10 + 2||22||82|
||10||2 + 3||15||97|
||2 + 3||—||5||102|
||4 + 4||—||8||110|
||1 + 9||0||10||120|
||0 + 10 + 10||—||20||140|
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 “
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.
at most six “
the result is at most 109
no game whose description contains any characters “
the input sequence ends with “
no additional constraints
2 10 08x-7/2/x?x-23??1/??? 8 -1 40 60 82 97 102 110 120 140 5 x-x-23?/00- 22 37 42 52 52
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
9 is consistent with the input data.