Not an official ACM page
[Problem C
| 1995 East-Central problem set
| My ACM problem archive
| my home page]
1995 East-Central Regionals
ACM International Collegiate programming Contest
sponsored by Microsoft
Problem B - Up and Down Sequences
The quality of pseudo random-number generators used in some computations, especially simulation, is a
significant issue. Proposed generation algorithms are subjected to many tests to establish their quality, or,
more usually, their lack of it. One of the common tests is the run test.
In this test, sequences are tested for "runs up" and "runs down."
We will examine series of data values for the "Up" and "Down" sequences each series contains.
Within a series, an "Up" sequence continues as long as each data-value received is not less than the previous data-value.
An "Up" sequence terminates when a data-value received is less than the previous
data-value received.
A "Down" sequence continues as long as each data-value received is not greater than the previous data-value.
A "Down" sequence terminates when a data-value received is greater than the previous data-value
received.
An "Up" sequence can be initiated by the termination of a "Down" sequence and vice versa. (Sequences
initiated in this manner have length one at this initiation point.)
All the initial data-values are part of an "Up" sequence, and contribute to its length, if the first deviation of
the data-values is upwards.
All the initial data-values are part of a "Down" sequence, and contribute to its length, if the first deviation of
the data-values is downwards.
If the data-values received don't allow classification as either an "Up" or a "Down" sequence, the data
should be considered to have neither sequence.
Find the average length of both the "Up" and the "Down" sequences encountered for each input line in the
data file. Report these average lengths as each input line is processed.
Input
- Each of the separate series to be examined is contained on a single line of input.
- Each series to be analyzed consists of at least one and no more than 30 unsigned, non-zero integers.
- Each integer in a series has at least one digit and no more than four digits.
- The integers are separated from each
other by a single blank character.
- Each of the series will be terminated by a single zero (0) digit. This terminator
should not be considered as being part of the series being analyzed.
- The set of series to be analyzed is terminated by a single zero (0) digit as the input on a line. This terminator
should not be considered to be a series, and no output should be produced in response to its encounter.
Output
Aline with two real values is to be emitted for each input data set encountered. First, the average "Up" run
length, then the average "Down" run length. Separate these values with one or more spaces. The default real/float
output format should be used. Non-zero answers must be within 0.1% of the correct answer. Zero-valued
answers must be within +/- 0.001.
Sample Input
1 2 3 0
3 2 1 0
1 2 3 2 1 0
2 2 2 2 3 0
4 4 4 4 3 0
4 4 4 3 3 3 3 0
4 4 4 3 3 3 4 0
5 5 5 5 0
1 2 3 2 3 4 5 0
0
Output for the Sample Input
2.000 0.000
0.000 2.000
2.000 2.000
4.000 0.000
0.000 4.000
0.000 6.000
1.000 5.000
0.000 0.000
2.500 1.000
This page maintained by
Ed Karrels.
Last updated November 6, 1997