2011年10月29日 星期六

276 - Egyptian Multiplication

埃及的數字系統與阿拉伯數字系統並不相同,埃及數字以不同符號表示一,十,佰,仟,萬,十萬,佰萬,仟萬,本題以ASCII字元表示如下:
  • | 表示一(注意 | 並不同於 1)
  • n 表示十。
  • 9 表示佰。
  • 8 表示仟。
  • r 表示萬。
(本題不討論大於99,999的數目)

數字的表示方式很簡單,以4,023為例,共有3個一、兩個十、零個佰、四個仟,表示成 ||| nn 8888。位數為零的符號不需要寫出來。40,230的埃及數字寫成:nnn 99 rrrr。

對於兩個數字 a 與 b 的乘法而言,埃及數字的乘法運算式以兩欄數字表示,第一列的左欄數字為 |,右欄數字為 a,接下來每一列兩欄的數字為上一列的兩倍,所以下一列可簡單地將上一列的每一組數字乘兩倍而得到,且當數量大於九時作進位。左欄的數字不斷乘上兩倍,且到不超過 b 為止。從左欄的數字中選擇部份的數字做加總使之等於 b,並在被選擇的數字後打上星號(*),將所有打上星號的每一列的右欄數字加總即為 a * b 的值。
下列顯示 483 * 27 的運算過程:
| *                             ||| nnnnnnnn 9999
|| *                            |||||| nnnnnn 999999999
||||                            || nnn 999999999 8
|||||||| *                      |||| nnnnnn 99999999 888
|||||| n *                      |||||||| nn 9999999 8888888
The solution is:  | nnnn 888 r
總和為 | nnnn 888 r,為下列埃及數字的總和:
||| nnnnnnnn 9999
|||||| nnnnnn 999999999
|||| nnnnnn 99999999 888
|||||||| nn 9999999 8888888
本題請你寫一個程式來作埃及數字的乘法運算。

Input

測試資料兩列一組,分別以埃數數字表示兩個大於零的數字。以空行表示測試資料結束。

Output

請對每組測試資料輸出埃及數字的乘法運算過程,左欄請靠左輸出,每個數字的每個位數符號之後皆必須有一個空白字元,包含最後的位數。請以空白字元填滿左欄的輸出,並在第35個字元位置開始輸出右欄的數字。

請參考範例資料格式,本題的測試資料可以保證不會有字元重疊的問題,請在每組的最後輸出"The solution is: "並接著以埃及數字輸出其乘數(請取除100000的餘數)。

Sample Input

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

Sample Output

|                                 || 
|| *                              |||| 
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

原文出處

沒有留言:

張貼留言