TopCoder problem "Computers" used in SRM 257 (Division I Level Three)



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

Writer:

dgoodman

Testers:

PabloGilberto , lbackstrom , brett1479 , Olexiy

Problem categories:

Dynamic Programming, Recursion