Problem Statement
Fox Ciel likes sequences of integers. She especially likes sequences which she considers to be beautiful. A sequence (A[0], A[1], ..., A[N-1]), N >= 1, is beautiful if and only if it satisfies the following conditions:
- Each element of the sequence is an integer between 0 and 40, inclusive.
- Each element of the sequence is less than or equal to the arithmetic mean of the previous elements. That is, for each i, 1 <= i < N, we have A[i] <= (A[0] + A[1] + ... + A[i-1]) / i.
- There are no three consecutive elements in the sequence that follow in strictly decreasing order. In other words, there must be no index i, 0 <= i < N-2, such that A[i] > A[i+1] > A[i+2].
You are given a int[] seq that describes some sequences. Each element in seq is between -1 and 40, inclusive. You can change each occurrence of -1 in seq into an arbitrary integer between 0 and 40, inclusive. Different occurrences can be changed into different integers.
Return the number of different beautiful sequences that can be obtained in this way, modulo 1,000,000,007.
Definition
- Class:
- FoxAverageSequence
- Method:
- theCount
- Parameters:
- int[]
- Returns:
- int
- Method signature:
- int theCount(int[] seq)
- (be sure your method is public)
Notes
- Two sequences of the same length are different if there is at least one position at which their elements are different.
Constraints
- seq will contain between 1 and 40 elements, inclusive.
- Each element of seq seq will be between -1 and 40, inclusive.
Examples
{3, -1}Returns: 4
{3, 0}, {3, 1}, {3, 2} and {3, 3} are valid sequences.{5, 3, -1}Returns: 2
{5, 3, 3} and {5, 3, 4} are valid sequences.{-1, 0, 40}Returns: 0
There are no valid sequences.{-1, 40, -1, -1, -1, 10, -1, -1, -1, 21, -1}Returns: 579347890
{-1, 12, 25, 0, 18, -1}Returns: 58
Back to all problems