OkonomiyakiParty | Topcoder Archive

Problem Statement

Wolf Sothe is planning a party for his M friends. He wants to give them some okonomiyaki at the party. (Okonomiyaki is a Japanese pancake.)

Sothe just came to an okonomiyaki restaurant. The restaurant makes several types of okonomiyaki. Each type of okonomiyaki has its specific size. You are given the sizes of all okonomiyaki types as a int[] osize.

Sothe would like to buy exactly M okonomiyaki. They must all have different types, so that the people at the party have the most options to choose from. Additionally, they must all have roughly the same sizes, so that nobody feels disappointed. More precisely, the difference between the size of the largest and smallest okonomiyaki ordered by Sothe must be K or less.

You are given the int[] osize and the ints M and K. Compute and return the number of different orders Sothe could place at the restaurant, modulo 1,000,000,007.

Definition

Class:: OkonomiyakiParty
Method:: count
Parameters:: int[], int, int
Returns:: int
Method signature:: int count(int[] osize, int M, int K)
(be sure your method is public)

Constraints

osize will contain between 2 and 50 elements, inclusive.
Each element in osize will be between 1 and 10,000, inclusive.
M will be between 2 and the number of elements in osize, inclusive.
K will be between 1 and 10,000, inclusive.

Examples

```
{1,4,6,7,9}
```
```
2
```
```
3
```
```
Returns: 6
```
There are five types of okonomiyaki. Let's call them types A, B, C, D, and E. (Type A has size 1, type B has size 4, and so on.) Sothe wants to buy M=2 different okonomiyaki and their sizes must differ by K=3 or less. There are 6 valid orders: A+B, B+C, B+D, C+D, C+E, and D+E. Note that B+A is the same order as A+B: you get one pancake of type A and one pancake of type B.
```
{1,6,2,7,4,2,6,1,5,2,4}
```
```
4
```
```
3
```
```
Returns: 60
```
Different types of okonomiyaki may have equal sizes. An order may contain multiple okonomiyaki of the same size, they are only required to have different types.
```
{1,4,5,7,10,11,13,16,18}
```
```
4
```
```
5
```
```
Returns: 0
```
In this test case there is no valid order: regardless of which 4 pancakes Sothe wants, the difference between their sizes will be too large.

{55,2,7,232,52,5,5332,623,52,6,532,5147}

Returns: 924

{5781,8708,1754,4750,9888,3675,4810,1020,922,9834,5695,1101,1236,2496,8431,6727,
1376,3373,4423,1839,7438,9407,1851,6966,8715,2905,542,535,8980,2602,2603,3117,3452,
5682,7775,4356,5140,8923,9801,3729}

Returns: 114514

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.