NoRepeatPlaylist
SRM 531 · 2011-11-22 · by Mimino
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
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.
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}.
Submissions are judged against all 96 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class NoRepeatPlaylist with a public method int numPlaylists(int N, int M, int P) · 96 test cases · 2 s / 256 MB per case