HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Sections > Search > problem:


50784 - Top Growing Company

Guest
• Review clarifications (1)

Section problems

• 50457 - The Number of Winners
• 50453 - The Cubic Difference
• 50451 - Processing Cost
• 50459 - The Biggest Digit
• 50538 - Sum of kth Diagonal
• 50465 - How many students have p...
• 50378 - Sum of the given digits
• 50470 - Close Pairs - Revised
• 50784 - Top Growing Company
• 50458 - Weekly Report
• 50478 - Letter Grades
• 50791 - Mine field
• 50867 - Average of the Best Grades
• 50782 - Max of N integers
• 50460 - Median of 3 Numbers
• 50552 - Casual shoes
• 50558 - Biggest Barn

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