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 == ' ')
{
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[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 (; 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]
[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 != '\0')
{
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++)
{
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]
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
My solution outputs:
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.
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.
Thanks Per for your output.
But I want to ask for input
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

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 == 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[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]