TopCoder problem "StringFragmentation" used in SRM 373 (Division I Level One , Division II Level Two)



Problem Statement

    You are given a String containing a list of words separated by single spaces, with no leading or trailing spaces. You have a panel on which you would like to write these words, in order, possibly over multiple lines. The words must go from left to right within each line, and the lines must go from top to bottom. Each line must contain only complete words, and each pair of adjacent words in a line must be separated by a single space. There must be no leading or trailing spaces.



You must write the words in a font size greater than 7. In a font of size N, the height of each letter is 2*N pixels, and the width of each character (letters and spaces) is N+2 pixels. There is no space between adjacent characters and adjacent lines.



You are given a String text containing the words you must write. The dimensions of the panel in pixels are given in the ints width and height. You are not allowed to rotate the panel. Return the largest integer font size strictly greater than 7 that you can use to write the words on the panel, or -1 if it is impossible.
 

Definition

    
Class:StringFragmentation
Method:largestFontSize
Parameters:String, int, int
Returns:int
Method signature:int largestFontSize(String text, int width, int height)
(be sure your method is public)
    
 

Notes

-If you start a new line between two words, then the space that separated them in the input doesn't get written to the panel.
 

Constraints

-text will contain between 1 and 50 characters, inclusive.
-Each character in text will be an uppercase letter ('A'-'Z') or a space (' ').
-text must be a list of words separated by single spaces, with no leading or trailing spaces, where each word is one or more uppercase letters.
-width and height will be between 1 and 10000, inclusive.
 

Examples

0)
    
"ONE TWO THREE FOUR FIVE"
150
40
Returns: 9
With a font size of 9, we can write "ONE TWO THREE" on the first line and "FOUR FIVE" on the second line. The width of the first line is 13 characters * (9+2) pixels = 143 pixels. The width of the second line is 9 characters * (9+2) pixels = 99 pixels. The total height is 2 lines * (2*9) pixels = 36 pixels. The total size is therefore 143 x 36 pixels, which fits inside the 150 x 40 pixel panel. If you used a font size of 10, it would be 156 x 40 pixels, which would not fit.
1)
    
"ONE TWO THREE FOUR FIVE"
150
60
Returns: 10
Now we can write it in a font size of 10 by separating the text into three lines: "ONE TWO", "THREE", "FOUR FIVE".
2)
    
"ONE TWO THREE FOUR FIVE"
150
10000
Returns: 28
If you write each word on a separate line, you can use a font size of 28. The widest line would be "THREE", which is 150 pixels wide.
3)
    
"ONE TWO THREE FOUR FIVE"
10000
10000
Returns: 1250
4)
    
"ONE TWO THREE FOUR FIVE"
50
50
Returns: -1
5)
    
"A"
9
14
Returns: -1
Note that font size must be strictly greater than 7.

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=8087

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10791&pm=8087

Writer:

Vedensky

Testers:

PabloGilberto , gawry , lovro , ivan_metelsky

Problem categories:

String Manipulation