TopCoder Statistics - 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.

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

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.
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.
1000

5

5

10

Returns: 113420686168080
1000

5

1

10

Returns: 173961190219683
529

8

3

5

Returns: 14613709
1

15

1

1

Returns: 1
24

15

1

10

Returns: 0
25

15

1

10

Returns: 1
1000

1000

10

10

Returns: 1
1000

23

2

32

Returns: 8161973618
39

9

2

15

Returns: 1
39

10

2

15

Returns: 0
895

11

3

48

Returns: 316512474230
150

5

1

15

Returns: 149000
999

667

3

100

Returns: 1
999

5

3

333

Returns: 1
997

23

23

35

Returns: 721
1000

5

1

29

Returns: 1029704832576574848
500

6

250

2

Returns: 1
998

10

2

879

Returns: 0
999

8

4

729

Returns: 0
999

6

3

595

Returns: 0
996

10

1

694

Returns: 2459695
993

9

3

755

Returns: 0
998

6

2

186

Returns: 6676289999230
991

6

3

623

Returns: 0
994

9

3

734

Returns: 0
997

8

4

772

Returns: 0
993

6

4

404

Returns: 0
999

6

3

281

Returns: 116536
995

7

1

132

Returns: 555244678911023
992

7

5

688

Returns: 0
994

10

5

543

Returns: 0
995

9

5

169

Returns: 9402
326

80

26

158

Returns: 0
784

29

1

116

Returns: 5835877
443

91

6

158

Returns: 0
359

36

29

103

Returns: 0
652

58

27

10

Returns: 2093
443

32

21

131

Returns: 0
663

69

12

94

Returns: 0
532

34

3

137

Returns: 11
641

12

5

65

Returns: 1242722
635

11

12

32

Returns: 295096
535

25

8

22

Returns: 71506
579

5

4

31

Returns: 274534078261
980

11

8

90

Returns: 301072
422

10

4

45

Returns: 325381
950

14

13

42

Returns: 7121535
834

20

14

6

Returns: 314300196
745

11

1

54

Returns: 74926183760
927

10

14

37

Returns: 114484608
840

14

14

48

Returns: 2585
739

8

9

23

Returns: 43099920426
539

17

10

18

Returns: 912636
849

16

3

15

Returns: 47544882460
594

19

6

57

Returns: 10082
602

12

12

76

Returns: 0
495

9

4

58

Returns: 1337180
478

9

12

30

Returns: 2112
511

11

13

62

Returns: 0
974

9

13

70

Returns: 62
452

6

6

67

Returns: 88
784

19

7

29

Returns: 65589098
880

17

13

3

Returns: 52814
634

8

6

9

Returns: 31852321257
678

14

14

49

Returns: 0
1000

5

1

30

Returns: 1026422528606748097
1000

5

1

28

Returns: 1025312423793859418
999

5

1

29

Returns: 1004886441099242096
999

5

1

1000

Returns: 0
345

15

1

757

Returns: 0
1

5

1

2

Returns: 0
1

5

1

1

Returns: 1
1

1000

1

1

Returns: 1
45

5

46

1

Returns: 0
45

5

23

2

Returns: 0
1000

5

1

1000

Returns: 1
1000

5

5

10

Returns: 113420686168080
1000

5

1

63

Returns: 379259218509992696
1000

5

1

300

Returns: 494122875344338
1000

5

1

100

Returns: 127422982821203918
1000

5

5

20

Returns: 90705939142338637
1000

5

1

30

Returns: 1026422528606748097

Statistics

Problem Statement for "Computers"

Problem Statement

Definition

Constraints

Examples