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

User avatar
danielrocha
New poster
Posts: 44
Joined: Sun Apr 27, 2003 3:17 am
Location: Rio Grande do Norte - Brazil
Contact:

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).
Daniel
UFRN HDD-1
Brasil

rahat
New poster
Posts: 2
Joined: Sun Aug 06, 2006 11:33 am

276 - Egyptian Multiplication

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;
}
I like to know.

rahat
New poster
Posts: 2
Joined: Sun Aug 06, 2006 11:33 am

Sorry I think I need to add My Input Output.

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 


I like to know.

sakhassan
Experienced poster
Posts: 105
Joined: Sat Mar 11, 2006 9:42 am
Location: cse,DU

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

I am getting P.E .. Am really confused !!!!!!! :oops: 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
Time that gone is gone forever ...

sakhassan
Experienced poster
Posts: 105
Joined: Sat Mar 11, 2006 9:42 am
Location: cse,DU

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

Still getting PE in this code :(... tried all I/O hard and soul :( ....
Time that gone is gone forever ...

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

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
Learning poster
Posts: 57
Joined: Fri Nov 03, 2006 3:33 pm

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
Learning poster
Posts: 69
Joined: Mon Feb 09, 2015 1:56 am

Re: 276 - Egyptian Multiplication

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!!!! :)

Post Reply

Return to “Volume 2 (200-299)”