//Alex Silva copyright (c) 2013
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
public class puzzle2Driver {
//DRIVER FIELDS
private static Scanner scn;
private static ArrayList<Song> arrInput;
private static String[] tokens
; private static int nSongs;
private static int nSelects;
//MAIN METHOD
scn = null;
try {
//accept first line of input
//split and parse entries; add to values to variables
if(scn.hasNext()){
strIn = scn.nextLine();
tokens = strIn.split(" ");
nSongs = parseToInt(tokens[0].trim());
nSelects = parseToInt(tokens[1].trim());
arrInput = new ArrayList<Song>(nSongs);
}
//accept and record first song info in input array
if(scn.hasNext()){
strIn = scn.nextLine();
tokens = strIn.split(" ");
//add first song to array
arrInput.add((new Song(parseToInt(tokens[0].trim()), tokens[1].trim(), 0)));
//set quality value to 1
arrInput.get(0).setnQuality(1.0);
//if first song has 0 plays
if(arrInput.get(0).getnPlayNum()==0){
arrInput.get(0).setnPlayNum(1);
}
}
//if only one song is added
if(nSongs==1){
System.
out.
println(arrInput.
get(0).
getSongName()); }
//otherwise, proceed:
else{
Song songIn;
double tempQ;
int i=1;
while (scn.hasNext()) {
strIn = scn.nextLine();
tokens = strIn.split(" ");
//create and add song to array
songIn = new Song(parseToInt(tokens[0].trim()), tokens[1].trim(), i+2);
arrInput.add(songIn);
//calculate quality using:
//q(i) = song(i).plays / (song(0).plays / i )
tempQ = (double)arrInput.get(i).getnPlayNum() / ((double)arrInput.get(0).getnPlayNum() / (double)(i+1));
//set Quality value to current song
arrInput.get(i).setnQuality(tempQ);
i++;
if(i==nSongs){
break;
}
}
//sort array of songs by quality value
//prints only the number of songs defined earlier
for (i = 0; i < nSelects; i++) {
System.
out.
println(arrInput.
get(i
).
getSongName()); }
}
}
System.
out.
println("Exception caught"); System.
out.
println(e.
getStackTrace());
} finally {
if (scn != null) {
scn.close();
}
}
}
//helper method for parsing from String to integer
private static int parseToInt
(String strIn
) { int nRes = -1;
try{
nRes
= Integer.
parseInt(strIn.
trim()); }
System.
out.
println("Error parsing to Integer"); }
return nRes;
}
//PRIVATE SONG UTILITY CLASS
private static class Song implements Comparable<Song> {
//Song Fields
private int nPlayNum;
private int nTrackNum;
private double nQuality;
//Song constructor
public Song
(int nPlayNum,
String songName,
int nTrackNum
){ this.nPlayNum = nPlayNum;
this.songName = songName;
this.nTrackNum = nTrackNum;
}
@Override
public int compareTo(Song o) {
if(getnQuality() > o.getnQuality()){
return -1;
}
if(o.getnQuality() > getnQuality()){
return 1;
}
//if quality values are equal, put songs with lower track numbers first
if(getnTrackNum() < o.getnTrackNum()){
return -1;
}
return 1;
//note: no way to return 0, since songs can't have the same track number
}
//GETTERS SETTERS
public int getnPlayNum() {
return nPlayNum;
}
public void setnPlayNum(int nPlays) {
nPlayNum = nPlays;
}
return songName;
}
public double getnQuality() {
return nQuality;
}
public void setnQuality(double nQuality) {
this.nQuality = nQuality;
}
public int getnTrackNum() {
return nTrackNum;
}
}
/* comment */
}