PKU 1653 - Compacting Stickers

Autor da análise: dinakdinak

Link: http://acm.pku.edu.cn/JudgeOnline/problem?id=1653

Resumo

Dado um texto de entrada, inserir quebras de linha de modo que um quadro que emoldure o texto, tenha a menor área possível.

Detralhes:
— nesse quadro, deve-se adicionar duas unidades de comprimento na largura e na altura, representando as margens;
— uma quebra de linha não pode separar uma palavra de sua pontuação (existe no máximo uma pontuação após cada palavra);
— o enunciado tem um problema, de fato, não existe um inteiro no início indicando a quantidade de linhas.

Solução

Li uma linha por vez, para cada linha separei as palavras por tokens (' ' e \n). Para cada palavra fui armazenando o tamanho dela. Se eu achar uma pontuação, não armazeno seu tamanho, mas adiciono 1 no tamanho da palavra anterior (não preciso me preocupar com o início, a entrada nunca começa com pontuação).

Feito isso procuro o maior tamanho nesse vetor e armazeno x = maxTam + 2, que será a largura inicial do quadro a partir da qual eu vou começar a procurar. Assim, vou incrementando x e tentando encaixar os tamanhos em cada linha, no fim consigo a altura. Basta eu ir mantendo a menor área alcançada. O processo termina quando a altura for igual a 3 (todo o texto em apenas uma linha + 2 das margens).

Testes

Entrada

Many copies of the sticker are to be
printed, and to minimize paper
consumption the sticker should be made as small
in area as possible . Consider , for example, the
sticker
with the following text
!
Our pink elephants have great size and a small price. Buy our elephants?

Saída

360

Enquete

Qualidade do enunciado

Dificuldade do problema

Problema interessante

Discuta o problema

Add a New Comment
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License