Connection Status:
Competition Arena > Computers

Computers

SRM 257 · 2005-08-08 · by dgoodman

SRM 257 · 2005-08-08 · by dgoodman · Dynamic Programming, Recursion
Class Name: Computers
Return Type: long
Method Name: choices
Arg Types: (int, int, int, int)
Problem Statement

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.

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
3)
1000
5
1
10
Returns: 173961190219683
4)
529
8
3
5
Returns: 14613709

Submissions are judged against all 84 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class Computers with a public method long long choices(int n, int minDif, int minInComp, int amount) · 84 test cases · 2 s / 256 MB per case

Submitting as anonymous