343 - What Base Is This?

All about problems in Volume 3. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Ashkankhan
New poster
Posts: 12
Joined: Wed Oct 13, 2004 10:14 am
Location: Teh
Contact:

What's wrong with my code?

Post by 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
New poster
Posts: 21
Joined: Wed Mar 08, 2006 4:05 am

343(What Base Is This?), TLE. I don't know the reason.

Post by 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
Last edited by mosaick2 on Sat Sep 02, 2006 4:22 am, edited 1 time in total.

Vexorian
Learning poster
Posts: 100
Joined: Sat Aug 26, 2006 5:50 am

Post by 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
New poster
Posts: 21
Joined: Wed Mar 08, 2006 4:05 am

I have changed my code, but...

Post by mosaick2 »

Vexorian wrote: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
Learning poster
Posts: 100
Joined: Sat Aug 26, 2006 5:50 am

Post by Vexorian »

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

(There is no base 1)

Mushfiqur Rahman
Learning poster
Posts: 56
Joined: Tue Jun 13, 2006 5:18 pm
Location: (CSE, SUST) Sylhet, Bangladesh
Contact:

343 WA Please Help.

Post by 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
Last edited by Mushfiqur Rahman on Sat Mar 03, 2007 3:20 pm, edited 1 time in total.

Mushfiqur Rahman
Learning poster
Posts: 56
Joined: Tue Jun 13, 2006 5:18 pm
Location: (CSE, SUST) Sylhet, Bangladesh
Contact:

To Ahskankhan

Post by 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 :wink:

kana
New poster
Posts: 19
Joined: Mon Mar 13, 2006 6:03 pm
Location: dhaka

Post by 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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by 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.
Ami ekhono shopno dekhi...
HomePage

parkj
New poster
Posts: 1
Joined: Fri Dec 29, 2006 11:43 am

343 output limit...

Post by 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;
}
Last edited by parkj on Tue Jan 02, 2007 4:26 pm, edited 5 times in total.

Spykaj
New poster
Posts: 47
Joined: Sun May 21, 2006 12:13 pm

Post by Spykaj »

Plz give your code in the:

Code: Select all

 
because it's no good for reading :)

kamiloj
New poster
Posts: 9
Joined: Fri Dec 29, 2006 3:34 pm

343

Post by kamiloj »

thank's for all.
Last edited by kamiloj on Fri Dec 29, 2006 5:40 pm, edited 1 time in total.

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by 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
New poster
Posts: 47
Joined: Sun May 21, 2006 12:13 pm

Post by 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
New poster
Posts: 7
Joined: Mon Jan 02, 2006 1:44 am
Location: Puno - Peru
Contact:

343 - WA

Post by RoMeLuKo »

I got WA :cry: ... help!! heheh Thanks ... :D

Code: Select all

ERASED 
:lol: Thanks!
Last edited by RoMeLuKo on Wed Feb 28, 2007 3:17 am, edited 1 time in total.
Luck!

Post Reply

Return to “Volume 3 (300-399)”