[Problem H | 1994 East-Central Regional problem set | My ACM problem archive | my home page]

There is no zero in the number system. There are separate characters denoting ones, tens, hundreds, thousands, ten-thousands, hundred-thousands, millions and ten-millions. For the purposes of this problem, we use near ASCII equivalents for the symbols:

- | for one (careful, it's a vertical line, not 1)
- n for ten
- 9 for hundred
- 8 for thousand
- r for ten-thousand

Numbers were written as a group of ones preceded in turn by groups of tens, hundreds, thousands and ten-thousands. Thus our number 4,023 would be rendered: ||| nn 8888. Notice that a zero digit is indicated by a group consisting of none of the corresponding symbol. The number 40,230 would thus be rendered: nnn 99 rrrr. (In the Rhind Papyrus, the groups are drawn more picturesquely, often spread across more than one horizontal line; but for the purposes of this problem, you should write numbers all on a single line.)

To multiply two numbers a and b, the Egyptians would work with two columns of numbers. They would begin by writing the number | in the left column beside the number a in the right column. They would proceed to form new rows by doubling the numbers in both columns. Notice that doubling can be effected by copying symbols and normalizing by a carrying process if any group of symbols is larger than 9 in size. Doubling would continue as long as the number in the left column does not exceed the other multiplicand b. The numbers in the first column that summed to the multiplicand b were marked with an asterisk. The numbers in the right column alongside the asterisks were then added to produce the result. Below, we show the steps corresponding to the multiplication of 483 by 27:

| * ||| nnnnnnnn 9999 || * |||||| nnnnnn 999999999 |||| || nnn 999999999 8 |||||||| * |||| nnnnnn 99999999 888 |||||| n * |||||||| nn 9999999 8888888 The solution is: | nnnn 888 r(The solution came from adding together:

||| nnnnnnnn 9999 |||||| nnnnnn 999999999 |||| nnnnnn 99999999 888 |||||||| nn 9999999 8888888.)You are to write a program to perform this Egyptian multiplication.

|| || ||| |||| nnnnnn 9 ||| n n 9 ||| 8

| || || * |||| The solution is: |||| | ||| || |||||| |||| * || n The solution is: || n | * nnnnnn 9 || nn 999 |||| * nnnn 999999 |||||||| * nnnnnnnn 99 8 The solution is: nnnnnnnn 88 | n || nn |||| * nnnn |||||||| nnnnnnnn |||||| n nnnnnn 9 || nnn * nn 999 |||| nnnnnn * nnnn 999999 The solution is: 8 | ||| || |||||| |||| || n |||||||| * |||| nn |||||| n |||||||| nnnn || nnn * |||||| nnnnnnnnn |||| nnnnnn * || nnnnnnnnn 9 |||||||| nn 9 * |||| nnnnnnnn 999 |||||| nnnnn 99 * |||||||| nnnnnn 9999999 || n 99999 * |||||| nnn 99999 8 The solution is: 888

This page maintained by Ed Karrels.

Last updated September 20, 1999