FoxAndSouvenir | Topcoder Archive

Problem Statement

Fox Ciel is returning from her trip to New Fox Land. She is now waiting for her flight in the terminal. She still has some money left and she wants to spend all of it on souvenirs.

There is a rectangular grid of vending machines. The grid has n rows by m columns. Both rows and columns are numbered starting at zero. Each vending machine sells just one type of souvenirs. Different machines sell different souvenirs. Some vending machines may be broken. Broken machines don't sell anything.

The vending machine in row r, column c is described by the value price[r*m+c]. If this value is positive, it is the cost in dollars of buying a single souvenir in the machine. If the value is zero, the machine is broken.

Fox Ciel now wants you to answer multiple queries. For each valid i, query i has five parameters: xMin[i], xMax[i], yMin[i], yMax[i], and require[i]. The query you should answer looks as follows:

Ciel has exactly require[i] dollars and she wants to spend all of them on souvenirs.
Ciel only wants to use vending machines in some specific rectangular area. More precisely, she will only use machines in rows xMin[i] to xMax[i], inclusive, and columns yMin[i] to yMax[i], inclusive.
In each vending machine she will buy at most one souvenir (she doesn't want to have duplicates).
The answer to the query is the number of ways in which she can spend her money, modulo 1,000,000,009.

You are given the dimensions n and m, the int[] price, and the int[]s xMin, xMax, yMin, yMax, and require. Return a int[] with as many elements as there are queries. For each valid i, element i of the return value should be the answer to query i.

Definition

Class:: FoxAndSouvenir
Method:: waysToBuy
Parameters:: int, int, int[], int[], int[], int[], int[], int[]
Returns:: int[]
Method signature:: int[] waysToBuy(int n, int m, int[] price, int[] xMin, int[] xMax, int[] yMin, int[] yMax, int[] require)
(be sure your method is public)

Constraints

n, m will be between 1 and 50, inclusive.
price will contain exactly n*m elements.
Each number in price will be between 0 and 2,500, inclusive.
The sum of all integers in price will be no more than 2,500.
xMin will contain between 1 and 2,500 elements, inclusive.
xMin, xMax, yMin, yMax and require will contain the same number of elements.
Each element in xMin and xMax will be between 0 and (n-1), inclusive.
Each element in yMin and yMax will be between 0 and (m-1), inclusive.
For each i, xMin[i] will be less than or equal to to xMax[i].
For each i, yMin[i] will be less than or equal to to yMax[i].
Each element in require will be between 0 and 2,500, inclusive.

Examples

```
1
```
```
5
```
```
{5,0,5,7,7}
```
```
{0}
```
```
{0}
```
```
{0}
```
```
{4}
```
```
{12}
```
```
Returns: {4 }
```
We have 4 vending machines, each have a souvenir with price 5, 5, 7, 5. We want a total price = 12, we must select 1 with price = 5 and another with price = 7. So there are 2*2 = 4 ways to get that.

{1,2,3,
 4,5,6,
 7,8,9}

{0,0,0,0,0,0,0,0,0,0}

{2,2,2,2,2,2,2,2,2,2}

{0,0,0,0,0,0,0,0,0,0}

{2,2,2,2,2,2,2,2,2,2}

{1,2,3,4,5,6,7,8,9,10}

Returns: {1, 1, 2, 2, 3, 4, 5, 6, 8, 9 }

For example, there are 3 ways to get 5: {1,4}, {2,3}, {5}.

```
1
```
```
10
```
```
{1,0,2,1,0,3,1,0,0,1}
```
```
{0,0}
```
```
{0,0}
```
```
{2,3}
```
```
{5,7}
```
```
{3,4}
```
```
Returns: {2, 2 }
```
For the first query we want to get a total of 3 from {2,1,3}. For the second query we want to get a total of 4 from {1,3,1}.

{1,1,0,1,2,
 1,2,1,1,1,
 0,1,2,0,2,
 1,2,0,1,1,
 1,0,1,1,0}

{0,1,0,2,3}

{2,1,4,4,3}

{1,2,0,1,2}

{2,4,4,3,4}

{5,2,6,3,1}

Returns: {5, 3, 8928, 12, 2 }

{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}

{0}

{0}

{0}

{39}

{20}

Returns: {846527587 }

There are C(40, 20) = 137846528820 ways to do that. Don't forget mod 1,000,000,009.

```
1
```
```
1
```
```
{0}
```
```
{0}
```
```
{0}
```
```
{0}
```
```
{0}
```
```
{0}
```
```
Returns: {1 }
```

{5,7,7,5,6,9,3,7,2,8,7,5,4,7,6,6,8,8,7,12,9,4,4,3,5,7,6,6,15,3,11,8,7,11,6,9,7,5,3,11,10,7,5,3,1,3,2,10,6,10,3,10,6,5,6,
4,4,10,5,7,5,5,7,5,7,10,4,4,5,9,5,6,5,10,3,12,6,7,4,5,5,3,3,10,5,3,8,5,2,10,8,6,13,9,6,8,6,7,5,7,7,5,2,1,5,7,6,8,12,4,4,
6,4,6,7,4,3,7,2,8,5,5,5,5,8,3,6,3,7,6,9,3,4,3,5,3,7,5,10,4,7,6,8,5,8,4,8,4,6,6,4,9,9,5,7,5,4,10,10,1,9,4,3,10,4,6,9,7,4,
8,4,13,4,7,6,5,12,10,3,11,9,5,8,6,8,10,5,8,17,8,6,10,5,2,5,6,7,4,9,7,11,4,7,3,6,4,6,4,6,4,6,5,4,1,6,4,8,4,3,3,0,7,7,11,8,
9,8,4,7,7,6,8,4,2,8,7,7,9,3,5,7,5,13,8,8,10,5,10,6,6,10,8,5,5,5,2,5,9,10,4,3,5,4,7,14,5,4,7,7,3,5,8,5,6,6,7,4,7,9,6,7,4,4,
10,5,9,8,9,4,7,5,6,9,10,5,9,5,5,8,4,8,3,6,4,5,10,6,5,7,7,7,11,8,7,10,6,9,11,3,8,3,2,6,3,8,9,4,5,6,7,9,7,5,8,8,4,5,5,5,7,8,
11,11,6,8,4,3,3,11,6,5,12,6,6,8,7,10,4,5,6,6,7,8,8,7,9,6,8,5,6,3,7,7,2,4,3,1,9,3,7,3,5,4,10,6,7,6,6,8,6,5,8,8,11,8,1}

{11,6,4,6,11,11,2,0,11,2,5,3,5,4,10,0,6,11,7,0,10,4,2,7,13,6,2,9,0,4}

{13,8,4,17,15,14,13,13,15,3,16,17,13,6,15,11,15,15,9,11,12,8,12,16,16,14,6,10,1,14}

{8,1,1,17,4,2,0,8,1,7,1,14,11,7,2,15,14,2,1,12,2,14,1,11,10,2,4,8,3,9}

{20,17,3,19,17,13,10,10,2,9,10,15,20,12,7,21,17,13,16,15,9,14,11,12,20,14,7,9,3,19}

{55,147,232,244,268,98,102,381,114,251,363,94,31,169,226,24,393,387,8,179,270,283,202,274,264,156,258,54,172,381}

Returns: {78093026, 387159947, 0, 0, 291584072, 626572479, 426120834, 0, 0, 0, 745892889, 22065496, 262599170, 0, 7946, 9199037, 0, 54, 142, 103980580, 0, 0, 195571841, 0, 37, 502623060, 0, 0, 0, 96198211 }

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.