355 - The Bases Are Loaded

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

toomyem
New poster
Posts: 6
Joined: Tue Jun 04, 2002 5:48 pm

355 - The Bases Are Loaded

Post by toomyem » Tue Jun 04, 2002 5:52 pm

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
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:

Post by Caesum » Thu Jun 27, 2002 10:31 pm

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
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia

Post by Ivan Golubev » Thu Jun 27, 2002 11:30 pm

Here is a quote from old message board:
Josh Metzler wrote: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
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:

Post by Caesum » Fri Jun 28, 2002 12:11 am

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
New poster
Posts: 3
Joined: Tue Nov 04, 2003 12:20 pm
Location: Dhaka

355 why WA?????

Post by Sarwar » Tue Jun 15, 2004 4:10 pm

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
Learning poster
Posts: 53
Joined: Sat Jul 10, 2004 5:57 pm
Location: Shanghai China

355 WA

Post by oulongbin » Sat Aug 28, 2004 4:19 am

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
New poster
Posts: 30
Joined: Tue Jul 20, 2004 5:22 am
Contact:

Why my code is wrong?Problem 355

Post by frankhuhu » Sat Jan 29, 2005 10:46 am

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;
}

User avatar
mohiul alam prince
Experienced poster
Posts: 120
Joined: Sat Nov 01, 2003 6:16 am
Location: Dhaka (EWU)

Post by mohiul alam prince » Wed Feb 02, 2005 2:54 pm

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

User avatar
mohiul alam prince
Experienced poster
Posts: 120
Joined: Sat Nov 01, 2003 6:16 am
Location: Dhaka (EWU)

Post by mohiul alam prince » Wed Feb 02, 2005 2:58 pm

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

User avatar
mohiul alam prince
Experienced poster
Posts: 120
Joined: Sat Nov 01, 2003 6:16 am
Location: Dhaka (EWU)

Post by mohiul alam prince » Wed Feb 02, 2005 3:00 pm

Hi
u do not consider any negative number

MAP

Cruzer
New poster
Posts: 11
Joined: Thu Feb 10, 2005 4:18 am
Location: Waterloo, ON, Canada

355 OLE

Post by Cruzer » Sat Feb 12, 2005 11:27 pm

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);
    }
}

User avatar
mohiul alam prince
Experienced poster
Posts: 120
Joined: Sat Nov 01, 2003 6:16 am
Location: Dhaka (EWU)

Post by mohiul alam prince » Sun Feb 13, 2005 12:36 pm

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
New poster
Posts: 33
Joined: Tue Jun 29, 2004 1:38 pm
Location: IITM,chennai,Tamil Nadu,India
Contact:

355 - The Bases Are Loaded

Post by Karthekeyan » Fri May 27, 2005 6:28 pm

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!!!! :D
Karthe

User avatar
Ali Arman Tamal
Learning poster
Posts: 76
Joined: Sat Jan 15, 2005 5:04 pm
Location: Dhaka
Contact:

getting Wa 355

Post by Ali Arman Tamal » Fri May 27, 2005 7:54 pm

Hello! :P

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
New poster
Posts: 33
Joined: Tue Jun 29, 2004 1:38 pm
Location: IITM,chennai,Tamil Nadu,India
Contact:

Post by Karthekeyan » Sat May 28, 2005 7:01 am

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!
Karthe

Post Reply

Return to “Volume 3 (300-399)”