355 - The Bases Are Loaded

[toomyem]

Hi,

What is the trick for this problem. I'm correctly converting numbers. I'm handling zero and vegative numbers. And still Wrong Answer I receive.

BTW: for line 2 10 -0 output should be
-0 base 2 = -0 base 10
or
-0 base 2 = 0 base 10

thanx,
tomekM

[Caesum]

there are no negative numbers in this question. use assert() more

the only thing that caught me out was input like
2 10 0
where i was not printing the 0 in my conversion......

[Ivan Golubev]

Here is a quote from old message board:

It took me multiple WA's before I got accepted, but I don't remember why. I think this problem requires a long long int. Note that the number to convert can be negative or 0 (in which case be certain you are writing out the - or the 0). Also note that it can contain invalid digits, and that there can be more than one space between input numbers. Finally, it says that the input won't be longer than 10 digits, but doesn't say how long the output could be - at most 40 digits, though (base 16 to base 2). I don't know what else to suggest.

Sample Input:
16 10 FFFFFFFFFF
16 2 FFFFFFFFFF
2 10 0
10 3 1234567
10 3 -1234567
16 10 -1FFFFFFFF
2 15 1001102001
15 2 3014593F19
16 2 -FFFFFF
10 10 1234567890
16 16 FEDCBA0987
2 3 0
2 10 0
10 2 0
14 8 0
5 12 -1
4 9 -1
2 10 -1
10 2 -10

Sample Output
FFFFFFFFFF base 16 = 1099511627775 base 10
FFFFFFFFFF base 16 = 1111111111111111111111111111111111111111 base 2
0 base 2 = 0 base 10
1234567 base 10 = 2022201111201 base 3
-1234567 base 10 = -2022201111201 base 3
-1FFFFFFFF base 16 = -8589934591 base 10
1001102001 is an illegal base 2 number
3014593F19 is an illegal base 15 number
-FFFFFF base 16 = -111111111111111111111111 base 2
1234567890 base 10 = 1234567890 base 10
FEDCBA0987 base 16 = FEDCBA0987 base 16
0 base 2 = 0 base 3
0 base 2 = 0 base 10
0 base 10 = 0 base 2
0 base 14 = 0 base 8
-1 base 5 = -1 base 12
-1 base 4 = -1 base 9
-1 base 2 = -1 base 10
-10 base 10 = -1010 base 2

Maybe there no negative numbers but I've got WA because output buffer was too small (only 32 symbols).

[Caesum]

I suppose the other comment is to ensure you use long long, although I can only test long on my compiler.... I use
[c]
#ifdef ONLINE_JUDGE
#define longint long long
#else
#define longint int
#endif
[/c]
etc
and printf("%lld",n); for long longs

[Sarwar]

Every output is correct but why WA??
do u have any cretical input, plese help me......
[cpp]
#include<stdio.h>
#include<string.h>
#include<math.h>
#define MAX 10000

#ifdef ONLINE_JUDGE
#define longint long long
#else
#define longint int
#endif

longint DEC;
char Other[MAX];

char Insert_Char(long base,long mod)
{
long i;
char C = 'A';

for(i = 0; i < base - 10; i++)
if(mod == 10+i) return C+i;
return '0';

}

void To_Desimal(char *NUM, long base)
{
long i,ins,l,len;

l = len = strlen(NUM) - 1;
DEC = 0;
for(i = 0; i <= len ; i++)
{
if(NUM == 'A') ins = 10;
else if( NUM == 'B') ins = 11;
else if( NUM == 'C') ins = 12;
else if( NUM == 'D') ins = 13;
else if( NUM == 'E') ins = 14;
else if( NUM == 'F') ins = 15;
else ins = NUM - '0';

DEC = DEC + ins * pow(base,l);
l--;
}
}

void From_Desimal(long base)
{
long i,mod,len,j;
longint dec;
char temp[MAX];

dec = DEC;

for(i = 0; dec!=0;i++ )
{
mod = dec % base;

if(mod >= 10)
temp = Insert_Char(base,mod);


else temp = mod + '0';

dec = dec / base;
}
temp = NULL;

len = strlen(temp)-1;
j = 0;
for(i = len; i >= 0; i-- )
Other[j++]=temp[i];
Other[j] = NULL;

}


int main()
{

long b1,b2,i;
int flag,f;
char NUM[MAX];

while( scanf("%ld%ld%s",&b1,&b2,NUM)==3)
{
flag = 0;
f = 0;

for(i = 0; NUM[i]!=NULL;i++)
{
if( NUM[i] >= '1' && NUM[i]<= '9')
if( b1<= NUM[i] - '0' )
{
printf("%s is an illegal base %ld number\n ",NUM,b1);
flag = 1;
break;
}
}
if(flag) continue;

for(i = 0; NUM[i]!=NULL; i++)
if(NUM[i] != '0'){ flag=1;break;}


if(f == 0) {printf("0 base %ld = 0 base %ld\n",b1,b2);continue;}

if(b2 == 10 )
{

To_Desimal(NUM,b1);
printf("%s base %ld = %lld base %ld\n",NUM,b1,DEC,b2);
}

else if(b1 == 10)
{
sscanf(NUM,"%lld",&DEC);
From_Desimal(b2);
printf("%s base %ld = %s base %ld\n",NUM,b1,Other,b2);
}
else
{
To_Desimal(NUM,b1);

From_Desimal(b2);

printf("%s base %ld = %s base %ld\n",NUM,b1,Other,b2);

}
}


return 0;
}
[/cpp]

[oulongbin]

can someone tell me why my code is wrong??
[cpp]
#include <iostream>
using namespace std;
#include <cstring>
#include <cmath>

int main()
{
int a,b;
char c[15]={'\0'};
char cc[100];
int len;
int i;
long long temp;
bool illegala;
while(cin>>a>>b)
{
cin>>c;
illegala=false;
len=strlen(c);
for(i=0;i<len;i++)
{
if(c>='0'&&c<='9'&&int(c)-48>=a)
{
illegala=true;
break;
}
else if(c>='A'&&c<='F'&&int(c)-55>=a)
{
illegala=true;
break;
}
}
if(illegala)
{
cout<<c<<" is an illegal base "<<a<<" number"<<endl;
}
else
{
temp=0;
for(i=len-1;i>=0;i--)
{
if(c>='0'&&c<='9')
temp+=(int(c)-48)*pow(a,len-i-1);
else
temp+=(int(c)-55)*pow(a,len-i-1);
}
if(b==10)
{
cout<<c<<" base "<<a<<" = "<<temp<<" base "<<b<<endl;
}
else
{
int x=0;
int j=0;
while(temp>b)
{
x=temp%b;
if(x>9)
{
cc[j++]=char(x+55);
}
else
{
cc[j++]=char(x+48);
}
temp/=b;
}
if(temp>9)
{
cc[j]=char(temp+55);
}
else
{
cc[j]=char(temp+48);
}
cout<<c<<" base "<<a<<" = ";
for(i=j;i>=0;i--)
cout<<cc[i];
cout<<" base "<<b<<endl;
}
}
for(i=0;i<15;i++)
c[i]='\0';

}
return 0;
}

[/cpp]

[frankhuhu]

It is not a difficult problem,but why I am WA. Is there anyone who can help me? Thanks!!
Here is my code:
#include <iostream.h>
#include <math.h>
#include <string.h>
#include <cctype>

bool islegal(char *p,int base)
{
int i,max;
for (i=0;p!='\0';i++)
{
if (isdigit(p))
{
max=p-'0';
if (max>base-1) return false;
}
if (isalpha(p))
{
max=p-'A'+10;
if (max>base-1) return false;
}
}
return true;
}

void convert(char *p,int base1,int base2)
{
if (strcmp(p,"0")==0)
{
cout<<p<<" base "<<base1<<" = "<<p<<" base "<<base2<<endl;
return;
}
if (base1==base2)
{
cout<<p<<" base "<<base1<<" = "<<p<<" base "<<base2<<endl;
return;
}
int i,length=(int)strlen(p);
long long tmp=0;
int lens_array=0,tmp2;
char array[1000],flag;
if (p[0]=='-')
{
flag='-';
for (i=length-1;i>0;i--)
{
if (isdigit(p))
tmp+=(int)pow(base1,length-1-i)*(p-'0');
else if (isalpha(p))
tmp+=(int)pow(base1,length-1-i)*(p-'A'+10);
}
tmp*=-1;
}
else if (p[0]=='+')
{
flag='+';
for (i=length-1;i>0;i--)
{
if (isdigit(p))
tmp+=(int)pow(base1,length-1-i)*(p[i]-'0');
else if (isalpha(p[i]))
tmp+=(int)pow(base1,length-1-i)*(p[i]-'A'+10);
}
}
else if (p[0]!='+' && p[0]!='-')
{
flag='+';
for (i=length-1;i>=0;i--)
{
if (isdigit(p[i]))
tmp+=(int)pow(base1,length-1-i)*(p[i]-'0');
else if (isalpha(p[i]))
tmp+=(int)pow(base1,length-1-i)*(p[i]-'A'+10);
}
}
if (base2==10)
{
cout<<p<<" base "<<base1<<" = "<<tmp<<" base 10"<<endl;
return;
}
if (flag=='-') tmp*=-1;
while (tmp)
{
tmp2=tmp%base2;
if (tmp2<10) array[lens_array++]=(char)(tmp2+'0');
else array[lens_array++]=(char)(tmp2-10+'A');
tmp/=base2;
}
cout<<p<<" base "<<base1<<" = ";
if (flag=='-') cout<<'-';
for (i=lens_array-1;i>=0;i--)
cout<<array[i];
cout<<" base "<<base2<<endl;
}

int main()
{
int base1,base2;
char buf[100];
while (cin>>base1>>base2>>buf)
{
if (!islegal(buf,base1))
{
cout<<buf<<" is an illegal base "<<base1<<" number"<<endl;
continue;
}
convert(buf,base1,base2);
}
return 0;
}

[mohiul alam prince]

hi

u have used
- int and
- tmp+=(int)pow(base1,length-1-i)*(p-'0');

instead of this u have to use all data type
- long long
- tmp+=(long long )(pow(base1,length-1-i) + 0.5)*(p-'0');
This could be help for u;

MAP

[mohiul alam prince]

hi

u have used
- int and
- tmp+=(int)pow(base1,length-1-i)*(p-'0');

instead of this u have to use all data type
- long long
- tmp+=(long long )(pow(base1,length-1-i) + 0.5)*(p-'0');
This could be help for u;

MAP

[mohiul alam prince]

Hi
u do not consider any negative number

MAP

[Cruzer]

My code works perfectly on my machine for all input that I've tested (big, small, different bases, negatives, zero). I use Dev-C++ so I use __int64 and %I64d on my computer and then before I submit I change to long long int and %lld. If I don't make this change, the OJ gives me compile error. But when I submit with changes I get OLE. I can't find the problem... Here is my code:

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
long long int convertToInt( char digit );
char convertToChar( long long int digit );
main() {
    long long int base1, base2, i, j, length, temp, valid, decimal, count, countFlag, negativeFlag;
    char input[15], output[55], tempStr[15];
    
    while( scanf("%lld %lld %s", &base1, &base2, input) ) {
        length = strlen(input);
        valid = 1;
        
        /* If negative, remove the negative sign, set negativeFlag */
        negativeFlag = 0;
        if( input[0] == '-' ) {
            strcpy( tempStr, &input[1] );            
            strcpy( input, tempStr );
            negativeFlag = 1;
            length--;
        }
        
        /* Determine if input is valid in base1 */
        for(i = 0; i < length; i++) {
            if( convertToInt(input[i]) >= base1 || convertToInt(input[i]) == -1 ) {
                valid = 0;
                break;
            }
        }
        
        if( valid == 1 ) {
            /* Convert to decimal */
            decimal = 0;
            for(i=0; i < length; i++) {
                temp = convertToInt(input[i]) * (long long int)pow(base1, length - i - 1);
                decimal += temp;
            }
            
            /* Convert decimal to new base */
            if( base2 != 10 ) {
                count = 0; /* counts number of places in new number */
                countFlag = 0;
                for(i=60-(base2*3); i>=0; i--) {
                    temp = 0;
                    if( decimal >= (long long int)pow(base2, i) ) {
                        /* Find digit to use */
                        for(j=1; j < base2; j++) {
                            if( decimal >= j * (long long int)pow(base2, i) ) {
                                temp = j * (long long int)pow(base2, i);
                            }
                            else {
                                break;
                            }
                        }
                        decimal -= temp;
                        /* Place digit long long into output string */
                        output[count] = convertToChar(j-1);
                        countFlag = 1; /* now count starts to increase */
                    }
                    if(countFlag == 1) {
                        if(temp==0) {
                            output[count] = '0';
                        }
                        count++;
                    }
                }
                
                /* Add null char to end of string, take long long into account 0 */
                if( count == 0 ) {
                    output[0] = '0';
                    output[1] = '\0';
                }
                else {
                    output[count] = '\0';
                }                
                
                /* Print result */
                if(negativeFlag==1)
                    printf("-");
                printf("%s base %lld = ", input, base1);
                if(negativeFlag==1)
                    printf("-");
                printf("%s base %lld\n", output, base2);
            }
            else {
                if(negativeFlag==1)
                    printf("-");
                printf("%s base %lld = ", input, base1);
                if(negativeFlag==1)
                    decimal *= -1;
                printf("%lld base %lld\n", decimal, base2);
            }
        }
        else {
            if(negativeFlag==1)
                printf("-");
            printf("%s is an illegal base %lld number\n", input, base1);
        }
    }
}

long long int convertToInt( char digit ) {
    if( isdigit( digit ) ) {
        return digit - '0';
    }
    else if( digit >= 65 && digit <= 70 ) {
        return digit - 'A' + 10;
    }
    else {
        /* error */
        return -1;
    }
}

char convertToChar( long long int digit ) {
    if( digit <= 9 ) {
        return (char)(digit + '0');
    }
    else {
        return (char)(digit - 10 + 65);
    }
}

[mohiul alam prince]

hi
just i have changed
while( scanf("lld lld %s", &base1, &base2, input) == 3 )
and u have got WA
please check some Critical test cases

MAP

[Karthekeyan]

This was the case that i didn't consider initially....and the only sp. case because of which i got WAs frm OJ!!!!
I printed

Code: Select all

0 base 2 = base 10

But, make sure that you print

Code: Select all

0 base 2 = 0 base 10

......
Hope it helps!!!!

[Ali Arman Tamal]

Hello!

I am getting WA in 355 . I have some confusions -

1) do I have to remove the leading 0's
say- what will be the output for following input

16 2 0000120110
10 5 0000120110

my output is:

120110 base 16 = 100100000000100010000 base 2
120110 base 10 = 12320420 base 5

is that correct?

2) Do I have to consider negative input. What will be the output of following inputs :

5 6 -10242
6 8 -0
10 10 -10

my output is:

-10242 base 5 = -3121 base 6
-0 base 6 = 0 base 8
-10 base 10 = -10 base 10
Press any key to continue

is that correct?

3) can there be embedded spaces in the input number, like this -

5 6 -102 42

what should be the output then ?

4) I convert the input value to decimal & keep it in long long. Then I convert it to the required base (with error checking in both steps). Is that ok ?

5) what can be the invalid digits ? What is your method of considering them ?

Give me your opinions. If possible, give me some tricky test cases.

[Karthekeyan]

1)my inputs:

Code: Select all

16 2 0000120110
10 5 0000120110

my outputs:

Code: Select all

0000120110 base 16 = 100100000000100010000 base 2
0000120110 base 10 = 12320420 base 5

2) No need to consider negative inputs (my code didn't consider)
3) There won't be any embedded space in the input number
4)

4) I convert the input value to decimal & keep it in long long. Then I convert it to the required base (with error checking in both steps). Is that ok ?

That's the simplest solution for this problem and i also did the same
5) invalid nos are like the following:
126 is an invalid number to the base 5 because, when you consider a no. represented to the base 5, all digits should be less than 5....similary, AA4 is an invalid no. to the base 10! So, check if each digit is less than the base to check for validity!!!

hope it helped!
bye!