ProductQuery
SRM 540 · 2011-11-22 · by rng_58
SRM 540 · 2011-11-22 · by rng_58 · Dynamic Programming, Math
Problem Statement
Problem Statement
Mrs. Jeipouju took part in a programming contest. One of the problems was as follows:
You are given an array A containing N integers. Each element of A is an integer between 0 and 9, inclusive. You are also given two arrays Qfrom and Qto, containing Q elements each. For each i, Qfrom[i] and Qto[i] describe the i-th query: you must take all elements of A with indices between Qfrom[i] and Qto[i], inclusive, and calculate their product modulo 10. Output exactly Q integers. The i-th number of the output must be the answer to the i-th query.
Mrs. Jeipouju made an input for this task by herself and generated the output using her program. However, she erased the array A by mistake - now she only knowsint N, int[] Qfrom, int[] Qto and int[] output (output[i] is the i-th integer generated by her program). Return the number of possible arrays A, modulo 1,000,000,007. If there are no possible arrays A (i.e. her program is definitely wrong), return 0.
You are given an array A containing N integers. Each element of A is an integer between 0 and 9, inclusive. You are also given two arrays Qfrom and Qto, containing Q elements each. For each i, Qfrom[i] and Qto[i] describe the i-th query: you must take all elements of A with indices between Qfrom[i] and Qto[i], inclusive, and calculate their product modulo 10. Output exactly Q integers. The i-th number of the output must be the answer to the i-th query.
Mrs. Jeipouju made an input for this task by herself and generated the output using her program. However, she erased the array A by mistake - now she only knows
Constraints
- N will be between 1 and 100, inclusive.
- Qfrom, Qto and output will contain the same number of elements.
- Qfrom, Qto and output will contain between 1 and 50 elements, inclusive.
- Each element of Qfrom and Qto will be between 0 and N-1, inclusive.
- For each i, Qto[i] will be greater than or equal to Qfrom[i].
- Each element of output will be between 0 and 9, inclusive.
Examples
0)
3
{0}
{0}
{5}
Returns: 100
A[0] must be 5. A[1] and A[2] are arbitrary integers between 0 and 9.
1)
5
{0, 2, 0}
{1, 4, 4}
{3, 4, 6}
Returns: 0
Mrs. Jeipouju's program is definitely wrong.
2)
3
{0, 1}
{1, 2}
{5, 8}
Returns: 4
There are 4 possible inputs: A[0] = 5, A[1] = 1, A[2] = 8 A[0] = 5, A[1] = 3, A[2] = 6 A[0] = 5, A[1] = 7, A[2] = 4 A[0] = 5, A[1] = 9, A[2] = 2
3)
8
{2, 0, 3, 6}
{3, 7, 4, 6}
{2, 0, 6, 7}
Returns: 118080
4)
58
{2, 7, 1, 15, 27, 5, 34, 26, 10, 22}
{18, 34, 4, 29, 52, 40, 54, 36, 34, 25}
{2, 6, 3, 4, 5, 0, 7, 8, 4, 1}
Returns: 0
Submissions are judged against all 68 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class ProductQuery with a public method int theInput(int N, vector<int> Qfrom, vector<int> Qto, vector<int> output) · 68 test cases · 2 s / 256 MB per case