Problem Statement
Michael loves listening to music from his cell phone while travelling by train. He currently has N songs in his cell phone. During one trip he has the time to listen to P songs. So his cell phone creates a playlist of P (not necessarily different) songs according to the following rules:
- Each song has to be played at least once.
- At least M songs have to be played between any two occurrences of the same song. (This ensures that the playlist is not playing the same song too often.)
Michael wonders how many different playlists his cell phone can create. You are given the
Definition
- Class:
- NoRepeatPlaylist
- Method:
- numPlaylists
- Parameters:
- int, int, int
- Returns:
- int
- Method signature:
- int numPlaylists(int N, int M, int P)
- (be sure your method is public)
Notes
- Two playlists A and B are different if for some i between 1 and P, inclusive, the i-th song in A is different from the i-th song in B.
Constraints
- N will be between 1 and 100, inclusive.
- M will be between 0 and N, inclusive.
- P will be between N and 100, inclusive.
Examples
1
0
3
Returns: 1
You have only 1 song which can be played as often as you want. So the only valid playlist is: {song1, song1, song1}.
1
1
3
Returns: 0
Now is the same scenario as in Example 0, but the song cannot be played 2 times in a row. Thus there is no valid playlist.
2
0
3
Returns: 6
Now you have 2 songs and you can play them as often as you want. Just remember that playlists {song1, song1, song1} and {song2, song2, song2} are not valid, because each song must be played at least once.
4
0
4
Returns: 24
You have time to play each song exactly once. So there are 4! possible playlists.
2
1
4
Returns: 2
The only two possibilities are {song1, song2, song1, song2} and {song2, song1, song2, song1}.
50
5
100
Returns: 222288991
1
0
1
Returns: 1
1
1
1
Returns: 1
1
0
2
Returns: 1
1
1
2
Returns: 0
2
0
2
Returns: 2
2
1
2
Returns: 2
2
2
2
Returns: 2
1
0
3
Returns: 1
1
1
3
Returns: 0
2
0
3
Returns: 6
2
1
3
Returns: 2
2
2
3
Returns: 0
3
0
3
Returns: 6
3
1
3
Returns: 6
3
2
3
Returns: 6
3
3
3
Returns: 6
1
0
4
Returns: 1
1
1
4
Returns: 0
2
0
4
Returns: 14
2
1
4
Returns: 2
2
2
4
Returns: 0
3
0
4
Returns: 36
3
1
4
Returns: 18
3
2
4
Returns: 6
3
3
4
Returns: 0
4
0
4
Returns: 24
4
1
4
Returns: 24
4
2
4
Returns: 24
4
3
4
Returns: 24
4
4
4
Returns: 24
47
47
47
Returns: 846397273
47
46
47
Returns: 846397273
47
47
48
Returns: 0
1
0
100
Returns: 1
1
1
100
Returns: 0
2
0
100
Returns: 976371283
2
1
100
Returns: 2
2
2
100
Returns: 0
3
0
100
Returns: 956927880
3
1
100
Returns: 964556918
3
2
100
Returns: 6
3
3
100
Returns: 0
100
0
100
Returns: 437918130
100
100
100
Returns: 437918130
42
20
100
Returns: 917652623
35
4
100
Returns: 241141251
70
33
100
Returns: 113350320
79
78
100
Returns: 472081547
63
16
100
Returns: 791270589
6
5
100
Returns: 720
82
61
100
Returns: 443647325
62
50
100
Returns: 362358782
96
11
100
Returns: 22353827
28
13
100
Returns: 491360085
92
3
100
Returns: 635215935
3
1
100
Returns: 964556918
14
6
93
Returns: 137054740
16
5
17
Returns: 122941672
31
19
48
Returns: 654394566
37
0
39
Returns: 834227218
52
22
68
Returns: 35563645
14
6
95
Returns: 282801414
20
12
23
Returns: 353616274
62
25
65
Returns: 762027972
11
11
54
Returns: 0
38
36
45
Returns: 601830705
60
15
100
Returns: 228534218
99
3
100
Returns: 989467997
37
7
97
Returns: 945713644
50
30
100
Returns: 226791857
53
3
100
Returns: 177662748
50
23
81
Returns: 885425071
49
7
100
Returns: 437821697
5
5
5
Returns: 120
80
8
100
Returns: 467650474
100
25
100
Returns: 437918130
64
33
100
Returns: 910604984
40
15
100
Returns: 553780149
25
13
60
Returns: 23832333
88
5
100
Returns: 638621416
100
1
100
Returns: 437918130
50
10
100
Returns: 663536800
10
10
100
Returns: 0
100
10
100
Returns: 437918130
99
5
100
Returns: 53044368
50
7
100
Returns: 363575434
20
2
100
Returns: 545911587
60
25
100
Returns: 145208404
13
9
39
Returns: 997218499
50
50
50
Returns: 318608048