Programming Contest World Finals

Problem H

Towers of Powers

File: towers.cc

One of the many problems in computer-generated graphics is realistically modeling the "orderly randomness" of things like mountain ranges and city skylines. A new student intern at a graphics company had an ideanumber representations to model height. In this ¡ªuse fluctuations in problem you will compute several such number representations and show the they produce.¡°skylines¡±

Let *n* be any positive
integer, and let *b* be an integer greater than or equal to 2. The
*complete
base-b expansion of n* is obtained as follows. First write the usual
base-*b* expansion of *n*, which is just a sum of powers of *b*,
each multiplied by a coefficient between 1 and *b-*1, omitting terms
with zero coefficients. For example, if *n* = 20000 and *b* =
3, the base-3 expansion of 20000 is given by

9 5 3 2 20000 = 3 + 3 + 2*3 + 2*3 + 2

To obtain the complete base-*b*
expansion, we apply the same procedure to the exponents until all numbers
are represented in base *b*. For
*n* = 20000 and *b*= 3
we would have

2 3 3+2 3 2 20000 = 3 +3 +2*3 +2*3 +2As another example, consider

2+1 2 2+1 2 +2 +2 2 2 16647 = 2 +2 +2 +2+1The rising and falling heights of the numbers form the number's "skyline."

For each pair of integers
*n*
and *b* in the input, display the complete base-*b* representation
of *n*. Your display should use multiple output lines for different
exponent heights The display must begin with *n* = , followed by the
expansion. Answers should use an asterisk (*) as the multiplication symbol
between coefficients and powers of b. Zero terms must not be printed, and
unnecessary coefficients and exponents must not be shown (for example,
display 1 instead of b^0,
*b^2* instead of 1**b^2*
and
*b* instead of *b^1 -- note that the caret
symbol has been used here only to simplify the display of this page in
HTML, your output will use the raised powers shown above and in the examples*).
To assist in accurately viewing the skyline of the number, the display
must show one character (either a digit, +, or *) per column of the multi-line
display; there must be no unnecessary spaces. The correct format is illustrated
in the sample output below.

Answers must be displayed
using no more than 80 columns. Expansions requiring more than 80 columns
must be split after the last complete term that ends before reaching 81
columns, i.e. after the last term residing on the __lowest__ display
line. A second set of display lines (and the same number of display lines)
should be used to show the remaining portion of the expansion. The second
part of the answer must begin in the same column as the previous part of
the answer. There will not be more than one such split required for each
input pair. See the sample output for an example.

**Input**

Input is a sequence of pairs
of integers, *n* and *b*, followed by a pair of zeroes. Each
value for *n* will be positive, and each value for *b* will be
greater than or equal to 2. No value will exceed the maximum signed integer
size for the machine.

**Output**

For each input pair, *n*
and *b*, print the complete base-*b* expansion of *n* as
described above. Print a line containing

preceding each expansion. Follow this withe a blank line, the first display line. End each output with a line of 80 hyphens. All coefficients, bases, and exponents are to be displayed as standard base 10 integers. Be sure there are no extra spaces after the characters on each display line or the introductory line.nin complete baseb:

**Sample Input**

20000 3

16647 2

1000 12

85026244 3

0 0

**Output for the Sample Input**

20000 in complete base 3: 2 3 3+2 3 2 20000 = 3 +3 +2*3 +2*3 +2 -------------------------------------------------------------------------------- 16447 in complete base 2: 2+1 2 2+1 2 +2 +2 2 2 16647 = 2 +2 +2 +2+1 -------------------------------------------------------------------------------- 1000 in complete base 12: 2 1000 = 6*12 +11*12+4 -------------------------------------------------------------------------------- 85026244 in complete base 3: 2 2 2 2 2 2 2 3 +2*3+1 3 +2*3 3 +3+2 3 +3+1 3 +2 3 +1 3 85026244 = 3 +2*3 +2*3 +2*3 +2*3 +2*3 +2*3 2*3+2 2*3+1 3 +2*3 +3 +2*3 +3+1 --------------------------------------------------------------------------------