Climbing the Leaderboard -ALGORITHM
Climbing the Leaderboard
Alice is playing an arcade game and wants to climb to the top of the leaderboard. Can you help her
track her ranking as she beats each level? The game uses Dense Ranking, so its leaderboard works
like this:
track her ranking as she beats each level? The game uses Dense Ranking, so its leaderboard works
like this:
- The player with the highest score is ranked number on the leaderboard.
- Players who have equal scores receive the same ranking number, and the next player(s) receive
- the immediately following ranking number.
For example, four players have the scores , , , and . Those players will have ranks , , , and ,
respectively.
respectively.
When Alice starts playing, there are already people on the leaderboard. The score of each player
is denoted
by . Alice plays for levels, and we denote her total score after passing each level as .
After completing each level,
Alice wants to know her current rank.
is denoted
by . Alice plays for levels, and we denote her total score after passing each level as .
After completing each level,
Alice wants to know her current rank.
You are given an array, , of monotonically decreasing leaderboard scores, and another array, ,
of Alice's cumulative scores for each level of the game. You must print integers. The integer
should indicate the current rank of
alice after passing the level.
of Alice's cumulative scores for each level of the game. You must print integers. The integer
should indicate the current rank of
alice after passing the level.
Input Format
The first line contains an integer, , denoting the number of players already on the leaderboard.
The next line contains space-separated integers describing the respective values of .
The next line contains an integer, , denoting the number of levels Alice beats.
The last line contains space-separated integers describing the respective values of .
The next line contains space-separated integers describing the respective values of .
The next line contains an integer, , denoting the number of levels Alice beats.
The last line contains space-separated integers describing the respective values of .
Output Format
Print integers. The integer should indicate the rank of alice after passing the level.
Sample Input 0
7
100 100 50 40 40 20 10
4
5 25 50 120
Sample Output 0
6
4
2
1
Explanation 0
Alice starts playing with players already on the leaderboard, which looks like this:
After Alice finishes level , her score is and her ranking is :
After Alice finishes level , her score is and her ranking is :
After Alice finishes level , her score is and her ranking is tied with Caroline at :
After Alice finishes level , her score is and her ranking is :
PROGRAM CODE:
import java.util.*;
/**
* @author kuttyselva
*/
public class Hacker_leaderboard {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int scores_i;
int prev_score = in.nextInt();
int curr_score;
List<Integer> dense_ranks = new ArrayList<>();
dense_ranks.add(prev_score);
for(scores_i = 1; scores_i < n; scores_i++) {
curr_score = in.nextInt();
if (curr_score < prev_score)
{
dense_ranks.add(curr_score);
prev_score = curr_score;
}
}
int m = in.nextInt();
int alice_i;
int alice_score;
int ranks_i = dense_ranks.size()-1;
for(alice_i = 0; alice_i < m; alice_i++) {
alice_score = in.nextInt();
while (ranks_i > 0 && alice_score > dense_ranks.get(ranks_i)) {
ranks_i--;
}
if (alice_score >= dense_ranks.get(ranks_i)) {
System.out.println(ranks_i + 1);
} else {
System.out.println(ranks_i + 2);
}
}
in.close();
}
}
0 comments:
Post a Comment