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

All about problems in Volume III. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

Postby mosaick2 » Fri Sep 01, 2006 4:35 pm

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

Postby Vexorian » Fri Sep 01, 2006 5:58 pm

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

Postby mosaick2 » Sat Sep 02, 2006 4:27 am

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 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;
}
mosaick2
New poster
 
Posts: 21
Joined: Wed Mar 08, 2006 4:05 am

Postby Vexorian » Sat Sep 02, 2006 6:09 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


Return to Volume III

Who is online

Users browsing this forum: Google [Bot] and 2 guests