343 - What Base Is This?

[Ashkankhan]

what's wrong with my code?

Code: Select all

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

char a[50];
char a1[50];
char b[50];
char b1[50];
main()
{
	int i,j,h,la,lb,f,ma,mb;
	unsigned long va,vb;
	while(scanf("%s%s",&a1,&b1)==2)
	{
		ma=mb=0;
		strcpy(a,a1);
		strcpy(b,b1);
		f=0;
		la=strlen(a)-1;
		lb=strlen(b)-1;
		for(i=0;i<=la;i++)
		{
			if(a[i]<='Z' && a[i]>='A')
				a[i]-=7;
			a[i]=a[i]-'0';
			if(a[i]>ma)
				ma=a[i];
		}
		for(i=0;i<=lb;i++)
		{
			if(b[i]<='Z' && b[i]>='A')
				b[i]-=7;
			b[i]=b[i]-'0';
			if(b[i]>mb)
				mb=b[i];
		}
		if(ma==0)
			ma=1;
		if(mb==0)
			mb=1;
		for(i=ma+1;i<=36;i++)
		{
			va=a[la];
			for(h=la-1;h>=0;h--)
			{
				va+=a[h]*(int)pow(i,(la-h));
			}
			for(j=mb+1;j<=36;j++)
			{
				vb=b[lb];
				for(h=lb-1;h>=0;h--)
				{
					vb+=b[h]*(int)pow(j,(lb-h));
				}
				if(i!=j && va==vb)
				{
					f=1;
					break;
				}
			}
			if(f)
				break;
		}
		if(va==0 && vb==0)
			printf("0 (base 2) = 0 (base 2)\n");
		else
		if(j==37 && i==37)
			printf("%s is not equal to %s in any base 2..36\n",a1,b1);
		else
			printf("%s (base %d) = %s (base %d)\n",a1,i,b1,j);
	}
	return 0;
}

[mosaick2]

I don't know what's problem in my code.
Frankly, I think my algorithm is fast enough. But, I got TLE. I don't know the reason. Who can advice me?
Below my code.

Code: Select all

Code Removed

[Vexorian]

Edit: Try to update the algorythm so one of the bases is always less than the other one, instead of checking every single case, given the input it is possible to figure out which of the 2 bases is supposed to be the lesser than the other.


The OJ defines an ONLINE_JUDGE constant so you don't have to use your own define.

[mosaick2]

Edit: Try to update the algorythm so one of the bases is always less than the other one, instead of checking every single case, given the input it is possible to figure out which of the 2 bases is supposed to be the lesser than the other.


The OJ defines an ONLINE_JUDGE constant so you don't have to use your own define.

You're right. I have tested unnecessary cases. So, I have changed my code. But, I got WA. maybe My algorithm have a problem. Could help me one more?

below my code.

Code: Select all

#define ONLINE
#include <fstream>
#include <iostream> 
#include <string> 
#include <vector> 
#include <algorithm> 
using namespace std; 
#include <cstdio>
#include <cstring>
#include <cmath>

#define pb push_back 
#define sz size

#ifndef ONLINE
ifstream in("input.txt");
#else
istream& in = cin;
#endif

typedef long long ll;

ll GetNumBased(string str, int base)
{
	ll num = 0;
	int last = str.sz() - 1;
	for (int i = last; i >= 0; i--)
	{
		ll digit;
		if (isalpha(str[i]))
			digit = (str[i] - 'A' + 10) * pow((double)base, (double)i);
		else
			digit = str[i] - '0';

		ll n = (digit * pow((double)base, (double)last-i));
		num += n;
	}
	return num;
}

int FindStartBase(string str)
{
	char max = '0';
	for (int i = 0; i < str.sz(); i++)
		max = (str[i] > max) ? str[i] : max;

	int start;
	if (isalpha(max))
		start = max - 'A' + 10;
	else
		start = max - '0';

	if (start == 0)
		start++;
	return start+1;
}

void CutZero(string& str)
{
	int pos = 0;
	for (int i = 0; i < str.size(); i++)
	{
		if (str[i] == '0')
			pos++;
		else
			break;
	}
	str.erase(0,pos);
}
int main()
{
	for (;;)
	{
		string str1, str2; in >> str1 >> str2; if (in.eof()) break;
		CutZero(str1);
		CutZero(str2);

		int start1 = FindStartBase(str1);
		int start2 = FindStartBase(str2);

		ll num1 = 0, num2 = 0;
		int base1, base2;
		for (base1 = start1; base1 <= 36; base1++)
		{
			for (base2 = start2; base2 <= 36; base2++)
			{
				num1 = GetNumBased(str1, base1);
				num2 = GetNumBased(str2, base2);
				if (num1 <= num2) break;
			}
			if (num1 == num2) break;
		}

		if (base1 < 37 && base2 < 37)
			cout << str1 << " (base " << base1 << ") = "<< str2 << " (base "<< base2 << ")\n";
		else
			cout << str1 << " is not equal to " << str2 << " in any base 2..36\n";	
	}

	return 0;
}

[Vexorian]

try:
0 0
Output should be 0 (base 2) = 0 (base 2)

(There is no base 1)

[Mushfiqur Rahman]

I didn't found any worng with my code, but I am getting WA. Maybe I got WA more than 10 times. I checked it with all I/O from board but its giving the correct answer.

Now I am giving my code. Anybody who got AC can check it with his code.

If anybody help me than I would be grateful to him.

My code:

Code: Select all

Remove after AC

[Mushfiqur Rahman]

Dear, Ashkankhan

Your code is giving wrong output with this following input.
Input:

Code: Select all

 1   1
  2    2
   3     3
   4  4
5  5
6 6
7 7
8 8

Fix it and got AC

[kana]

i'm really helpless. i've collected more than 10 WA with this one. anyone to help me ...???

Code: Select all

/*
	What Base Is This?
*/

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

#define max 300

char a1[max], a2[max];


long todeci(char arr[], int base)
{
	int i, len = strlen(arr);
	long d = 0, dum;

	for(i = 0; i < len; i++)
	{
		if(isdigit(arr[i]))
			dum = arr[i] - '0';

		if(isalpha(arr[i]))
			dum = arr[i] - 'A' + 10;

		d += (long)pow(base, (len - i - 1)) * (dum);
	}

	return d;
}


int startbase(char s[])
{
	int i, base = 2, len = strlen(s), dum;

	for(i = 0; i < len; i++)
	{
		if(isdigit(s[i]))
			dum = s[i] - '0';

		else if(isalpha(s[i]))
			dum = s[i] - 'A' + 10;

		if(dum >= base)
			base = dum + 1;
	}

	return base;

}

char *rmvzero(char a[], char b[])
{
	int len = strlen(b), k, l;
	
	strcpy(a, b);

	for(k = 0; k < len; k++)
	{
		if(a[k] != '0' || len == 1)
			break;

		else
		{
			for(l = k; a[l]; l++)
				a[l] = a[l + 1];
			
			k--;
			len--;
		}
	}

	return a;
}


int main()
{
	char s[max], s1[max], s2[max];
	int i, j, b1, b2, flag, sb1, sb2;
	long n1, n2, min1, min2;


	while(gets(s))
	{
		if(strlen(s) == 0)
			continue;

		sscanf(s,"%s %s", s1, s2);

		n1 = n2 = -1;
		min1 = min2 = flag = 0;

		rmvzero(a1, s1);
		rmvzero(a2, s2);

		sb1 = startbase(a1);
		sb2 = startbase(a2);

		for(i = sb1; i <= 36; i++)
		{
			for(j = sb2; j <= 36; j++)
			{
				if(!min1)
				{
					n1 = todeci(s1, i);
					min1 = 1;
					b1 = i;
				}
				
				if(!min2)
				{
					n2 = todeci(s2, j);
					min2 = 1;
					b2 = j;
				}

				if( n1 > -1 &&  n2 > -1)
				{
					if(n1 == n2)
						flag = 1;

					else
						min1 = min2 = 0;

				}
				if(flag)
					break;
	
			}
			if(flag)
				break;
		}

		if(flag)
			printf("%s (base %d) = %s (base %d)\n", s1, b1, s2, b2);

		else
			printf("%s is not equal to %s in any base 2..36\n", s1, s2);
	}

	return 0;
}

[Jan]

Try the cases...

Input:

Code: Select all

7FR82OGF   7FR82OGF 
IGW6NFP   IGW6NFP 
I7U4NK1   I7U4NK1 
4NTD52X   4NTD52X 
NMEP0AI   NMEP0AI 
ID9QJFE   ID9QJFE 
IU0TLAO   IU0TLAO 
4CY20XP   4CY20XP 
2U6OA34   2U6OA34 

Output:

Code: Select all

7FR82OGF (base 28) = 7FR82OGF (base 28)
IGW6NFP (base 33) = IGW6NFP (base 33)
I7U4NK1 (base 31) = I7U4NK1 (base 31)
4NTD52X (base 34) = 4NTD52X (base 34)
NMEP0AI (base 26) = NMEP0AI (base 26)
ID9QJFE (base 27) = ID9QJFE (base 27)
IU0TLAO (base 31) = IU0TLAO (base 31)
4CY20XP (base 35) = 4CY20XP (base 35)
2U6OA34 (base 31) = 2U6OA34 (base 31)

Hope these help.

[parkj]

why output limit......?plz.......

Code: Select all

#include<iostream>
#include<string.h>

using namespace std;



int getNumber(char *cValue, int base)
{
	int i = 0;
	int j = 1;
	int nValue = 0; 
	int temp;

	while(cValue[i] != '\0')
	{	
		if(nValue < 0) break;
		temp = 0;

		if(cValue[i] >='0' && cValue[i] <='9')
		{	

			if(temp = (cValue[i] -'0') >= base)
			{
				nValue = -1;
				break;
			}
			nValue *= base;
			nValue += (cValue[i]-'0');
		}
		else if(cValue[i] >='A' && cValue[i] <= 'Z')
		{
			if(temp = 10 + (cValue[i] -'A') >= base)
			{
				nValue =-1;
				break;
			}
			nValue *= base;
			nValue += (10 + (cValue[i] - 'A'));
		}
		else 
		{
			nValue = -2;
		}
		i++;
	}

	return nValue;
}


int main()
{
	char cInput1[50];
	char cInput2[50];
	bool check = false;
	while(1)
	{
		int len = 0;
		cin>>cInput1>>cInput2;
		if(strlen(cInput1) > 50)
			len++;
		if(strlen(cInput2) > 50)
			len++;
		if(len != 0)
			return 0;

		for(int i = 2; i < 37; i++)
		{
			for(int j = 2; j < 37; j++)
			{
				if(check == true) break;

				if((getNumber(cInput1, i) >= 0) && (getNumber(cInput2, j) >= 0))
				{

					if(getNumber(cInput1, i) == getNumber(cInput2, j))
					{
						cout << cInput1 <<"(base"<< i <<") = "<< cInput2 <<"(base"<< j <<")"<<endl; 
						check = true;
						break;
					}
				}
				else if((getNumber(cInput1, i)) == -2 || (getNumber(cInput2, j) == -2))
					return 0;
				
			}
		}
		if(check == false)
			cout <<cInput1<<"is not equal to "<<cInput2<<" in any base 2..36"<<endl;
		check = false;

	}
	return 0;
}

Code: Select all

Code: Select all

[Spykaj]

Plz give your code in the:

Code: Select all

because it's no good for reading

[kamiloj]

thank's for all.

[rio]

I think you code need this.

Code: Select all

#include <cmath>
#include <cstdio>
#include <cctype>

!Don't forget removing your code after AC.

[Spykaj]

Change

Code: Select all

      int len = 0;
      cin>>cInput1>>cInput2;
      if(strlen(cInput1) > 50)
         len++;
      if(strlen(cInput2) > 50)
         len++;
      if(len != 0)
         return 0; 

to

Code: Select all

      if(! (cin>>cInput1>>cInput2) )return 0;

I add some spaces

12 (base 3) = 5 (base 6)

insteed of

12(base3) = 5(base6)

and i get PE :] u must do it carefully...

[RoMeLuKo]

I got WA ... help!! heheh Thanks ...

Code: Select all

ERASED 

Thanks!