HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Sections > Search > problem:


50784 - Top Growing Company

Guest
• Review clarifications (1)

Section problems

• 50834 - The train which leaves the f...
• 51046 - The biggest number
• 50453 - The Cubic Difference
• 50451 - Processing Cost
• 50538 - Sum of kth Diagonal
• 50535 - Image Compression
• 50470 - Close Pairs - Revised
• 50459 - The Biggest Digit
• 50784 - Top Growing Company
• 50791 - Mine field
• 50867 - Average of the Best Grades
• 50460 - Median of 3 Numbers
• 50566 - Grade Point Average (GPA)
• 50573 - Count and Sum
• 50575 - Number of Prime numbers
• 50576 - Number of Perfect numbers
• 50588 - Processing the list of numbers

Feedback

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

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:

  1. There can be many companies sharing the same position in a year.
  2. 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.
  3. 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


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

www.contester.ru