343 - What Base Is This?

[minor_coder]

I cant understand why i m getting WA pls help

Code: Select all

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


char num1[50],num2[50];
long long value1,value2;


long long basevalue(char num[],int base)
{
	int i,j,length;
	long long value=0;
	length=strlen(num);
	for(i=length-1,j=0;i>=0;i--,j++)
	{
		if(isalpha(num[i]))
			value=value+int(num[i]-55)*(long long)( pow(double(base),double(j)) );
		else
			value=value+int(num[i]-48)*(long long)(pow(double(base),double(j)));
	}
	return value;
}

int main()
{
	
 
	int len1,len2,i,j,flag=0,high1,high2;
	while( (scanf("%s %s",&num1,&num2))==2 )
	{
		len1=strlen(num1);
		len2=strlen(num2);
		high1=0;
		high2=0;
		if(num1[0]=='0' && num2[0]=='0')
		{
			printf("0 (base 2) = 0 (base 2)\n");
		    continue;
		}
		for(i=0;i<len1;i++)
		{
			if(isdigit(num1[i]))
			{
				if(high1<num1[i]-48)
					high1=num1[i]-48;
			}
			else
			{
				if(num1[i]-55>high1)
					high1=num1[i]-55;
			}

		}
		for(i=0;i<len2;i++)
		{
			if(isdigit(num2[i]))
			{
				if(high2<num2[i]-48)
					high2=num2[i]-48;
			}
			else
			{
				if(num2[i]-55>high2)
					high2=num2[i]-55;
			}

		}
		for(i=2;i<=36 && !flag;i++)
		{	

			if(i<=high1)
				continue;
			value1=basevalue(num1,i);
			for(j=2;j<=36;j++)
			{
				if(j<=high2 )
					continue;
				value2=basevalue(num2,j);
				if(value1==value2){
					flag=1;
					break;
				}
			}
		}
		if(flag)
			printf("%s (base %d) = %s (base %d)\n",num1,i-1,num2,j);
		else
			printf("%s is not eqal to %s in any base 2..36\n",num1,num2);
		flag=0;

	}


	return 0;

}

[Taman]

You should try to avoid built_in pow() function for this type of problem. It may cause some troubles. . .I also got a WA and when I removed the pow() function, I got accepted
Hope it helps

[jobbysunrise]

I'ev encounted a weird situation, all the logic seems no problem, and at first I implement the pair match as follows

Code: Select all

		while(start_index_one < 37 && start_index_one < 37)
		{
		if(value_one[start_index_one] < value_two[start_index_two])
			start_index_one++;
		else if(value_one[start_index_one] > value_two[start_index_two])
			start_index_two++;
		else
		{
			index_one = start_index_one;
			index_two = start_index_two;
			return true;

cos I thought that the value should increase as the base increses, and the problem you shou solve is just to find the smallest pair you could in two increasing series, but I always got WA, and then I looked at sb else's code and changed it to

Code: Select all

for ( int i = start_index_one; i <= 36; i++ ) {
		for ( int j = start_index_two; j <= 36; j++ ) {
			if ( value_one[i] == value_two[j] ) {
				index_one = i;
				index_two = j;
				return true;
			}
		}
	}

this seems more complete in logic, but I don't think there's any difference in those two on this situation, and I've done thousands of tests using random-generated input, and those two eactly give the same result, any body please tell me what I have missed here? If I didn't get it wrong, my person understanding is that there must be overflow here, the value is not an increasing series

[deximat]

I made my own, I found some on internet, I cant find even one input that it fails, but it says WA on online judge...
If anyone could suggest me some inputs, thanks a lot.

Code: Select all

#include <stdio.h>
#include <string.h>
int convertdigit(char digit); 

int main()
    {
          char broj[2][100];
          //freopen("baze.in","r",stdin);
          //freopen("baze[moj].out","w",stdout);
          while((scanf("%s",broj[0])!=EOF) && (scanf("%s",broj[1]))!=EOF)
          {
              int min[2]={2,2};
              
              unsigned long long int matrica[41][41];
              int i,j;
              //minimalna baza
              for(j=0;j<=1;j++)
                for(i=0;i<strlen(broj[j]);i++)
                  if( min[j]<(convertdigit(broj[j][i])+1))
                        min[j]=convertdigit(broj[j][i])+1;
              //printf("%d %d",min[0],min[1]);
              //system("pause");      
                 
              //generisem matricu bazaXexsponent
              for(i=1;i<=38;i++) matrica[i][0]=1;
              for(i=1;i<=38;i++)
                for(j=1;j<=18;j++){
                  matrica[i][j]=matrica[i][j-1]*i;              
                  }
              //izracunavam oba broja u svim bazama
              int broja,baza,eksponent;
              unsigned long long int resenja[2][40];
              for(broja=0;broja<=1;broja++)
                for(baza=min[broja];baza<=38;baza++)
                { 
                  resenja[broja][baza]=0;
                  for(eksponent=0;eksponent<strlen(broj[broja]);eksponent++)
                    resenja[broja][baza]+=convertdigit(broj[broja][strlen(broj[broja])-eksponent-1])*matrica[baza][eksponent];
                    
                };
              
              for(i=min[0];i<=36;i++){
                for(j=min[1];j<=36;j++)
                  if(resenja[0][i]==resenja[1][j])
                    {
                       printf("%s (base %d) = %s (base %d)\n",broj[0],i,broj[1],j);
                       goto gotov;
                    };
               
              }
              printf("%s is not equal to %s in any base 2..36\n",broj[0],broj[1]);
              
              gotov:
              if(1);
          }     
    }
int convertdigit(char digit)
{
if(digit<'A')
  {
      return digit - 48;
  }
  else
  {
      return digit - 55;
  }
}

[dejavu_logic]

I always got runtime error on this problem. And I use java

This is my code :

Code: Select all

//import java.io.File;
//import java.io.FileInputStream;
//import java.io.FileNotFoundException;
//import java.util.Formatter;
import java.util.Scanner;
import java.lang.Math;

class WhatBaseIsThis {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        String valSet = "0123456789ABCDEFGHIJKLMONPQRSTUVWXYZ";
//        Scanner in = new Scanner(new FileInputStream(new File("input")));
        Scanner in = new Scanner(System.in);
//        Formatter out = new Formatter(System.out);
        String val1 = "", val2 = "";

        while (in.hasNext()) {
            int [] valList1 = new int[35], valList2 = new int[35];
            val1 = in.next();
            val2 = in.next();
            int smallestBase1 = 2, smallestBase2 = 2;
            int len1 = val1.length();
            int len2 = val2.length();
            boolean error = false;
            for (int i = 0; i < len1; i++) {
                int charVal = valSet.indexOf(val1.charAt(i));
                if (error || charVal < 0) {
                    error = true;
                    break;
                }
                if (charVal + 1 > smallestBase1) smallestBase1 = charVal + 1;
                for (int j = 0; j < 35; j++) {
                    valList1[j] = (int) (valList1[j] + (charVal * Math.pow(j + 2, len1 - i - 1)));
                }
            }
            for (int i = 0; i < len2; i++) {
                int charVal = valSet.indexOf(val2.charAt(i));
                if (error || charVal < 0) {
                    error = true;
                    break;
                }
                if (charVal + 1 > smallestBase2) smallestBase2 = charVal + 1;
                for (int j = 0; j < 35; j++) {
                    valList2[j] = (int) (valList2[j] + (charVal * Math.pow(j + 2, len2 - i - 1)));
                }
            }
            int base1 = 0, base2 = 0;
            boolean found = false;
            for (int i = smallestBase1 - 2; i < 35; i++) {
                if (error) break;
                for (int j = smallestBase2 - 2; j < 35; j++) {
                    if (valList1[i] == valList2[j]) {
                        base1 = i + 2;
                        base2 = j + 2;
                        found = true;
                        break;
                    }
                }
                if (found) break;
            }
            if (found) System.out.println(val1 + " (base " + String.valueOf(base1) + ") = " + val2 + " (base " + String.valueOf(base2) + ")");
            else System.out.println(val1 + " is not equal to " + val2 + " in any base 2..36");
            
        }

//        out.close();
        in.close();
    }

}

Help please,
Anyone?

[dejavu_logic]

Anybody please?
Any help would be very appreciated

[dejavu_logic]

So sad that I always got runtime error on this problem
even when I move to use c++ (leaving java)
Even though the code was able to produce exactly the same outputs
with every input in the test cases given in the problem and every possible
input I found in the internet (especially this forum) but the judge
always give me runtime error (not even WA)

This is my code in C++

Code: Select all

#include <stdlib.h>
#include <stdio.h>
#include <map>
#include <string.h>
#include <ctype.h>
#include <math.h>
#include <iostream>
using namespace std;

void resetValList (map<unsigned int, unsigned long long> &valList) {
    for (unsigned int i = 0; i < 37; i++) {
        valList[i] = 0;
    }
}

unsigned int charToVal (char number) {
    unsigned int ascii = number;
    if (ascii >= 65 && ascii <= 90) return ascii - 55;
    else if (ascii) return ascii - 48;
}

unsigned int getMinBase (char *number) {
    unsigned int minBase = 2;
    unsigned int l = strlen(number);
    for (unsigned int i = 0; i < l; i++) {
        unsigned int cVal = charToVal(number[i]);
        if (minBase < cVal + 1) minBase = cVal + 1;
    }
    return minBase;
}

void assignValues (char *number, map<unsigned int, unsigned long long> &valList) {
    unsigned int minBase = getMinBase(number), l = strlen(number);
    for (unsigned int i = 0; i < l; i++) {
        unsigned int charVal = charToVal(number[i]);
        for (unsigned int j = minBase; j < 37; j++) {
            valList[j] = valList[j] + (unsigned long long) (charVal * pow(j, l - 1 - i));
        }
    }
}

/*
 * 
 */
int main(int argc, char** argv) {
    #ifndef ONLINE_JUDGE
        freopen("input", "rb", stdin);
    #endif
    map<unsigned int, unsigned long long> valList1, valList2;
    char *val1 = (char *)malloc(sizeof(char) * 20), *val2 = (char *)malloc(sizeof(char) * 20);
    while (scanf("%s%s", val1, val2) != EOF) {
        resetValList(valList1);
        resetValList(valList2);
        assignValues(val1, valList1);
        assignValues(val2, valList2);
        unsigned int minBase1 = getMinBase(val1);
        unsigned int minBase2 = getMinBase(val2);
        bool found = false;
        for (unsigned int i = minBase1; i < 37; i++) {
            for (unsigned int j = minBase2; j < 37; j++) {
                if (valList1[i] == valList2[j]) {
                    printf("%s (base %u) = %s (base %u)\n", val1, i, val2, j);
                    found = true;
                    break;
                }
            }
            if (found) break;
        }
        if (!found) printf("%s is not equal to %s in any base 2..36\n", val1, val2);
    }
    free(val1);
    free(val2);
    return EXIT_SUCCESS;
}

I don't know what else to say.
I just want any help or any suggestion
What went wrong
Thx.

[sirius]

Hi dejavu_logic

try to change your

Code: Select all

char *val1 = (char *)malloc(sizeof(char) * 20), *val2 = (char *)malloc(sizeof(char) * 20);

with this one

Code: Select all

char val1[25],val2[25];

and don't forget to delete

Code: Select all

free(val1); free(val2);

and also, put a space between %s%s in the argument of your scanf...

I have tried to change your code with my suggestion above, and it turn out to be an accepted one. So, good luck!
PS : when you got accepted, please delete your code. thank you.

[dejavu_logic]

Hi dejavu_logic

try to change your

Code: Select all

char *val1 = (char *)malloc(sizeof(char) * 20), *val2 = (char *)malloc(sizeof(char) * 20);

with this one

Code: Select all

char val1[25],val2[25];

and don't forget to delete

Code: Select all

free(val1); free(val2);

and also, put a space between %s%s in the argument of your scanf...

I have tried to change your code with my suggestion above, and it turn out to be an accepted one. So, good luck!
PS : when you got accepted, please delete your code. thank you.

Woaa, nice. It was accepted. Thx sirius.
However it seemed that without a space in the scanf between "%s%s" also worked
And I have a couple of question,

1. Is it necessary to free the array
ex:

Code: Select all

free(val1);

because I thought that an array does not
need to be freed, I thought that only a variable (pointer) that is allocated dynamically with
either

Code: Select all

malloc

or

Code: Select all

calloc

needs to be freed.

2. Which code did you mean need to be deleted?

Thx, and sorry about my english

[sasa_blood]

import java.util.Scanner;

/**
*
* @author mostafa
*/
public class Main {

/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// TODO code application logic here
Scanner input=new Scanner(System.in);
while(input.hasNext())
{
String first=input.next();
String second=input.next();
int [] firstDigits=StringToIntArray(first);
int [] secondDigits=StringToIntArray(second);
int FirstMinIndex=Math.max(MaxNum(firstDigits)+1,2);
int SecondMinIndex=Math.max(MaxNum(secondDigits)+1,2);
int firstindex=0;
int secondindex=0;
boolean stop=false;
for(int i=FirstMinIndex;i<=36&&!stop;i++)
for(int j=SecondMinIndex;j<=36&&!stop;j++)
{
if(getTheNumber(firstDigits, i)==getTheNumber(secondDigits, j))
{
firstindex=i;
secondindex=j;
stop=true;
break;
}
}
if(firstindex!=0)
{
System.out.println(first+" "+"(base "+firstindex+") = "+second+" (base "+secondindex+")");
}
else
{
System.out.println(first+" is not equal to "+second+" in any base 2..36");
}
}
}

private static int[] StringToIntArray(String first) {
int [] array=new int[first.length()];
for(int i=0;i<first.length();i++)
{
if(first.charAt(i)<='9')
array=(int)first.charAt(i)-48;
else
array=(int)first.charAt(i)-55;
}
return array;
}

private static int MaxNum(int[] Array) {
int max=0;
for(int i=0;i<Array.length;i++)
{
max=Math.max(max, Array);
}
return max;
}

private static int getTheNumber(int[] firstDigits, int base) {
int number=0;
for(int i=firstDigits.length-1;i>=0;i--)
{
number+=firstDigits*Math.pow(base, firstDigits.length-i-1);
}
return number;
}

}

my code pass all the test cases on this post and i still got Wrong Answer
plz help me

[shiv]

this gets me a WA, can anyone please help ???
#include<stdio.h>
#include<math.h>
#include<string.h>

int findMinBase(char x[])
{
int mb=2,b,i;
for(i=0;x;i++)
{

if(x>=65)
b=x-54;
else b=x-47;
if(b>mb)mb=b;
}
return mb;
}
int toDec(char x[],int base)
{
int i=strlen(x)-1;
int sum=0,j=0,b;
for(;i>=0;i--)
{
if(x>=65)
b=x-55;
else b=x-48;
sum+=b*pow(base,j++);
}
return sum;
}
main()
{
char x[50],y[50],z[1000];
int mbx,mby,i,j,s,dx,dy;

while(gets(z))
{
sscanf(z,"%s%s",x,y);
mbx=findMinBase(x);
mby=findMinBase(y);
s=0;
for(i=mbx;i<37;i++)
{
dx=toDec(x,i);
for(j=mby;j<37;j++)
{

dy=toDec(y,j);
if(dx==dy)
{
printf("%s (base %d) = %s (base %d)\n",x,i,y,j);
s=1;break;

}
}
if(dx==dy)break;
}
if(s==0)printf("%s is not equal to %s in any base 2..36\n",x,y);

}


return 0;
}

[live_lie]

@jan Thank you sir, i got Ac by your provided Cases.Thank you.

[bill8124]

I've tried all the inputs I found but still received WA.

Sample Input

Code: Select all

12 5
10 A
12 34
123 456
1 2
10 2
0 0
10 36
35 Z
Z 35
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
7FR82OGF 7FR82OGF
IGW6NFP IGW6NFP
I7U4NK1 I7U4NK1
4NTD52X 4NTD52X
NMEP0AI NMEP0AI
ID9QJFE ID9QJFE
IU0TLAO IU0TLAO
4CY20XP 4CY20XP
2U6OA34 2U6OA34
2E 2
153 10
N 1
331 87
9D 312
86 5V
9 21
B 14
6 20

Sample Output (= My Output)
(comfirmed by UVA toolkit: http://uvatoolkit.com/problemssolve.php, they are correct!)

Code: Select all

12 (base 3) = 5 (base 6)
10 (base 10) = A (base 11)
12 (base 17) = 34 (base 5)
123 is not equal to 456 in any base 2..36
1 is not equal to 2 in any base 2..36
10 (base 2) = 2 (base 3)
0 (base 2) = 0 (base 2)
10 (base 27) = 36 (base 7)
35 (base 10) = Z (base 36)
Z (base 36) = 35 (base 10)
1 (base 2) = 1 (base 2)
2 (base 3) = 2 (base 3)
3 (base 4) = 3 (base 4)
4 (base 5) = 4 (base 5)
5 (base 6) = 5 (base 6)
6 (base 7) = 6 (base 7)
7 (base 8) = 7 (base 8)
8 (base 9) = 8 (base 9)
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)
2E is not equal to 2 in any base 2..36
153 is not equal to 10 in any base 2..36
N is not equal to 1 in any base 2..36
331 (base 6) = 87 (base 15)
9D (base 21) = 312 (base 8)
86 (base 25) = 5V (base 35)
9 (base 10) = 21 (base 4)
B (base 12) = 14 (base 7)
6 (base 7) = 20 (base 3)

Hope somebody can find out what mistake I make.
Thanks in advance.

----
My arrays are too small to store the input.
Just change

Code: Select all

  char input[2][30], processed_input[2][30];

to

Code: Select all

  char input[2][100], processed_input[2][100];

and I got Accepted.