3573 - Buying Candies III 3573 - Buying Candies III 3573 - Buying Candies III

Statistics Sub: 23 | AC: 9 | AC%: 39,13 | Score: 4,76
Created by Oreste Nillar Cambara
Added by Oreste (2016-03-24)
Limits
Total Time: 3000 MS | Test Time: 1000 MS |Memory: 512 MB | Output: 64 MB | Size: 9 KB
Enabled languages
Available in

Description

John would like to go the shop for some candies. The local grocery has exactly N types of candies and almost an infinite amount of candies of each type. These candies have a cylindrical shape, each has a radius of 10 units and a given length. The weight of the candies is equal to its length.
John has a knapsack that can carry M units of weight.  On his way to the shop, John opens a hole of rectangular shape in the bottom of the knapsack of length K and 10 units of width.
The knapsack have a special feature:The dimensions of the knapsack vary depending on the set of candies that John puts on it. It's length will be as long as the max between the size hole and the longer of the bought candies, and its height is equal to the size of the set of bought candies. The width is static and equal to 10 units.
He would like to know how many combinations of candies he can buy, in a way that the total weight on his knapsack be exactly M units.
John would like to go the shop for some candies. The local grocery has exactly N types of candies and almost an infinite amount of candies of each type. These candies have a cylindrical shape, each has a radius of 10 units and a given length. The weight of the candies is equal to its length.
John has a knapsack that can carry M units of weight.  On his way to the shop, John opens a hole of rectangular shape in the bottom of the knapsack of length K and 10 units of width.
The knapsack have a special feature:The dimensions of the knapsack vary depending on the set of candies that John puts on it. It's length will be as long as the max between the size hole and the longer of the bought candies, and its height is equal to the size of the set of bought candies. The width is static and equal to 10 units.
He would like to know how many combinations of candies he can buy, in a way that the total weight on his knapsack be exactly M units.
John would like to go the shop for some candies. The local grocery has exactly N types of candies and almost an infinite amount of candies of each type. These candies have a cylindrical shape, each has a radius of 10 units and a given length. The weight of the candies is equal to its length.
John has a knapsack that can carry M units of weight.  On his way to the shop, John opens a hole of rectangular shape in the bottom of the knapsack of length K and 10 units of width.
The knapsack have a special feature:The dimensions of the knapsack vary depending on the set of candies that John puts on it. It's length will be as long as the max between the size hole and the longer of the bought candies, and its height is equal to the size of the set of bought candies. The width is static and equal to 10 units.
He would like to know how many combinations of candies he can buy, in a way that the total weight on his knapsack be exactly M units.

Input specification

The first line contains three integers N, M and K denoting the number of different candies in the local grocery, the weight that the knapsack can carry and the length of the hole.
The following N lines contains one integer Ai denoting the weight of each candy.
(1<=N<=100, 1<=M<=10^9, 0<=K<=10^9) where M/Ai<=100 and max(Ai,...,An)-min(Ai,...,An)<=10 for i= 1, 2, ... N;jsessionid=EB569271BD3058A137BBFF0CD371F534
The first line contains three integers N, M and K denoting the number of different candies in the local grocery, the weight that the knapsack can carry and the length of the hole.
The following N lines contains one integer Ai denoting the weight of each candy.
(1<=N<=100, 1<=M<=10^9, 0<=K<=10^9) where M/Ai<=100 and max(Ai,...,An)-min(Ai,...,An)<=10 for i= 1, 2, ... N;jsessionid=EB569271BD3058A137BBFF0CD371F534
The first line contains three integers N, M and K denoting the number of different candies in the local grocery, the weight that the knapsack can carry and the length of the hole.
The following N lines contains one integer Ai denoting the weight of each candy.
(1<=N<=100, 1<=M<=10^9, 0<=K<=10^9) where M/Ai<=100 and max(Ai,...,An)-min(Ai,...,An)<=10 for i= 1, 2, ... N;jsessionid=EB569271BD3058A137BBFF0CD371F534

Output specification

Print the number of different ways that John can buy the candies and its total weight is exactly equal to M.
As the result is a very large value, you must modulate 1000000007.
Print the number of different ways that John can buy the candies and its total weight is exactly equal to M.
As the result is a very large value, you must modulate 1000000007.
The first line contains three integers N, M and K denoting the number of different candies in the local grocery, the weight that the knapsack can carry and the length of the hole.
The following N lines contains one integer Ai denoting the weight of each candy.
(1<=N<=100, 1<=M<=10^9, 0<=K<=10^9) where M/Ai<=100 and max(Ai,...,An)-min(Ai,...,An)<=10 for i= 1, 2, ... N;jsessionid=EB569271BD3058A137BBFF0CD371F534

Sample input

3 10 0
4
3
7

Sample output

2

Hint(s)

Input:
3 10 4
4
3
7

Ouput
1

in the first example we can buy the following convination
3 3 4
3 7

in the second example we can place the candy of size 7 at the bottom and up the one of size 3
the convination 3 3 4 is not valid because the hole in the backpack is 4 and the sweets fall
Input:
3 10 4
4
3
7

Ouput
1

in the first example we can buy the following convination
3 3 4
3 7

in the second example we can place the candy of size 7 at the bottom and up the one of size 3
the convination 3 3 4 is not valid because the hole in the backpack is 4 and the sweets fall
Input:
3 10 4
4
3
7

Ouput
1

in the first example we can buy the following convination
3 3 4
3 7

in the second example we can place the candy of size 7 at the bottom and up the one of size 3
the convination 3 3 4 is not valid because the hole in the backpack is 4 and the sweets fall

Recommendation

We have carefully selected several similar problems: 3378 | 3599 | 3147 | 1103 | 3134 | 2191