ZOJ Problem Set - 2648
Vivid likes playing bowl, however his highest score is never beyond 160. Once, he got 159 points, what a pity! So, he was thinking hard to calculate how many ways existed to get 160 points.
Of course, since you may not know how to score a game of bowling, there is a simple description of the rules. The basic game consists of ten frames. In a frame, you get two chances to throw a ball down the alley and knock over as many pins as you can. There are ten pins standing at the beginning of a frame, and none are replaced after getting knocked over on the first ball, so the most pins you can knock over in a frame is ten. You get one point for each pin knocked over. In addition, there are two bonuses you can earn. If you knock over all ten pins on your first ball of the frame, you have scored a ��strike��; besides the ten points for the pins, your score in this frame is increased by the total number of pins knocked down with your next two balls. Those next two balls are usually part of another frame (or two) and score points in that frame (or those frames) as well. If you knock over all ten pins in a frame, but it takes you two balls to do it, you have scored a ��spare��; in addition to your ten points for pins knocked down, your score for the frame is increased by the number of pins you knock down on your next ball. Of course, those pins also count as part of the next frame. If you score a spare (or strike) in the final (tenth) frame, you are entitled to one (or two) extra balls to determine your tenth frame bonus. A perfect game scores 300 points, because each frame scores 30, 10 for knocking down 10 pins, and 20 for knocking down 20 pins with the next two balls combined.
Notice: In a frame, you first knock over a pin(s), then knock over b pin(s) (a != b) is not the same as you first knock over b pin(s), then knock over a pin(s).
There are multiple test cases. Each test case contains a integer S indicate the score (between 0 to 300 inclusive).
Each test case output a integer indicate the ways to get S points in a single line.
0 1 300
1 20 1
Author: JIN Tianpeng
Source: ZOJ Monthly, February 2006