In 1858, A. Henry Rhind, a Scottish antiquary, came into possession of a
document which is now called the Rhind Papyrus. Titled ``Directions
for Attaining Knowledge into All Obscure Secrets", the document provides
important clues as to how the ancient Egyptians performed arithmetic.
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
(The actual Egyptian hieroglyphs were more picturesque but followed the
general shape of these modern symbols. For the purpose of this problem,
we will not consider numbers greater than 99,999.)
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.
Input will consist of several pairs of nonzero numbers written in the Egyptian
system described above. There will be one number per line; each number will
consist of groups of symbols, and each group is terminated by a single space
(including the last group). Input will be terminated by a blank line.
For each pair of numbers, your program should print the steps described
above used in Egyptian multiplication. Numbers in the left column should
be flush with the left margin. Each number in the left and right column will
be represented by groups of symbols, and each group is terminated by a single
space (including the last group). If there is an asterisk in the left column,
it should be separated from the end of the left number by a single space.
Up to the 34th character position should then be filled with spaces. Numbers
in the right column should begin at the 35th character position on the line
and end with a newline character.
Test data will be chosen to ensure that
no overlap can occur. After showing each of the doubling steps, your program
should print the string: ``The solution is: " followed by the product
of the two numbers in Egyptian notation (modulus 100000).
||
||
|||
||||
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
以下用了很醜的代碼,不計時間消耗。
#include <stdio.h>
#include <iostream>
using namespace std;
string int2ch(int n) {
static int i, flag, t;
static int v[6] = {'|', 'n', '9', '8', 'r'};
string r = "";
flag = 0;
for(i = 0; i < 6; i++) {
if(n%10) {
if(flag) r += ' ';
t = n%10;
while(t) r += v[i], t--;
flag = 1;
}
n /= 10;
}
return r;
}
int main() {
int ch2int[127] = {};
ch2int['|'] = 1;
ch2int['n'] = 10;
ch2int['9'] = 100;
ch2int['8'] = 1000;
ch2int['r'] = 10000;
char a[200], b[200];
int i;
while(gets(a)) {
gets(b);
int na = 0, nb = 0, ans;
for(i = 0; a[i]; i++)
na += ch2int[a[i]];
for(i = 0; b[i]; i++)
nb += ch2int[b[i]];
ans = na*nb;
for(i = 0; (nb>>i) > 0; i++) {
string line = int2ch(1<<i);
if((nb>>i)&1)
line += " *";
while(line.length() < 34)
line += ' ';
line += int2ch((1<<i)*na);
cout << line << endl;
}
printf("The solution is: %s\n", int2ch(ans).c_str());
}
return 0;
}
文章定位: