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

[mosaick2]

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

[Vexorian]

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.

[mosaick2]

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 ONLINE
ifstream in("input.txt");
#else
istream& in = cin;
#endif

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

[Vexorian]

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

(There is no base 1)