Write Program in JAVA Programming Language

Radio stations have a challenging job: Creating a daily play-list. At the beginning of each day, a radio station creates a daily play-list (a list of songs that it will play for that day). If a radio station wishes to stay in business, it will choose the songs that are likely to be most popular. It has been observed that the number of requests for a song in the preceding days is a good predictor of whether the song will be popular in the future. In fact, requests in recent days are better predictors of a song's popularity than requests in earlier days. For a given song, this observation is modeled by the exponential moving average: Pt = RtW + Pt-1(1 -W) where Pt is the predicted popularity of the song after day t, Rt is the fraction of requests for the song out all requests on that day,

Rt = (# of requests for the song on day t) / (Total # of requests on day t) and W is the weight given to more recent requests and is in the range 0 ....1.

Problem 1 (C Grade): Radio Ga Ga

Given a list of songs, and sequences of daily song requests your program will need to create a play-list of a specified length that the radio station should play. Write a program called RadioGaGa.java that reads in a song list, and a sequence of song requests, spanning multiple days, and outputs a play-list of specified length for each following day.

Input

The input comprises a number of lines. The first line, contains an integer N, denoting the number of songs in the song list. This is followed by N lines, enumerating the songs. Each line consists of three values: a single word, denoting the title of the song; an integer T, denoting the length of the song (in seconds); and decimal value between 0 and 1 denoting the initial popularity of the song. For example: Red_Barchetta 371 0.5 The next line contains three values: an integer T, denoting the maximum length (in minutes) of the play-list, a double W denoting the weight attributed to new requests (see the formula above); and an integer D denoting the number of days of song requests to follow. For example, 22 0.5 2 specifies a T = 22 minute play-list, with a weight W = 0:5, and D = 2 days of song requests. Each day of requests consists of a number of lines. The first line contains the integer R, denoting the number of song requests to follow. The next R lines contain song titles from the previously loaded song list. (See Example section.)

Processing

1) The day 0 of programming begins after the list is read. Each following day begins after a day of song requests have been read.

2) The play-list should be as close to the specified time T as possible without exceeding T minutes.

3) Songs should be added to the list according to popularity (most popular to least pop- ular), with ties broken by song length. For example, if two songs are equally popular, the shorter one is preferred.

4) If a song is too long to t on the play-list, it is passed over.

5)The order of the songs on the play-list should be the order in which they were added.

Output

For each day (0 ....D) your program should output a play-list. I.e., there should be D + 1 play-lists. Each play-list consists of single line. Each line starts with an integer denoting the day followed by the play-list song titles in the order specified, separated by spaces. Each line is terminated by a new-line character. See next section for example of output. Example

Sample Input

13 The_Garden 419 0.7 Red_Sector_A 311 0.6 High_Water 333 0.4 Red_Barchetta 371 0.5 The_Pass 291 0.55 Roll_The_Bones 330 0.45 Arm_And_Sword 396 0.55 Test_For_Echo 356 0.35 Vapor_Trails 358 0.34 Nobodys_Hero 349 0.22 2112_Overture 1232 0.7 Closer_To_The_Heart 175 0.9 Cygnus_X_1 622 0.2 22 0.5 2 5 Red_Sector_A Red_Sector_A Vapor_Trails Red_Sector_A Test_For_Echo 6 The_Garden Vapor_Trails 2112_Overture The_Garden Test_For_Echo 2112_Overture Sample Output 0 Closer_To_The_Heart The_Garden Red_Sector_A The_Pass 1 Red_Sector_A Closer_To_The_Heart The_Garden The_Pass 2 The_Garden Red_Sector_A Closer_To_The_Heart Test_For_Echo