Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
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:
- There can be several students in the same position
because they have the same results.
- 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.
- 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.
Для отправки решений необходимо выполнить вход.
|