Not an official ACM page
[ Problem G | 1992 ACM East-Central Regional problem set | My ACM problem archive | my home page]
1992 ACM East Central Regional Programming Contest

Draggin' The Line

A popular speechwriter has recently decided to offer an additional service to her clients. She will transfer the text of the speeches she develops for them onto a series of 3"×5" index cards which they can then use during their presentation. Since she uses a 12-point monospaced font for visual clarity, she is able to get 18 lines of 50 characters onto each card.

Many of her clients prefer to have some room reserved for notes on the top, bottom, or both top and bottom of each index card so that they can add last-minute comments or jot down a few related thoughts with the text on the front of the card just before delivering the speech. Consider the structure of each card as conveyed by the diagram below:

The speechwriter is especially concerned about formatting the index cards to avoid four potential typographical miscues that can affect the number of index cards necessary and, more importantly, their readability for the speaker. These are:

when the last line of a paragraph begun on the previous card appears at the top of the current index card
when the first line of a paragraph continued on the next card appears at the bottom of the current index card
leading blank lines and trailing blank lines
when a blank line which appears between two paragraphs appears at the top or bottom of the current index card

Write a program that will assist the speechwriter by accepting a set of margin parameters and the text of a speech and output a format report detailing which of these typographical miscues will occur if the text is transcribed without further modification onto 3"×5" index cards.


The input file will consis of two integers on a single line followed by the text to be placed onto the index cards. The two integers (which will be separated by at least one space) respectively denote the number of lines which are to be reserved for the top and bottom margins on each card. You may assume that any margin settings given will not overlap and that there will always be enough room left over for at least two lines of text to appear on each index card. The remainder of the file will consist of an unknown number of lines of text from the speechwriter. Each line of text will have already been formatted so that it consists of zero to fifty characters, not counting a standard carriage return character which will be used to terminate each line. Paragraphs are delineated by exactly one blank line and will always contain at least two lines of text.


Your output will consist of a formatting report detailing the formatting errors (if any) which would appear on each index card. Each line of the report should indicate the index card number and the formatting error (widow, orphan, leading blank line, or trailing blank line) or the letters OK if none of these formatting errors is present. Should multiple formatting errors occur on a single index card, these errors must be indicated across the output line in the order in which they occur on the card (top to bottom), with each error separated by a comma and a space from the one preceding it. Refer to the example on the next page.

Sample Input

3 5
Why multiprocessing? Some computer systems employ
a uniprocessor approach, in which a single
processor performs the work. Multiprocessing
systems (systems that employ two or more
processors) offer a number of advantages over
uniprocessors.  The most obvious is speed.

     In theor, if a single processor can solve a
problem in a given length of time, two identical
processors working together should be able to
solve the same problem in half of the time.

     In practice, the nature of the problem of the
design of the multiprocessing system may not
provide such an ideal result. But there are many
applications which show nearly linear speedups in
processing speed as more processors are provided.

Potential speedups from multiprocessing are even
more attractive in light of recent developments in
technology. The preformance of processors is
increasing, while their price is dropping. System
performance is being boosted by improvements in
hardware design and programming techniques.

    Multiprocessing also offers a level of system
reliability not found in uniprocessor system.  If
a processor fails, it can be quickly deconfigured
while the remaining processors pick up its work.

There are two basic approaches to multiprocessing
evident in commercial systems today. Distributed
memory multiprocessor systems usually consist of
from eight to several thousand processors, each
of which has its own memory. Processors typically
communicate with each other only to read initial
code and data, and to write final results. This is
termed loose-coupling.

The other common approach is called the shared-
memory approach. These systems typically employ
2 to 30 processors and use a common memory, all
linked by a high-speed bus. This design is called
tightly-coupled, since the processors must all
coordinate their access to the common memory.

Output for the Sample Input

Index Card #1:     OK
Index Card #2:     orphan
Index Card #3:     trailing blank line
Index Card #4:     widow
Index Card #5:     OK

This page maintained by Ed Karrels.
Last updated December 12, 1999