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.

Input

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.)

Output

For each test case, output one line containing a single integer: the number of ways a team can score exactly S points.

Example

Input:
2
10
6

Output:
5
3

Added by:Miorel Palii
Date:2009-10-26
Time limit:1s
Source limit:4096B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 C++ 4.3.2 NODEJS OBJC PERL6 SQLITE VB.NET
Resource:University of Florida Local Contest - September 27, 2009

hide comments
2018-06-16 11:16:25
Good problem
Don't know why only a handful of people have attempted it.

Here's a hint :
Let a2,a3,a6,a7,a8 denote the number of safeties , ..and so on.
Let n be desired score. So,
2*a2 + 3*a3 + 6*a6 + 7*a7 + 8*a8 = n.
Now find the number of solutions(integral obviously) for the above equation using recursion.

Last edit: 2018-06-16 11:20:33
2017-04-17 10:02:34
Use long long :/
2016-06-25 23:32:07
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.
2016-05-06 23:21:51 farhad chowdhury
for the case of ordering
index idx is always calculated from index (idx-1)
so u can calculate the 100000 for a particular idx in any order u dont have to calculate serially.
now think how can u calculate so that the ordering problem gets solved.
kinda sieve type
2016-01-29 11:12:32 birdie
same code in java:tle,
c: ac
2015-01-19 15:30:13 Arvind Ravi
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.
2014-06-29 21:37:40 The Bear
Use long not int...spent a lot of time finding that bug..
2014-01-05 16:39:50 Ishan Bansal
can someone give me any pointers for how to ignore the ordering?
2013-05-20 21:15:44 Ghost Of Perdition
What is the point from disabling C++ 4.3.2 in some problems???
no one knows :P
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.