Devil Game
InterviewTime limit1sMemory limit256 MB
Find a dictionary word containing the original word as a subsequence and maximize mood-killing degree per inserted letter, breaking ties by input order.
- Level
Medium4 of 10
- Topics
- String, Two pointers, Greedy
- Solved
- No attempts yet
Problem
Devil Game is an RPG made by Frost Entertainment, and it has reached its third installment. Thanks to its excellent game design, Devil Game has a large fan base.
A few days ago, there was a Devil Game development announcement event. The developers had been dropping hints about a new game for a long time, so the fans were excited. The fans were all shouting at the top of their lungs for the release of ‘Devil IV’.
The day of the development announcement event finally arrived. When the host put ‘Devil IV’ on the screen, the audience cheered. But the cheer was short-lived. The moment a single stroke was drawn after ‘Devil IV’, turning it into ‘Devil IVI’, the mood of the event turned cold in an instant. Unable to accept the sudden turn of events, the fans began to get angry. The mood at that moment can be explained by a single question one fan shouted: ‘Is this a belated April Fools’ joke?’
Dongyeop, a longtime fan of Devil Game, was shocked by that incident and wants to use it in a team presentation. First, he will put an interesting word on the ppt to draw the audience’s attention, and then insert a few letters at the start, end, or middle of the word to make the mood awkward.
Dongyeop has a ‘mood-killer dictionary’. He will make a word from the dictionary out of the original word to freeze the mood. The words in the dictionary each have a different degree of mood-killing, and Dongyeop wants to make the word with the greatest degree of mood-killing. However, since inserting too many letters is not fun, Dongyeop wants to choose the word with the greatest ratio of mood-killing degree to the number of added letters. Write a program to help Dongyeop choose a word.
Input
The first line gives the original word m that Dongyeop finds interesting.
The second line gives the number N of words in the mood-killer dictionary. (1 ≤ N ≤ 100)
Across the following N lines, the words in the mood-killer dictionary are given, each line containing the word w and its mood-killing degree g, separated by a space. (1 ≤ g ≤ 10,000)
Every word consists only of uppercase letters and has a length between 1 and 100.
The original word and the dictionary words are all different from each other.
Output
On the first line, print the word with the greatest ratio of mood-killing degree to the number of inserted letters.
If multiple such words exist, print the one that appears first in the mood-killer dictionary.
If no such word can be made, print "No Jam" without the quotation marks.