Challenge 03: Largest Font Size

The year is 2012 and your programming challenge skills have landed you a job at Microsoft on the Powerpoint team. Some people think that a Powerpoint presentation should have a lot of text on each slide, and it is your job to help them. You need to build an Autofit feature that will take the dimensions of a slide and a string of text, and will output the largest font size that will fit that text in the slide.

For any given font size n, assume that each character is n pixels tall. However, different characters can have different widths. Each character is assigned a multiplier, which when mulitplied with the font size gives its width in pixels (round down if it is not an even number). For example, if a has a multiplier of 1.1, it will be 11 pixels wide when the font size is 10 (1.1 * 10 = 11) and 13 pixels wide when the font size is 12 (1.1 * 12 = 13.2). You can assume the smallest possible font is 1, and the largest is the height of the slide. If the text cannot fit on the slide at all, print 0.

Input

The input will start by giving the weights of all the characters. For simplicity, only lower case letters will be used. The following lines will consist of the height and width of a slide, followed by the text that must be fitted to it.

Example Input

a 1.2
b 1.1
c 0.9
d 1.1
e 1.3
f 1.0
g 1.2
h 1.2
i 0.9
j 1.0
k 1.1
l 0.9
m 1.5
n 1.3
o 1.2
p 1.2
q 1.2
r 1.3
s 1.3
t 1.2
u 1.2
v 1.1
w 1.6
x 1.3
y 1.3
z 1.4
50 100 anyprogramisonlyasgoodasitisuseful
10 10 helloworld
1 1 johnisthebesttainthewholewideworld

Output

Your output should be the largest font size for each input string (or 0), separated by new lines.

Example Output

10
3
0

Submission

To submit your work, follow the same procedure you used for Reading 00:

$ cd path/to/cse-30872-fa17-assignments     # Go to assignments repository
$ git checkout master                       # Make sure we are on master
$ git pull --rebase                         # Pull any changes from GitLab

$ git checkout -b challenge03               # Create and checkout challenge02 branch

$ $EDITOR challenge03/program.cpp           # Edit your code

$ git add challenge03/program.cpp           # Stage your changes
$ git commit -m "challenge03: done"         # Commit your changes

$ git push -u origin challenge03            # Send changes to GitLab

To check your code, you can use the .scripts/submit.py script or curl:

$ .scripts/submit.py
Submitting challenge03 assignment ...
Submitting challenge03 code ...
  Result Success
   Score 6.00

$ curl -F source=@challenge02/program.cpp  https://dredd.h4x0r.space/code/cse-30872-fa17/challenge03
{"score": 6, "result": "Success"}

Once you have commited your work and pushed it to GitLab, member to create a merge request. Refer to the Reading 02 TA List to determine your corresponding TA for the merge request.