Billboards

gistfile1.py

import sys

case = 1

def fits_at_size(W, H, size, words):
    cur_row = 0
    cur_col = 0

    for word in S:
        if len(word) * size > W:
            return False

        if cur_col > 0:
            cur_col += 1 # Space

        cur_col += len(word)

        if cur_col * size > W:
            cur_row += 1
            cur_col = len(word)

    return (cur_row + 1) * size <= H

for line in [line.strip() for line in sys.stdin.readlines()[1:]]:
    words = line.split(' ')
    W = int(words[0])
    H = int(words[1])

    S = words[2:]

    soln = None

    for size in range(min(W, H), -1, -1):
        if fits_at_size(W, H, size, S):
            print 'Case #%d: %d' % (case, size)
            break

    case += 1