Connection Status:
Competition Arena > FoxAverageSequenceEasy

FoxAverageSequenceEasy

Member SRM 501 · 2010-11-01 · by wrong

Member SRM 501 · 2010-11-01 · by wrong · Dynamic Programming
Class Name: FoxAverageSequence
Return Type: int
Method Name: theCount
Arg Types: (vector<int>)
Problem Statement

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.

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
0)
{3, -1}
Returns: 4

{3, 0}, {3, 1}, {3, 2} and {3, 3} are valid sequences.

1)
{5, 3, -1}
Returns: 2

{5, 3, 3} and {5, 3, 4} are valid sequences.

2)
{-1, 0, 40}
Returns: 0

There are no valid sequences.

3)
{-1, 40, -1, -1, -1, 10, -1, -1, -1, 21, -1}
Returns: 579347890
4)
{-1, 12, 25, 0, 18, -1}
Returns: 58

Submissions are judged against all 132 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class FoxAverageSequence with a public method int theCount(vector<int> seq) · 132 test cases · 2 s / 256 MB per case

Submitting as anonymous