## 276 - Egyptian Multiplication

All about problems in Volume 2. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

ganza
New poster
Posts: 4
Joined: Wed Oct 17, 2001 2:00 am
Location: Portugal
Contact:
Hi!

I've sent that problem to judge and got WA

What should be done when a multiplication of a pair exceeds 99999?

Thanks,
Nuno Teixeira

PS: This board is great!! No more popups!!

FCS
New poster
Posts: 9
Joined: Mon Oct 15, 2001 2:00 am
Do all calculations modulo 100000.

ganza
New poster
Posts: 4
Joined: Wed Oct 17, 2001 2:00 am
Location: Portugal
Contact:
Now that works fine!

Thanks a lot!

FlyDeath
Learning poster
Posts: 73
Joined: Wed Jan 02, 2002 2:00 am
Location: Taiwan
What do you means??I don't understand
If i enter "r n n" then what shoud it be??
Here is the answer my program gave:

| r
|| * rr
|||| rrrr
|||||||| * rrrrrrrr
The solution is:
(I didn't type the space properly above)

ganza
New poster
Posts: 4
Joined: Wed Oct 17, 2001 2:00 am
Location: Portugal
Contact:
yep!
My program gets the same result

Do you get WA(Wrong Answer)?

FlyDeath
Learning poster
Posts: 73
Joined: Wed Jan 02, 2002 2:00 am
Location: Taiwan
I got AC finally

keen
New poster
Posts: 1
Joined: Sun May 18, 2003 6:11 pm

### 276 - what

Please, can anybody tell me why I get WA?
[c]
#include <stdio.h>
#include <string.h>

int egiDec (char num);
void imprimeEgi (int x, int ast);

int main()
{
int esquerda=0, i=0, j=0, k=0, m=0, decimal=0, decimal2=0, resultado=0;
char num = "";

fgets (num, 55, stdin);
while (num != '\n')
{
decimal = egiDec (num);
fgets (num, 55, stdin);
decimal2 = egiDec (num);
esquerda = 1;
resultado = (decimal * decimal2) % 100000;
while (esquerda * 2 <= decimal2)
esquerda *= 2;
i = decimal2;
for (j = 1; j <= esquerda; j *= 2)
{

k = esquerda;
m = k;
while (m < i)
{
k /= 2;
if (m + k <= i)
m += k;
}
if (k == j)
{
imprimeEgi (j, 1);
i -= j;
}
else
imprimeEgi (j, 2);
imprimeEgi (decimal, 0);
decimal *= 2;
}
printf ("The solution is: ");
imprimeEgi (resultado, 0);
fgets (num, 55, stdin);
}
return 0;
}

int egiDec (char num)
{
int lenNum=strlen(num), i=0, j=0;
int dec=0;
char grupo="";

for (i=0; i<=lenNum-1; i++)
{
if (num == ' ')
{
grupo[j] = '\0';
switch (num[i-1])
{
case '|' :
dec += strlen(grupo);
break;
case 'n' :
dec += 10 * strlen(grupo);
break;
case '9' :
dec += 100 * strlen(grupo);
break;
case '8' :
dec += 1000 * strlen(grupo);
break;
case 'r' :
dec += 10000 * strlen(grupo);
break;
}
j = 0;
}
else if (num != '\0')
{
grupo[j] = num;
j++;
}
else
break;
}
return dec;
}

void imprimeEgi (int x, int ast)
{
int casas = {0, 0, 0, 0, 0};
int i=0, len=0;
char a;
for (i = 0; i <= 4; i++)
{
casas = x % 10;
x /= 10;
}
for (i = 0; i <= 4; i++)
{
switch (i)
{
case 0:
a = '|';
break;
case 1:
a = 'n';
break;
case 2:
a = '9';
break;
case 3:
a = '8';
break;
case 4:
a = 'r';
}
for (; casas > 0; casas--)
{
printf ("%c", a);
len++;
}
if ((len > 0) && (i < 4) && (casas[i+1] > 0))
{
printf (" ");
len++;
}
}
printf (" ");
len++;
if (ast == 1)
{
printf ("*");
len++;
}
if (ast != 0)
{
for (; len < 34; len++)
printf (" ");
}
else
printf ("\n");
}
[/c]

angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia

### 276 - Egyptian Multiplication WA

Hello, help me.
I'm getting WA over and over. Please give me the output for these cases :

Code: Select all

``````r
n
| n 9 8 r
rrrrrrrrr
rrrrrrrrr
rrrrrrrrr
||||||||| nnnnnnnnn 999999999 888888888 rrrrrrrrr
||||||||| nnnnnnnnn 999999999 888888888 rrrrrrrrr``````
And I don't quite understand, what to do if the number while in steps (or the result) getting overflow (>99999). I just do modulus 100000 everytime I get new number.
Are there any blank lines? or any tricky inputs?

Thanks. Regards,
angga888

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden
My solution outputs:

Code: Select all

``````|                                 r
|| *                              rr
||||                              rrrr
|||||||| *                        rrrrrrrr
The solution is:
|                                 | n 9 8 r
||                                || nn 99 88 rr
||||                              |||| nnnn 9999 8888 rrrr
||||||||                          |||||||| nnnnnnnn 99999999 88888888 rrrrrrrr
|||||| n *                        |||||| nnnnnnn 9999999 8888888 rrrrrrr
|| nnn                            || nnnnn 99999 88888 rrrrr
|||| nnnnnn                       |||| 9 8 r
|||||||| nn 9 *                   |||||||| 99 88 rr
|||||| nnnnn 99 *                 |||||| n 9999 8888 rrrr
|| n 99999 *                      || nnn 99999999 88888888 rrrrrrrr
|||| nn 8 *                       |||| nnnnnn 999999 8888888 rrrrrrr
|||||||| nnnn 88 *                |||||||| nn 999 88888 rrrrr
|||||| nnnnnnnnn 8888 *           |||||| nnnnn 999999 r
|| nnnnnnnnn 9 88888888           || n 999 8 rr
|||| nnnnnnnn 999 888888 r *      |||| nn 999999 88 rrrr
|||||||| nnnnnn 9999999 88 rrr    |||||||| nnnn 99 88888 rrrrrrrr
|||||| nnn 99999 88888 rrrrrr *   |||||| nnnnnnnnn 9999 rrrrrrr
The solution is: rrrrrrrrr
|                                 rrrrrrrrr
||                                rrrrrrrr
||||                              rrrrrr
||||||||                          rr
|||||| n *                        rrrr
|| nnn                            rrrrrrrr
|||| nnnnnn                       rrrrrr
|||||||| nn 9 *                   rr
|||||| nnnnn 99 *                 rrrr
|| n 99999 *                      rrrrrrrr
|||| nn 8 *                       rrrrrr
|||||||| nnnn 88 *                rr
|||||| nnnnnnnnn 8888 *           rrrr
|| nnnnnnnnn 9 88888888           rrrrrrrr
|||| nnnnnnnn 999 888888 r *      rrrrrr
|||||||| nnnnnn 9999999 88 rrr    |||| 9999999 88 rrrrr
|||||| nnn 99999 88888 rrrrrr *   |||| 9999999 88 rrrrrrr
The solution is: |||||||| 9999 88888 rrrrrr
| *                               ||||||||| nnnnnnnnn 999999999 888888888 rrrrrrrrr
|| *                              |||||||| nnnnnnnnn 999999999 888888888 rrrrrrrrr
|||| *                            |||||| nnnnnnnnn 999999999 888888888 rrrrrrrrr
|||||||| *                        || nnnnnnnnn 999999999 888888888 rrrrrrrrr
|||||| n *                        |||| nnnnnnnn 999999999 888888888 rrrrrrrrr
|| nnn                            |||||||| nnnnnn 999999999 888888888 rrrrrrrrr
|||| nnnnnn                       |||||| nnn 999999999 888888888 rrrrrrrrr
|||||||| nn 9 *                   || nnnnnnn 99999999 888888888 rrrrrrrrr
|||||| nnnnn 99                   |||| nnnn 9999999 888888888 rrrrrrrrr
|| n 99999 *                      |||||||| nnnnnnnn 9999 888888888 rrrrrrrrr
|||| nn 8 *                       |||||| nnnnnnn 999999999 88888888 rrrrrrrrr
|||||||| nnnn 88                  || nnnnn 999999999 8888888 rrrrrrrrr
|||||| nnnnnnnnn 8888             |||| 999999999 88888 rrrrrrrrr
|| nnnnnnnnn 9 88888888           |||||||| 99999999 8 rrrrrrrrr
|||| nnnnnnnn 999 888888 r        |||||| n 999999 888 rrrrrrrr
|||||||| nnnnnn 9999999 88 rrr *  |||||| nnn 999999999 888888888 rrrrrrrrr
|||||| nnn 99999 88888 rrrrrr *   || nnnnnnn 99999999 888888888 rrrrrrrrr
The solution is: ||||||||| 9999 88888 rrrrrr
``````
As you can see, I only do the modulus when presenting the end result. (It sounds rather weird, but it's been a while since I solved the problem, and well, it's accepted )

As far as I can tell, my solution would terminate on a blank line, so I don't think there are any.

angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia
Thanks Per for your output. But I want to ask for input

Code: Select all

``````rrrrrrrrr
rrrrrrrrr``````
means 90000 * 90000 right?
So the solution if mod by 100000 should be 0 Your output is |||||||| 9999 88888 rrrrrr
Can you explain to me why?

What variable type do you use? int, long, or long long?
And in what way do you calculate the result?
By adding the right number when there is an asterisk on left number,
finally mod 100000, or
Just calculate (a*b) mod 100000 and ignoring the process at all?

You said that you don't do modulus at all while in process, so
if the number (left or right) getting bigger (overflow from max variable
you use), what will happen?

Thanks Regards,
angga888

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden
I use int, and just print the final result as (a*b)%100000, so when the input is 90000*90000 I get an overflow (and that's why my answer was not 0) In such cases I would get overflow in the process as well.

So I'm guessing there are no test cases in judge's input where a*b >= 2^31

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
Can someone post more inputs? I keep getting WA... Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
Nevermind, I tried multiply by 0 when input is a blank line, and I changed it to return when that happens and got AC. Stupidness.

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:
well, what is the rule of the spaces.
i had wa for the spaces.
please make it clear and precise.
--
Anupam "Everything should be made simple, but not always simpler"

mlvahe
New poster
Posts: 23
Joined: Wed Jul 30, 2003 6:54 am
Location: Yerevan, Armenia

### Help me please.     Please help me. Because whatever I do I get WA.
I don't know what to do.
[cpp]
#include <iostream>
using namespace std;

char dig[] = {'|','n','9','8','r'};

int print(int a)
{
int i = 0, l = 0, j;
while (a != 0)
{
if (a % 10)
{
for (j = 0; j < a % 10; j++)
{
cout << dig;
l++;
}
cout << ' ';
l++;
}
i++;
a /= 10;
}
return l;
}

int getdeg(char c)
{
int i, t10 = 1;
for (i = 0; i < 5; i++)
{
if (dig == c)
return t10;
t10 *= 10;
}
return 0;
}

int translate(char *a)
{
int i, s = 0;
for (i = 0; a; i++)
s += getdeg(a);
return s;
}

main()
{
char str;
int a, b, i, l, a0, j, m;
while (cin.getline(str,1000))
{
b = translate(str);
if (!(*str))
return 0;
cin.getline(str,1000);
a = translate(str);
/* if (!(*str))
return 0;*/
a0 = a;
m = 1;
i = 1;
while (a)
{
l = print(m);
if (a % 2)
{
cout << '*';
l++;
}
for (j = l + 1; j < 35; j++)
cout << ' ';
print(m*b);
m *= 2;
a /= 2;
i++;
cout << '\n';
}
cout << "The solution is: ";
print((a0*b)%100000);
cout << '\n';
}
return 0;
}
[/cpp]