The Basketball Game
All submissions for this problem are available.
Bob has recently learnt how to play basketball and he was told by Alice that the rules in basketball were as follows :
• 1 point for a free throw
• 2 points for a throw from within the D
• 3 points for a throw from outside the D
Being an inquisitive mind that Bob is, he would like to know how many combinations of 1-pointers, 2-pointers and 3-pointers can lead to a team score of N points.
Now if a team has scored enough points, Bob wouldn't be able to remember the number of possible combinations long enough to show-off in front of your friends.
So you decide to keep track of result modulo 100001.
Help Bob to compute the number of combinations of 1-pointers, 2-pointers and 3-pointers that can lead to a team score of N points.
The first line contains single integer T - the number of test cases. T test cases follow.For each test case input will just be a number which denotes the team score N.
Output should be number of combinations of 1-pointers, 2-pointers and 3-pointers that can lead to the given team score modulo 100001.
Sum of all the N's across a test file doesn't exceed 10^8.
Input: 4 8 12 1033 894755 Output: 10 19 89441 22727
Example case 1:
For the 1st test case,following are the possible combinations for team score of 8
1x6 + 2x1
1x4 + 2x2
1x2 + 2x3
1x5 + 3x1
1x3 + 2x1 + 3x1
1x1 + 2x2 + 3x1
1x2 + 3x2
2x1 + 3x2
NOTE : Use fast Input Output.
|Time Limit:||0.18 - 0.46 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, JAVA, GO|
Fetching successful submissions