## 276 - Egyptian Multiplication

**Moderator:** Board moderators

### 276 - what

Please, can anybody tell me why I get WA?

[c]

#include <stdio.h>

#include <string.h>

int egiDec (char num[55]);

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[55] = "";

fgets (num, 55, stdin);

while (num[0] != '\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[55])

{

int lenNum=strlen(num), i=0, j=0;

int dec=0;

char grupo[15]="";

for (i=0; i<=lenNum-1; i++)

{

if (num

[c]

#include <stdio.h>

#include <string.h>

int egiDec (char num[55]);

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[55] = "";

fgets (num, 55, stdin);

while (num[0] != '\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[55])

{

int lenNum=strlen(num), i=0, j=0;

int dec=0;

char grupo[15]="";

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{

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{

grupo[j] = num

*;*

j++;

}

else

break;

}

return dec;

}

void imprimeEgi (int x, int ast)

{

int casas[5] = {0, 0, 0, 0, 0};

int i=0, len=0;

char a;

for (i = 0; i <= 4; i++)

{

casasj++;

}

else

break;

}

return dec;

}

void imprimeEgi (int x, int ast)

{

int casas[5] = {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 (; casasx /= 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]{

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]

### 276 - Egyptian Multiplication WA

Hello, help me.

I'm getting WA over and over.

Please give me the output for these cases :

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

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

Are there any blank lines? or any tricky inputs?

Thanks.

Regards,

angga888

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 far as I can tell, my solution would terminate on a blank line, so I don't think there are any.

But I want to ask for input

Code: Select all

```
rrrrrrrrr
rrrrrrrrr
```

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

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

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; areturn t10;

t10 *= 10;

}

return 0;

}

int translate(char *a)

{

int i, s = 0;

for (i = 0; a

*; i++)*

s += getdeg(as += getdeg(a

*);*

return s;

}

main()

{

char str[1000];

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]return s;

}

main()

{

char str[1000];

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]