Here are David Neto's solutions for the Inaugural UTICPC. I've also included the test data used to judge the programs. In each case, these are a superset of the sample inputs and outputs.

I must emphasize that *all* the organizers worked hard to make this an
enjoyable experience. In particular, I'd like to commend Wayne Hayes
on the
excellent job he did in managing the contest judging environment.

I wrote these programs as quickly as I could.
Of course, I already knew the outline of
the solution before I got down to coding.
In most of these source files, I recorded the time I started typing in code
as the first ``date'' line, and the time I finished debugging as
the second ``date'' line.
The text formatting question is an exception
because after almost two hours of trying to solve my original question
(format *multiple* paragraphs),
I gave up and simplified the question instead to have only one paragraph
per run.

You may want to use File-SaveAs-Text option for the test input/output,
especially for the text formatting question. Then use `od -a`
under UNIX.

The base names of the files do not all match the names of the question. But they are in the right order.

- three.c -- The main trick is to notice that you don't have to perform the recursion all the way. Just do it once. The resulting number is no more than 10000.
- master.c -- Here's the
*O(n)*solution. Scan from left to right, maintaining a stack of as-yet unclosed domains of mastery. To simplify things, I defined`PINF`as so-called positive infinity. (I never did need`NINF`which was negative infinity.)Input master2.dat

Output master2.out - fact.c -- Count the number of times
that the factor 5 appears in
*n!*. This does it because there are always enough 2's to match up with the 5's. - prime.c -- This is the
Sieve of Eratosthenes. Keep a table of all the numbers from
2 to 100000 and mark off multiples of primes, where the multiplier
is at least 2. Any unmarked
position must be a prime. Be sure to build the entire table before
processing any input, so that we don't waste time generating
the primes multiple times for multiple inputs.
Also, make sure that we count primes correctly.
Program prime2.c is
a minor ``optimization'' on prime.c.
Two teams wrote other programs that computed the primes, then printed them out and massaged that output to be a program which then was submitted. (In one case it was a 150K Turing program; in the other it was a similarly large C program.) Wayne and I discussed this for a while, and then decided that Rule 3 requires that all submitted code must be "typed" in during the contest, and that therefore these solutions were disqualified. This is the source of the starred entries in the score file. Sorry, but this kind of thing has a precedent: something similar happened to David Neto's team in an ACM regional contest in the fall of 1992. :(

- text.c -- This is all bookkeeping. :)
I also solved it in Turing, see text.t, just before the contest. (I hadn't written a Turing program in a

*long*time...)You don't know how many spaces to print until you know if you've hit the end of the input. So you have to buffer the output line in decomposed form. You must also

*copy*each new word over, instead of just moving pointers, because sometimes the old data will get written over.The number of spaces to be inserted in any particular gap can be computed very nicely by integer division and a remainder.

A common mistake was having extra spaces just before the final newline in the file. See the last line of the specification.

Input 2 text.dat was given

Output 2 text.out

Input 2 text2.dat was given

Output 2 text2.out

Input 3 text3.dat is a cleaned up version of the initial portion of`/usr/dict/words`

Output 3 text3.out

Input 4 text4.dat is an old version of the Latex file describing this question. In it, the output for the second sample case is incorrect. At that point I had a bug in my program. :)

Output 4 text4.out

Input 5 text5.dat is a single word. I apologize here because I had promised that*c>10*. But no rejections were made based on this alone.

Output 5 text5.out

- worf.c -- The answer is always twice the
least common multiple of
*n*and*k*. I won't explain this fully until the next issue of MAT 007I appears.Input worf.dat -- Note that the last line is not used because only 7 inputs are specified. I wanted to keep my promise that no answer would be more than 2 million, so that people who simulated the phaser blast would still have enough time if they weren't too inefficient in coding.

Output worf.out

Back to David Neto's Auxiliary UTICPC page

Back to David Neto's home page