Time limit 5000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
Question by Ibrahim Mesecan.
Top Growing Company
Binary Search
President of Babylon country prepares Forte Ones List (FOL)
every year, top n companies of the country . This year,
the government wants also to see the top growing company,
the company which has increased its position the most.
Question:
Write a program that is going to read Company
Identification Numbers (CIN) for n companies
for last year and this year. Then, the program
will find out the most growing company.
Input specification
You will be given an integer number (n), the number
of companies in the lists where 1 ≤ n ≤ 60,000.
Then in the following n lines,
you will have two information for each company: CIN
and the position in the last year FOL. And, the list
for last year is in ascending order of CINs.
Then, the following n lines will give the list for
this year. This second list is sorted according their
orders in this year. That is, first appearing company
is the top company in this year.
Company Identification Numbers start with a letter
and contain upto 8 digit numbers.
Output specification:
Show the CIN of the top growing company.
Note:
- There can be many companies sharing the same
position in a year.
- Some companies may not be present in the 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 companies missing in the list of last year's FOL are
counted as having the (n+1)th position.
- If there are several companies which has climbed the
same number of steps up, then show the company
with the smallest position in this year.
Sample Input
5
E7182 3
S4673 5
S9990 4
X6509 2
Z8998 1
E7182
S4673
Z8998
N2793
X6509
|
Sample Output
S4673
|
Explanation: There are two companies
which has climbed up: E7182 and S4673. And, S4673 is the top most
growing company.
- E7182 was in the 3rd position and has climbed 2 steps up
- S4673 was in the 5th position and has climbed 3 steps up
- Z8998 was in the 1st position and it has fallen 2 steps down
- N2793 was not in the list that is it has climbed 2 steps up
- X6509 was in the 2nd position and it has fallen 3 steps down
Для отправки решений необходимо выполнить вход.
|