Pastebin launched a little side project called VERYVIRAL.com, check it out ;-) Want more features on Pastebin? Sign Up, it's FREE!
Guest

Untitled

By: a guest on Oct 30th, 2012  |  syntax: None  |  size: 2.88 KB  |  views: 136  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. The scoring rules of 10-pin bowling are as follows:
  2.  
  3. 1) A game consists of 10 frames. In each frame, the bowler has two chances to knock down as many pins as possible.
  4. 2) For each pin knocked down, the bowler scores 1 point.
  5. 3) If the bowler knocks off all pins with the first ball in a frame, it is called a "strike". In this case, the number of pins knocked off in the next two balls bowled is also added to the player's score for this frame.
  6. 4) Instead, if the bowler knocks off all remaining pins with the second ball in a frame, it is called a "spare". In this case, the number of pins knocked off in the next ball bowled is also added to the player's score for this frame.
  7. 5) If the player bowls a strike in the last frame, he is awarded two extra balls so as to allow the awarding of bonus points. If both these balls also result in strikes, a total of 30 points (10 + 10 + 10) is awarded for the frame. Similarly, if the player bowls a spare in the last frame, he is awarded one extra ball and the score for that ball is added to the score of the last frame.
  8.  
  9. For this problem, we will consider games with N frames.
  10.  
  11. For example, if N = 4 and the scores in the 4 frames achieved are:
  12. 3 6 | 10 | 5 5 | 9
  13. The scores for each frame are 9, 10 + (5 + 5), 5 + 5 + 9, and 9 respectively. The total score is 57.
  14.  
  15. If N = 3, and the scores in the 3 frames achieved are:
  16. 10 | 10 | 5 5.
  17. In this case, since the last frame was a spare, an additional ball will be bowled. If the bowler scores say 3 on that ball, the scores for each frame are: 10 + 10 + 5, 10 + 5 + 5, 5 + 5 + 3, for a total score of 58.
  18.  
  19. Note that the maximum score with N frames is 30 * N. This score is attained when all N frames are strikes, and the two additional balls bowled are strikes as well.
  20.  
  21. Given N and M, you need to count how many score sequences over N frames can result in a total score of M.
  22.  
  23.  
  24. Input:
  25. The first line contains the number of test cases T. The next T lines contain two integers, N and M respectively.
  26.  
  27. Output:
  28. Output T lines, one for each test case. Output all answers modulo 1000000007.
  29.  
  30. Constraints:
  31. 1 <= T <= 1000
  32. 1 <= N <= 100
  33. 0 <= M <= 30 * N
  34.  
  35.  
  36. Sample Input:
  37. 5
  38. 1 9
  39. 1 11
  40. 1 25
  41. 3 90
  42. 3 10
  43.  
  44. Sample Output:
  45. 10
  46. 12
  47. 1
  48. 1
  49. 3003
  50.  
  51.  
  52. Explanation:
  53. For the first case, there are 10 ways to score 9 in 1 frame - 0,9 or 1,8 ... or 9,0.
  54.  
  55. For the second case, there are 10 ways to bowl a spare in the first frame and score an additional 1 point with the extra ball. It is also possible to score a strike in the first frame followed by 0,1 or 1,0 with the two extra balls. Thus there are a total of 12 ways.
  56.  
  57. For the third case, there is only 1 way. Score a strike in the first frame, score another strike with the first extra ball, and an additional 5 with the second extra ball.
  58.  
  59. For the fourth case, there is again only 1 way. Score a strike in all frames, as well as with the two extra balls.