343 - What Base Is This?

Moderator: Board moderators

minor_coder
New poster
Posts: 2
Joined: Tue Sep 15, 2009 9:46 am

Re: 343(What Base is This?)

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
New poster
Posts: 32
Joined: Sun Oct 11, 2009 8:59 pm
Location: Southeast University

Re: 343(What Base is This?)

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
New poster
Posts: 1
Joined: Sat Jun 09, 2007 11:41 am

Re: 343(What Base is This?)

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
New poster
Posts: 1
Joined: Fri Sep 17, 2010 6:12 pm

343 WA, works on all inputs

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
New poster
Posts: 6
Joined: Sat Mar 06, 2010 8:30 am

343 Java Runtime Error

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

}
``````

Anyone?
dejavu_logic
New poster
Posts: 6
Joined: Sat Mar 06, 2010 8:30 am

Re: 343 Java Runtime Error

Any help would be very appreciated
dejavu_logic
New poster
Posts: 6
Joined: Sat Mar 06, 2010 8:30 am

343 Runtime Error Not Even WA (Again even using C++)

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
New poster
Posts: 4
Joined: Sat Aug 09, 2008 6:51 am

Re: 343 Runtime Error Not Even WA (Again even using C++)

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
New poster
Posts: 6
Joined: Sat Mar 06, 2010 8:30 am

Re: 343 Runtime Error Not Even WA (Again even using C++)

sirius wrote: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
New poster
Posts: 1
Joined: Sat Feb 19, 2011 2:43 pm

Re: 343(What Base is This?)

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
New poster
Posts: 2
Joined: Mon May 02, 2011 9:53 pm

Re: 343(What Base is This?)

#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
New poster
Posts: 19
Joined: Mon Nov 29, 2010 11:50 pm

Re: 343(What Base is This?)

@jan Thank you sir, i got Ac by your provided Cases.Thank you.
bill8124
New poster
Posts: 8
Joined: Fri Jan 21, 2011 8:13 am

Re: 343(What Base is This?)

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.

----
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.