Problem Statement

We have n identical processors and want to build a fixed amount of computers with them. Each computer is characterized by the number of processors we put into it. We want to use all the processors, and we don't mind forming many identical computers, but have decided that it would be wasteful to form two different computers that do not differ significantly. We also want all the computers that we build to be reasonably powerful.

Create a class Computers that contains a method choices that takes four ints as input: n (the number of processors), minDif (the smallest allowable difference between the number of processors in different computers), minInComp (the minimum number of processors that a computer is allowed to have), and amount (the number of computers we must produce). The method returns a long value that is the number of distinct ways in which we can combine all our processors to form amount computers.

Definition

 Class: Computers Method: choices Parameters: int, int, int, int Returns: long Method signature: long choices(int n, int minDif, int minInComp, int amount) (be sure your method is public)

Constraints

-n will be between 1 and 1000, inclusive.
-minDif will be between 5 and 1000, inclusive.
-minInComp will be between 1 and 1000, inclusive.
-amount will be between 1 and 1000, inclusive.

Examples

0)

 `20` `6` `5` `2`
`Returns: 4`
 The different ways in which we can produce the 2 computers are {5,15}, {6,14}, {7,13}, and {10,10}. Note that {4,16} would not be legal since a computer is not allowed to have less than 5 processors, and that {8,12} would not be legal because these two computers are different but do not differ by at least 6 processors.
1)

 `100` `500` `400` `1`
`Returns: 0`
 Since each computer must have at least 400 processors and we have only 100, it is not possible to build even 1 computer.
2)

 `1000` `5` `5` `10`
`Returns: 113420686168080`

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=2006

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=8005&pm=2006

dgoodman

Testers:

PabloGilberto , lbackstrom , brett1479 , Olexiy

Problem categories:

Dynamic Programming, Recursion