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

Moderator: Board moderators

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

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.
mosaick2
New poster

Posts: 21
Joined: Wed Mar 08, 2006 4:05 am

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.
Vexorian
Learning poster

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

### I have changed my code, but...

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 ONLINEifstream in("input.txt");#elseistream& in = cin;#endiftypedef 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;}`
mosaick2
New poster

Posts: 21
Joined: Wed Mar 08, 2006 4:05 am

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

(There is no base 1)
Vexorian
Learning poster

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