Connection Status:
Competition Arena > StringFragmentation

StringFragmentation

SRM 373 · 2007-10-23 · by Vedensky

SRM 373 · 2007-10-23 · by Vedensky · String Manipulation
Class Name: StringFragmentation
Return Type: int
Method Name: largestFontSize
Arg Types: (string, int, int)
Problem Statement

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.

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.

6)
"A"
10000
10000
Returns: 5000

max answer

7)
"A BB CCC A BB A BB CCC A BB CCC A A CCC BB A BB A"
200
200
Returns: 16

many splits possible

Submissions are judged against all 95 archived test cases, of which 8 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class StringFragmentation with a public method int largestFontSize(string text, int width, int height) · 95 test cases · 2 s / 256 MB per case

Submitting as anonymous