276 - Egyptian Multiplication

[ganza]

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]

Do all calculations modulo 100000.

[ganza]

Now that works fine!

Thanks a lot!

[FlyDeath]

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]

yep!
My program gets the same result

Do you get WA(Wrong Answer)?

[FlyDeath]

I got AC finally

[keen]

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]

[angga888]

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]

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]

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]

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]

Can someone post more inputs? I keep getting WA...

[Larry]

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]

well, what is the rule of the spaces.
i had wa for the spaces.
please make it clear and precise.
--
Anupam

[mlvahe]

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]