## A. Introduction

This week's lab consists of these three just as a break from our usual boring lab stuff. We've used these contests to select teams for the annual ACM Collegiate Programming Contest. In the Berkeley contests, participants work alone. In the ACM competitions, they work in teams of three (with one terminal between them). Feel free to do it either way (but everyone please submit a solution, even if it is collaborative, being careful, as always to name your fellow solvers).

In the contest finals, teams try to solve collections of these problems (12 in the 2017 contest, held in Rapid City, South Dakota) in a period of 5 hours. Top contenders get very good at it (the Tokyo University team solved its problem in 2015 in 5 minutes!). No, we don't expect this of you, but take it as an indication that the problems are doable.

The skeleton files (`P1.java`

, `P2.java`

, and `P3.java`

) are very skeletal
indeed this time. Input to each program will come from the standard input
(`System.in`

) and output goes to the standard output.

The directories `1`

, `2`

, and `3`

contain test data and expected results,
which `make check`

will use to test your solutions.

## B. Getting Started

Rather than have a lab devoted to current topics in the course, we're going to have a problem-solving lab instead. You won't be graded on how much you complete successfully (as usual), but we do suggest giving it a try. The problems here come from various programming contests. The idea in these contests is to work for speed of programming. Some teams of three at the ACM International Programming Contest, for example, will solve 12 (or even 13) problems like these in five hours.

In all of these problems, the input will come from the standard input and output will go to the standard output.

You'll find (trivial) skeletons and some test data for your answers
in the `lab 8`

directory which you can get by running.

```
git fetch shared
git merge shared/lab8 -m "Get lab8 skeleton"
git push
```

What follows are the instructions for each problem. They begin with a brief description of the problem followed by an illustrative example. At the end of each problem description you will find a table that maps example input (read from stdin) and its corresponding output (to be printed to stdout).

This will require you to write Java code that will read from `System.in`

. A common
class used to read from an input stream in competition programming is the
`BufferedReader`

class. You will want to read the
buffered reader java documentation. You may also refer to
this guide on how to use BufferedReader's `readLine()`

method.

This guide shows how to read from a file. To read from `System.in`

you may
want to look at the `InputStreamReader`

class documentation and look at
how to create one for `System.in`

. Alternatively you can use something called
scanner to replace the `BufferedReader`

and `InputStreamReader`

combination.

## C. (P1) From the Valladolid archives

An imaging device furnishes digital images of two machined surfaces that eventually will be assembled in contact with each other. The roughness of this final contact is to be estimated.

A digital image is composed of the two characters, `'X'`

(marking places
where material is present) and (blank, indicating space).

The first column will always have an `'X'`

in it and
will be part of the left surface. The left surface can extend to the
right as contiguous `X`

s.

Similarly, column $N$ will always have an `X`

in it and will be part of
the right surface, where $N$ is furthest right position of any `X`

over
all rows. The right surface can extend to the left from
column $N$ as contiguous `X`

s. Both surfaces will have the same
vertical extent (the same number of rows), so that there is a section of left
surface and right surface on each row of the image.

For example, here is a possible image (with blanks shown as ):

In this example, each line is 30 characters long

In each row of the image, there can be zero or more blanks separating the left surface from the right surface. There will never be more than a single blank region in any row.

For each image given, you are to determine the total empty area -- the
total number of blanks between the surfaces -- that will exist after
the left surface has been brought into contact with the right surface.
The two surfaces are brought into contact by displacing them strictly
horizontally towards each other until a rightmost `X`

of the left
surface of some row is immediately to the left of the leftmost `X`

of
the right surface of that row. There is no rotation or twisting of
these two surfaces as they are brought into contact; they remain
rigid, and only move horizontally.

The input consists of a series of digital images. Each image consists of
one or more lines of `X`

s and blanks, all having the same length and all
beginning and ending with `X`

. There will be an empty line after
every data set.

For each image in the series, output the total empty area, using the format shown in the example.

## D. (P2) Adapted from the Valladolid archives

Consider binary trees whose nodes are labeled with single digits and letters (upper- and lowercase, case-sensitive).

Given the preorder (root, left subtree, right subtree) node order and the
inorder (left subtree, root, right subtree) node order for the same tree,
it is possible to reconstruct the tree, assuming no two nodes in the tree have
the same label. For example, given the preorder traversal order `DBACEGF`

and the inorder traversal order `ABCDEFG`

you can compute that the tree
these come from is

You are to write a program to do this reconstruction on any such tree.

The input consists of one or more cases in free format. Each case
consists of two non-empty strings *PRE* and *IN*,
representing the preorder traversal and inorder traversal of a non-empty binary
tree, and consisting of letters and digits. Case *is* significant.

For each test case, print the reconstructed tree's postorder traversal (left subtree, right subtree, root), using the format shown in the example.

## E. (P3) Due to E. W. Dijkstra

Consider decimal numerals containing only the digits 1 -- 3. A numeral
is considered **good** if no two adjacent non-empty substrings of it are equal;
otherwise it is **bad**. For example, the numerals `1`

, `12`

, and `1213`

are
good, while `11`

, `32121`

, and `121321312`

are bad.

Write a program that, given $N > 0$, finds the smallest good $N$-digit numeral.

The input consists of a sequence of positive integers. For each of these
integers, $N$, the output is to contain a line of the form.

`The smallest good numeral of length N is S.`