MBALL - Feline Olympics - Mouseball
A popular event at the feline Olympics is watching and wagering on the outcome of the house cats playing Mouseball [which has the same scoring rules as American football] but is played with a catnip mouse. Wagers often involved predicting the score and, of course, some scores are more likely to occur than others. Multiples of 7 are good bets, because teams typically go for touchdowns (6 points) then attempt to kick the football between the uprights for an extra point. A score of 4 is unlikely because safeties (2 points each) are rare.
A score of exactly 1 is nearly (though not) impossible to achieve: suppose Team A has just scored a touchdown; during the extra point attempt, Team A fumbles the ball; it is recovered by a player from Team B, who returns it almost the entire length of the field, but fumbles right before reaching the endzone; the ball is recovered by a player from Team A, who voluntarily enters his own endzone, where he is tackled by Team B; this counts as a safety, but because it was scored during an extra point attempt, Team B will only be awarded 1 point.
Not surprisingly, such a scenario is not known to have ever occurred in the history of the game. So for simplicity, we will ignore this possibility altogether and consider only the following ways of scoring points:
- a safety: 2 points, always
- a field goal: 3 points
- a touchdown: 6 points
Additionally, after scoring a touchdown, a team attempts a "try." This may be either an extra point or a two-point conversion and will give, if successful, 1 or 2 points, respectively.
Write a program that, given a score, outputs the number of ways that score can be achieved. As an example, a team could score 10 points in exactly 5 ways:
- 5 safeties
- 2 field goals and 2 safeties
- a touchdown, extra point good, and a field goal
- a touchdown, a two-point conversion, and a safety
- a touchdown with a failed try and 2 safeties
Note that order is not important: a touchdown followed by a field goal is considered equivalent to a field goal followed by a touchdown.
The first line of input will contain an integer N <= 100, indicating the number of test cases. Each of the next N lines will contain an integer S, the number of points scored by a team in a game. S will be between 0 and 100000 inclusive. (Hey, the orange & blue [Flame-point Siamese] team could make it happen.)
For each test case, output one line containing a single integer: the number of ways a team can score exactly S points.
Input: 2 10 6 Output: 5 3
Use long long :/
In order to tackle the ordering part you could refer to a standard dynamic programming problem of the number of ways to get a sum using coins of different values.Hard to get the intuition without it.
for the case of ordering
same code in java:tle,
Don't forget that to get 0 points there's 1 way. Cost me so many wrong answers. Now got AC in 0.08s =D.
Use long not int...spent a lot of time finding that bug..
can someone give me any pointers for how to ignore the ordering?
Ghost Of Perdition:
What is the point from disabling C++ 4.3.2 in some problems???