All submissions for this problem are available.
You are a huge music fan! And you're a programming freak , too. So you've decided to create an application called "Music Mania" . "Music Mania" predicts the user's most played song as well as the number of songs he plays in a month, on the basis of his taste for music.
Here is what you've planned out:
You will ask the users for their Top 3 favourite music genres and Top 3 Favourite Bands. Then you'll ask them to input an arbitrary number of songs. According to your algorithm, the user is twice as likely to play songs from his/her favourite bands/artists. Similarly, he is twice as likely to play songs from his/her favorite genres. On the basis of the songs that have been entered, your program will calculate the expected number of times the "least played" song was played. Then using probability, the program will calculate the total number of songs played in the month.
The procedure used by the program to calculate the number of times the "least played" song was played:
Suppose the user entered N songs, each song having a probability of being played p(1),p(2),...p(N) respectively. Let LP denote the number of times the "least played" song was played. Now, the formula for the expected value of LP :
LP = 1*p(N) + 2*p(N-1) + 3*p(N-2) + ...... + i*p(1) / p(1) + p(2) + p(3) + ... + p(N)
Your task is to convert the above mentioned technique into a program.
The first line contains the number of test cases, T.
T Test cases follow.
For every test case, the first line is the list of the user's 3 favourite genres, which will be 3 space seperated strings.
The next line will contain names of his/her 3 favourite bands/artists which is again a space separated list.
Next line will contain the number of songs 'S' that the user wishes to enter.
The next S lines will each contain 3 space seperated strings, in this format :
ArtistName SongName Genre
Please note that the entered strings DO NOT HAVE SPACES inside them.
For example, the band "Pink Floyd" will be entered as "PinkFloyd".
Refer to the sample test cases below.
The sum of number of times each song was played in a month (an integral value) and the name of the most played song. In case multiple songs were played the same number of times, output the song that was entered first in the input for the test case.
0 < N < 1000000
Input: 3 Psychedelic Progressive Classic PinkFloyd TheDoors TheBeatles 5 PinkFloyd Time Progressive TheDoors TheEnd Psychedelic TheBeatles LetItBe Pop MGMT Whistle Psychedelic LinkinPark InTheEnd AltRock HeavyMetal DeathMetal BlackMetal Metallica ChildrenofBodom CradleofFilth 0 Jazz Blues Bollywood JohnMayer AmitTrivedi DireStraits 2 LinkinPark GivenUp Rock IronMaiden RunToTheHills NWOBHM Output: 47 Time 0 3 GivenUp
Explanation for Sample Case 1 :
Lets assume that a song that is least played has a probability of being played equal to 'p'.
The song "Time" is from his favourite band, "PinkFloyd" and also from his favourite genre "Progressive". So it has 2*2p = 4p probablity of being played.
Similarly, "TheEnd" also has 4p as the probability of being played.
"LetItBe" is from his favourite band, thus has a probablity 2p of being played.
"Whistle" too has a probability 2p of being played.
"InTheEnd" has p probability of being played.
After calculation, the value of p = 0.07692
After further calculations, the sum of number of times each song was played comes out to be 47.
Explanation for Sample Case 2 :
There are 0 songs entered.
Hence, the output is 0 and a space character.
Explanation for Sample Case 3 :
Both the songs entered are not from the user's favourite band/genre. Thus both are equally likely to be played with p(1) = 0.5 and p(2)=0.5
Thus the number of times the "least played" will be played 1.5.
Hence, the sum of number of times each song was played in the month = 1.5 + 1.5 = 3.
|Time Limit:||0.1 - 0.25731 sec|
|Source Limit:||50000 Bytes|
Fetching successful submissions
If you are still having problems, see a sample solution here.