HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Contests > CEN254 Final Exam > problem:


4. 51145 - Graduation Exam

CEN254 Final Exam

Start: June.23.2017 at 12:25:00 PM
Finish: June.23.2017 at 01:25:00 PM
The contest is finished!
• Contest scoreboard

Contest problems

• 1. 51142 - Jump Min Value
• 2. 51143 - Departments Competition
• 3. 51082 - Sum is equal to K - 1
• 4. 51145 - Graduation Exam

Feedback

If you notice incorrect translations in Contester, please let author know.

Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
Question by Ibrahim Mesecan.

Graduation Exam

There is 'Student Graduation and Assessment Test' (SGAT) for students every year in a country. The ministry of education follows the results carefully to measure the success of students; schools; or cities. Every year, they give certificates to the most successful students. This year, they want to give certificate also to the students who show the biggest change (development) in their last two results.

Question: Write a program that is going to get information for n students for last year and this year SGAT exams. Then, the program will find out top m students who show the biggest increase.

Input specification
You will be, first, given two integers: the number of students (n); and the number of top students to list where 1 ≤ m ≤ n ≤ 60,000. Then in the following n lines, you are given two information for each student: Student ID (SID) and the position taken from last year SGAT.

Following n lines list for SGAT results for this year. This second list is sorted according their SGAT results this year (first student got the first place in SGAT this year). SID starts with a letter and contains upto 8 digit numbers.

Output specification:
Show the SIDs of most developing m students.
Notes:

  1. There can be several students in the same position because they have the same results.
  2. Some students may not be present in previous year list or may be present in the last year's list but not present in this year's list. In this case, all students missing in last year SGAT list are counted as having the position (n+1)th position.
  3. If there are several students whose position increase the same number of steps up, then show them in ascending order according to SID.

Sample Input Sample Output
5 3
E7182 3
S4673 5
S9990 4
X6509 1
Z8998 1
E7182
S4673
Z8998
N2793
X6509
 		S4673
E7182
N2793

Explanation: There are three students who has increased his/her position: S4673, E7182 and N2793. And, S4673 is the top most growing company.

  • S4673 has changed 3 positions up
  • E7182 has changed 2 positions up
  • N2793 has changed 2 positions up
  • Z8998 has changed 2 positions down
  • X6509 has changed 4 positions down
N2793 was not in the list of last year and this year appears in the 4 fourth position (2 positions up). S9990 was in the list of last year, but not in this year. Thus, S4673 is the most developing student. Students E7182 and N2793 both has increased their positions up 2. Thus, they are in ascending SID order.


Для отправки решений необходимо выполнить вход.

www.contester.ru