DMOPC '14 Contest 3 P3 - Not Enough Personnel!

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem type

Amagi Brilliant Contests runs a business making and hosting contests on its online platform to competitive programmers who want to run their own contests.

On the last contest they hosted, there were simply not enough staff members to staff all of the judging servers. For the next time around, the management decided to enslave hire more personnel. But prospective employees come with all levels of management and technical know-how. Particularly, every employee has a potentially non-unique skill level s (0 \le s \le 1\,000), and there are Q (1 \le Q \le 100) newly-hired employees.

Since the management wishes to minimize the cost of potential mistakes, they've decided to pair each new employee with a veteran employee so that they can be shown the ropes. There are N (1 \le N \le 500) veteran employees.

Each new employee has an adaptability factor d (1 \le d \le 100), and must be paired with a veteran whose skill level is at most d higher than their own: any lower and they would not learn anything, and any higher and the teacher would be overly cocky. In other words, the skill level of the teacher has to be at least as much as the current skill level and at most that quantity + d. The same veteran employee may teach multiple new employees. If multiple veterans satisfy these conditions, the employee should be paired with the veteran closest to their skill level. If there is still more than one choice, the new employee should be paired with the one that is given first in the input.

Being the head of the human resources department at Amagi Brilliant Contests, you've been tasked with pairing each new employee with an existing employee.

Input Specification

The first line of input will have N, the number of existing employees.

Each of the next N lines will have the name of an existing employee (which is no longer than 20 uppercase and/or lowercase letters of the alphabet), and their skill level s, separated by a single space.

Line N+2 will have Q, the number of new employees.

Each of the next Q lines will have the skill level s of the new employee, along with their adaptability factor d.

Output Specification

The name of the employee they should be paired with, or No suitable teacher! if none exists.

Sample Input 1

Kanie 1000
Moffle 800
Sento 950
Macaron 550
Tirami 500
930 20
400 150
790 15

Sample Output 1


Sample Input 2

Muse 203
Sylphy 202
Koboli 202
Salama 999
200 1
200 3

Sample Output 2

No suitable teacher!


There are no comments at the moment.