Problem statement:
We are starting preparations for Hacker Cup 2013 really early. Our
first step is to prepare billboards to advertise the contest. We have
text for hundreds of billboards, but we need your help to design them.
The billboards are of different sizes, but are all rectangular. The
billboard widths and heights are all integers. We will supply you with
the size in inches and the text we want printed. We want you to tell
us how large we can print the text, such that it fits on the billboard
without splitting any words across lines. Since this is to attract
hackers like yourself, we will use a monospace font, meaning that all
characters are of the same width (e.g.. ‘l’ and ‘m’ take up the same
horizontal space, as do space characters). The characters in our font
are of equal width and height, and there will be no additional spacing
between adjacent characters or adjacent rows. If you print a word on
one line and print the next word on the next line, you do not need to
print a space between them.
Let’s say we want to print the text “Facebook Hacker Cup 2013″ on a
350×100″ billboard. If we use a font size of 33″ per character, then
we can print “Facebook” on the first line, “Hacker Cup” on the second
and “2013″ on the third. The widest of the three lines is “Hacker
Cup”, which is 330″ wide. There are three lines, so the total height
is 99″. We cannot go any larger.
Input
The first line of the input file contains a single integer T: the
number of test cases. T lines follow, each representing a single test
case in the form “W H S”. W and H are the width and height in inches
of the available space. S is the text to be written.
Output
Output T lines, one for each test case. For each case, output “Case
#t: s”, where t is the test case number (starting from 1) and s is the
maximum font size, in inches per character, we can use. The size must
be an integral number of inches. If the text does not fit when printed
at a size of 1″, then output 0.
Constraints
1 ? T ? 20
1 ? W, H ? 1000
The text will contain only lower-case letters a-z, upper-case letters
A-Z, digits 0-9 and the space character
The text will not start or end with the space character, and will
never contain two adjacent space characters
The text in each case contains at most 1000 characters
Example input
5
20 6 hacker cup
100 20 hacker cup 2013
10 20 MUST BE ABLE TO HACK
55 25 Can you hack
100 20 Hack your way to the cup
Example output
Case #1: 3
Case #2: 10
Case #3: 2
Case #4: 8
Case #5: 7
Solution:
Since the width and height are fairly small, simulation is feasible.
Solve the problem by iterating font size from 1 until the billboard
cannot contain all the words. Fill the billboard line by line.
import java.io.File; import java.io.FileNotFoundException; import java.util.Scanner; public class Billboards { public static void main(String[] args) throws FileNotFoundException { Scanner sc = new Scanner (new File(args[0])); int t = sc.nextInt(); for (int i=1; i<= t; i++) { int w = sc.nextInt(); int h = sc.nextInt(); sc.skip(" "); String s = sc.nextLine(); String[] sa = s.split(" "); int size = 0; for (int j=1; j<10000; j++) { int saPtr = 0; int currH = h; while (true) { currH -= j; if (currH < 0) break; int currW = w; while (currW >= (sa[saPtr].length()*j) ) { currW -= sa[saPtr].length()*j; currW -= j; saPtr++; if (saPtr == sa.length) { size = j; break; } } if (size == j) break; } if (size < j) break; } System.out.println("Case #"+i+": "+size); } } }
Posted via email from ramblings of a comsci student
![[del.icio.us]](http://images.del.icio.us/static/img/delicious.small.gif){kind=small}
