Not an official ACM page
[Problem 4
| 1997 East-Central problem set
| Ed's programming contest problem archive
| my home page]
ACM East Central Region
1997 Regional Programming Contest
Problem 3 - Critical Mass
During the early stages of the Manhattan Project, the dangers of the new radioctive
materials were not widely known. Vast new factory cities were built to manufacture
uranium and plutonium in bulk. Compounds and solutions of these substances were
accumulating in metal barrels, glass bottles and cardboard box piles on the
cement floors of store rooms. Workers did not know that the substances they were
handling could result in sickness, or worse, an explosion. The officials who
knew the danger assumed that they could ensure safety by never assembling any
amount close to the critical mass estimated by the physicists. But mistakes were
made. The workers, ignorant of the the dangers, often did not track these
materials carefully, and in some cases, too much material was stored together--an
accident was waiting to happen.
Fortunately, the dangers were taken seriously by a few knowledgeable physicists.
They drew up guidelines for how to store the materials to eliminate the danger
of critical mass accumulations. The system for handling uranium was simple.
Each uranium cube was marked "U". It was to be stacked with lead cubes (marked "L")
interspersed. No more than two uranium cubes could be next to each other on a
stack. With this simple system, a potential for the uranium reaching critical mass
(three stacked next to each other) was avoided. The second constraint is that no
more than thirty cubes can be stacked on top of each other, since the height of
the storage room can only accommodate that many. One of the physicists was still
not completely satisfied with this solution. He felt that a worker, not paying
attention or not trained with the new system, could easily cause a chain reaction.
He posed the question: consider a worker stacking the radioactive cubes and non
radioactive cubes at random on top of each other to a height of n cubes;
how many possible combinations are there for a disaster to happen?
For example, say the stack is of size 3. There is one way for the stack to reach
critical mass--if all three cubes are radioactive.
1: UUU
However, if the size of the stack is 4, then there are three ways:
1: UUUL
2: LUUU
3: UUUU
Input
The input is a list of integers on separate lines. Each integer corresponds
to the size of the stack and is always greater than 0. The input is terminated
with a integer value of 0.
Output
For each stack, compute the total number of dangerous combinations where each
cube position in the linear stack can either be "L" for lead, or "U" for uranium.
Output your answer as a single integer on a line by itself.
Sample Input
4
5
0
Output for the Sample Input
3
8
This page maintained by
Ed Karrels.
Last updated December 10, 1999