276 - Egyptian Multiplication

danielrocha · Post by **danielrocha** » Mon Oct 31, 2005 4:03 pm

Here's a tip for anyone who's trying to solve this problem but keeps getting WA: don't worry about overflow (as I only used ints), print only the result % 100000 and if you read a blank line, terminate your program. It appears that the judge's input has one blank line at the end (and not a EOF as some would expect).

rahat · Post by **rahat** » Sun Aug 06, 2006 12:04 pm

I have checked all the inputs available in the board and possible from my thought.

But i m getting wrong answer.

Code: Select all


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

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

int egyptToDec ( char s[] )
{
	int i;
	int len = strlen (s);
	int sum = 0;


	for ( i=0; i<len; i++ )
	{
		if ( s[i] == '|' ) sum +=1;
		else if ( s[i] == 'n' ) sum += 10;
		else if ( s[i] == '9' ) sum += 100;
		else if ( s[i] == '8' ) sum += 1000;
		else if ( s[i] == 'r' ) sum += 10000;
	}

	return sum;
}

char * decToEgypt ( int num )
{
	int pos = 0;
	char s[100];
	int first = 1;
	int IDX = 0;
	int rem;
	int temp = 0;
	

	while (num)
	{
		rem = num % 10;
		pos++;

		if ( rem )
		{
			if (!first)
			{
				s [IDX] = ' ';
				IDX++;
				temp = IDX;
			}
			for ( IDX; IDX<temp+rem; IDX++ )
				s[IDX] = letter[pos];		

			s[IDX] = NULL;
			temp = IDX;

			if (first) first = 0;
		}

		num = num / 10;	
	}

	return s;
}

int main ()
{
	char str1 [100], str2 [100], temp[100];
	int num1, num2;
	int Left, sum;
	char tempStr[100];
	int len;
	int i;
	char *p;
	int a, b;

	//freopen ("276.txt","r",stdin);
	//freopen ("276_out.out","w",stdout);
	while ( gets(str1) )
	{

		

		if (!strstr (str1,"|") && !strstr (str1,"n") && !strstr (str1,"9") && !strstr (str1,"8") && !strstr (str1,"r") ) break;
		
	
		
		gets (str2);


		if ( str2[0] == '\n') break;

		strcpy(temp,"");
		p = strtok (str1, " \n");
		while (p)
		{
			strcat (temp,p);
			p = strtok (NULL," \n");
		}
		strcpy (str1, temp);

		
		strcpy(temp,"");
		p = strtok (str2, " \n");
		while (p)
		{
			strcat (temp, p);
			p = strtok (NULL," \n");
		}
		strcpy (str2, temp);
		
		num1 = egyptToDec (str1);
		num2 = egyptToDec (str2);
		a = num1;
		b = num2;

		Left = 1;
		//sum = 0;

		int star = 0;

		printf ("|");
		if ( num2%2 != 0 )
		{
			printf (" *");
			//sum += num1;
			
			star = 1;
		}
		
			
		strcpy (tempStr, decToEgypt(num1));
		if (star) 
			printf ("                               ");

		else printf ("                                 ");
		strcat (tempStr," ");
		puts (tempStr);

		while ( (num2 / 2) )
		{
			num1 = num1 * 2;
			num2 = num2 / 2;
			
			//if ( num1 > 100000 )
				//num1 = num1 % 100000;
			
			Left *= 2;
			
			
			strcpy (tempStr, decToEgypt(Left));
			len = strlen (tempStr);
			for ( i=0; i<len; i++ )
					printf ("%c",tempStr[i]);

			star = 0;
			if ( ( num2 % 2 ) != 0 )
			{
				printf (" *");
				//sum += num1;
				star = 1;
				len +=2;
			}
			for ( i=len; i<34; i++ )
				printf (" ");
			
			
			
			int tempnum1;

			if ( num1 < 0 ) 
			{ 
				
				tempnum1 = num1;
				tempnum1 = 100000 + tempnum1%100000;
				
			}

			else tempnum1 = num1 % 100000;			
			
			strcpy (tempStr, decToEgypt(tempnum1));
			strcat (tempStr, " ");
			puts(tempStr);

		}
		

		sum = (a*b) % 100000;

		if (sum < 0 ) sum += 100000;
		if (sum>0)
		{ 
			strcpy (tempStr, decToEgypt(sum)); 
			strcat (tempStr," ");
		}

		printf ("The solution is: ");
		if (sum>0) puts (tempStr);
		else printf ("\n");
	}
	return 0;
}

rahat · Post by **rahat** » Sun Aug 06, 2006 12:11 pm

Input:

Code: Select all

r 
n 
| n 9 8 r 
rrrrrrrrr 
rrrrrrrrr 
rrrrrrrrr 
||||||||| nnnnnnnnn 999999999 888888888 rrrrrrrrr 
||||||||| nnnnnnnnn 999999999 888888888 rrrrrrrrr

Output:

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

sakhassan · Post by **sakhassan** » Sun Dec 31, 2006 6:20 pm

I am getting P.E .. Am really confused !!!!!!!

Could any one specify the output format clearly ? plsss..
Here is ma code:

Code: Select all


#include<stdio.h>
#include<string.h>


#define N 100

long int proc(char str[N])
{


	long int sum;
	int n,one,eight,nine,r;
	int len;
	int i;
	char ch;


	one = 0;
	n = 0;
	nine = 0;
	eight = 0;
	r = 0;
	len =  strlen(str);
	for(i=0;i<len;i++)
	{
		ch = str[i];
		if(ch=='9')
		 nine++;
		else if(ch=='|')
		 one++;
		else if(ch=='8')
		 eight++;
		else if(ch=='r')
		 r++;
		else if(ch=='n')
		 n++;
	}

	sum = one + n*10 + nine*100 + eight*1000 + r*10000;

	return sum;

}

int print(int f,long int n)
{

       int i,j;
       int  r;
       int flag;
       int idx;

       i=0;
       flag=f;
       idx=0;

       //if(n==0)
	//return 0;

       while(n)
       {
	   r = n%10;
	   if(r)
	   {

		switch(i)
		{
			case 0:

				if(flag)
				{
				 printf(" ");
				 idx++;
				}
				for(j=0;j<r;j++)
				  printf("|");
				idx+=r;
				if(!flag)
				 flag = 1;
			break;

			case 1:

				if(flag)
				{
				 printf(" ");
				 idx++;
				}
				for(j=0;j<r;j++)
				  printf("n");
				idx+=r;
				if(!flag)
				 flag=1;
			break;

			case 2:

				if(flag)
				{
				 idx++;
				 printf(" ");
				}
				for(j=0;j<r;j++)
				  printf("9");
				idx+=r;
				if(!flag)
				 flag = 1;
			break;

			case 3:

				if(flag)
				{
				 printf(" ");
				 idx++;
				}
				for(j=0;j<r;j++)
				  printf("8");
				idx+=r;
				if(!flag)
				 flag=1;
			break;

			case 4:

				if(flag)
				{
				 idx++;
				 printf(" ");
				}
				for(j=0;j<r;j++)
				  printf("r");
				idx+=r;

				if(!flag)
				 flag=1;

			break;
		}

	   }
	   n /= 10;
	   i++;
       }


       return idx;
}

int binary(char str[N],long int n)
{


	int i;

	if(n==0)
	{
	 strcpy(str,"0");
	 return 1;
	}

	i=0;
	while(n)
	{
		if(n%2)
		 str[i++]='1';
		else
		 str[i++]='0';

		n/=2;
	}

	str[i]='\0';
	return i;

}

int main()
{


   char str1[N];
   char str2[N];
   char temp[N];
   long int a,b,c,d,res;
   int count,i,j,k;
   int idx;
   


  freopen("276.cpp","w",stdout);

   while(gets(str1))
   {
      if(strlen(str1)==0)
        break;
	a=proc(str1);
 

	gets(str2);
	b=proc(str2);
	memset(temp,'\0',sizeof(temp));
	count=binary(temp,b);


	i=count-1;
	j=0;
	c = 1;
	d = a;

	while(i>=0)
	{
	      idx = print(0,c);
	      if(temp[j]=='1')
	      {
	       printf(" *");
	       idx+=2;
	      }

	      for(k=0;k<34-idx;k++)
	       printf(" ");

	      print(0,d);


	      printf("\n");
	      c*=2;
	      d*=2;
	      i--;
	      j++;
	}


	res = (a*b)%100000;
	printf("The solution is:");
	print(1,res);
	printf("\n");

   }


   return 0;
}

Thanks in Advance

sakhassan · Post by **sakhassan** » Thu Mar 01, 2007 4:55 pm

Still getting PE in this code

... tried all I/O hard and soul

....

little joey · Post by **little joey** » Thu Mar 01, 2007 6:15 pm

Remove all trailing spaces, and get AC. It's stupid and it took me 2 hrs to figure that out

pineapple · Post by **pineapple** » Fri Mar 02, 2007 6:42 am

Why this problem requires us to remove the trailing blank now.

Each number in the left and right column will be represented by groups of symbols, and each group is terminated by a single space (including the last group).

Very strange...

anacharsis · Post by **anacharsis** » Thu Mar 17, 2016 6:41 am

If you use the UHunt cached version of the pdf, it directs you to fill to the 40th column and start the double of the multiplicand in the 41st.
The actual statement at UVA directs you to fill to 34 and start in 35 for multiplicand.
Use the UVA version of the statement!!!!

OJ Board

276 - Egyptian Multiplication

276 - Egyptian Multiplication

Sorry I think I need to add My Input Output.

Re: 276 - Egyptian Multiplication