10023 - Square Root

[medv]

Thank you very much for algorithm!
But soon TLE!!!! How I tired of it!!!!
How to speed up it?????????????????????????????

#include <cstdio>
#include <string>
#include <memory>
#define MAXLENGTH 1001
using namespace std;

class BigInteger{
private:
int m[MAXLENGTH];
int len;

public:
BigInteger(int n)
{
memset(m,0,sizeof(m));
len=0;
if (n == 0) len++;
while (n > 0)
{
m[len++] = n % 10;
n = n / 10;
}
}

BigInteger(string s)
{
int i;
len = s.length();
memset(m,0,sizeof(m));
for(i=0;i<len;i++)
m[i] = s[len-i-1]-'0';
}

void print(void)
{
int temp = len-1;
while(temp>=0) printf("%d",m[temp--]);
}

BigInteger operator+ (const BigInteger &a)
{
int i,carry = 0;
BigInteger Temp(*this);
if (a.len > Temp.len) Temp.len = a.len;
for(i=0;i<Temp.len;i++)
{
Temp.m[i] += (a.m[i] + carry);
carry = Temp.m[i] / 10;
Temp.m[i] %= 10;
}
if (carry > 0) {Temp.m[i] = carry; Temp.len++;}
return Temp;
}

BigInteger operator+ (int a)
{
BigInteger Temp(*this);
int i,carry = a;
for(i=0;i<Temp.len;i++)
{
Temp.m[i] = Temp.m[i] + carry;
carry = Temp.m[i] / 10;
Temp.m[i] = Temp.m[i] % 10;
}
while (carry > 0)
{
Temp.m[i++] = carry % 10;
carry /= 10;
Temp.len++;
}
return Temp;
}

BigInteger operator- (const BigInteger &a) // *this > a !!!
{
BigInteger Temp(*this);
int i,carry = 0;
for(i=0;i<Temp.len;i++)
{
Temp.m[i] = Temp.m[i] - a.m[i] - carry;
if (Temp.m[i] < 0)
{
Temp.m[i] = Temp.m[i] +10;
carry = 1;
} else carry = 0;
}
while (!Temp.m[Temp.len-1] && (Temp.len > 1)) Temp.len--;
return Temp;
}

BigInteger operator* (int a)
{
BigInteger Temp(0);
int i,t,carry = 0;
Temp.len = len;
for(i=0;i<Temp.len;i++)
{
t = a*m[i] + carry;
Temp.m[i] = t % 10;
carry = t / 10;
}
while (carry > 0) {Temp.m[i++] = carry % 10; carry /= 10; Temp.len++;}
return Temp;
}

int operator< (const BigInteger &a)
{
int i;
if (len < a.len) return 1;
if (len > a.len) return 0;
for(i =len-1;(m[i] == a.m[i]) && (i>0);i--);
if (m[i] < a.m[i]) return 1;
return 0;
}

int operator>= (const BigInteger &a)
{
return !(*this < a);
}

BigInteger Sqrt()
{
BigInteger Answer(0), Remain(0), Odd(0);
int group,count,ptr = len-1;
if (len % 2) ptr++;
while(ptr >= 0)
{
group = m[ptr]*10+m[ptr-1];
Odd = Answer*20+1;
Remain = Remain*100+group;
count = 0;
while(Remain >= Odd)
{
count++;
Remain = Remain - Odd;
Odd = Odd + 2;
}
Answer = Answer*10+count;
ptr-=2;
}
return Answer;
}
};

void main(void)
{
int i,n;
char num[MAXLENGTH];
BigInteger a(0);
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%s",num);
a = BigInteger(num);
a.Sqrt().print();printf("\n");
if (i < n-1) printf("\n");
}
}

[mamun]

Slowly my concern is being shifted to BigInteger.

Before reading any post on this forum I tried to solve this problem using Newton's method and got TLE. Then here I came to know about Pell's equation which is nothing but the method we are taught in school for finding square root. I just didn't know the name. Thanks to little joey for putting the algorithm nicely. Anyway here also I got TLE.

Then I tried to find somebody else's BigInteger and got a hand on the one at ShyGypsy. Though the author admitted faster class exists, I got accepted this time with about 8 sec. little joey did it in 3 second.

I used my BigInteger for solving a number of problems over here and solved them in reasonable time. But this time it proved to be too slow. Maybe I've to do it agian. It's so big, hundreds of lines.

I'd like to know what's the best method for writing one such. I used string class in mine. I knew it's slow, but not so slow until now. I searched the forum and found something like using integer vector class, and also representing the nuber in some other base like 10000. I don't understand this part. Agian representing the nuber in char array or int array. char array takes less space but is it slower than using int array? If so then I must use int and to overcome memory wastage, I found, to use different base. But to remention, I didn't understand that.

Plz suggest me. Tell me what you've done.

Thanks all.

[chunyi81]

I used C strings (char arrays) and got TLE at first. I found that I was doing unnecessary reversing of strings when comparing them as integers. I cut down on that and now I don't get TLE, but WA in 8s. There are still some bugs in my BigInteger code somewhere and it's still slow compared to little joey's.

I stored the numbers in reverse (except for the input number) for ease of addition and subtraction.

[little joey]

One thing that is very important if you want to manipulate big integers efficiently, is that you make sure that the time complexites of your basic operations (initialisation, copying, addition, subtraction, multiplication with a small integer) are realy linear in the number of digits involved. In other words, adding two 10 digit numbers should be about 100 times faster than adding two 1000 digit numbers. This can be easily tested by doing the additions in a loop (say 1000000 iterations) and comparing the run times.
In the early stages of the algorithm I described the numbers are relatively small, so a lot of time can be wasted if your implementation is too slow for small numbers. Also the judge input will probably contain a reasonable amount of small input, and you don't want to waste too much time on them.
The nicest way to implement big integers is to use a class in C++ (or Java), but you have to be careful: an implicit call to an inefficient constructor can kill your runtime, but can be very hard to find and cure.

[mamun]

Thanks to all for suggestions. I'll keep the points in mind while rewrintng BigInteger.

I've made my BigInteger as a class in C++. My BigInteger class is of more then 500 lines and very much portable. I've tried to return and work with reference of a BigInteger object (copy constructor) to avoid time consuming recreating copies of the same objects. As I've already said, I solved a number of problems over here using this class.

What makes my class slow are, I think, use of string class to store the integers and, maybe, inefficient algorithm like multiplication and division. Oh yes, I do reversing sometimes.

Now I'd like to clear myself

What's the most time efficient datatype to store values and work with? As I've mentioned, char is enough to store a digit but needs doing addition and subtraction of 48. To print an int array I've to iterate through the array and print digit by digit. Is it slower than normal printing of char array?
Should I use array or link list? If link list then how good is vector class?
What base should I use? If not 10, then what does it mean?
What else should I consider?

Thnk you very much.

[20717TZ]

10023 Square root TLE - I'm going to die...

I tested all kinds of BigNumbers on my PC, and it's OK.
but this input will cost me 0.5second, so if there are more than 20 sets like this, I'll be TLEed
152415787532388367504953515625666819450083828733760097552251181223112635269100015241588876695626775186709466270385625502210030437738149832525529662127724434100289590198780673698753238837762841030565035817735378753241425392470931290961772004267645087943911297546105808629782048750495351663801249845255296452413046792030056393881880810856075598232396311537918506325259738149672762566681955131839663400701113128821825991757354067063252553495076970028382868470725803993861332114065008382874388355434227584209785883249510700807804281329065749257735107038256363915073921712632220703375704923548818777676006706299713153483182563633639381191896050602042816308489602755677492388050602450053345566130163088725499162083798201529504648685062947721717543057492879134281400396281351287913456253619877737844840985032769419628105474075293400618777625383002591070412741960252522481346377076666750190519886267337309751562263087639079520012193273126047859425087639153757049236500533455762536198787501905199875019052100

its root:
12345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890

so how can i improve my code. I'm using the Pell's equation described as follows.


Here is the algorithm:

Code: Select all

/*
(10a+1)^2 - (10a)^2 = 20a+1 // Here we get the number: 20
(10a+2)^2 - (10a+1)^2 = 20a+1+2 //Here we get the increaser number: 2

Take the square root of 148996.

Preparation:
- make groups of two digits, starting from the right: 14-89-96.  //Here we get the number: 100
(if the number of digits was odd, the leftmost group would have only one digit);
- initialise the variables remain, odd and answer with 0.

Loop for every group of two digits, from left to right:
   - odd  = 20 * answer +1;
   - remain = 100 * remain + group;
   - count = 0;
   - loop while remain >= odd:
      - count = count + 1;
      - remain = remain - odd;
      - odd = odd + 2;
   - answer = 10 * answer + count.

In our example we have 3 iterations of the outer loop:

Iteration 1 (group = 14):
   initial:     odd = 20 * 0 + 1 = 1, remain = 100 * 0 + 14 = 14;
   inner loops: remain = 14 - 1 - 3 - 5 = 5, count = 3;
   finaly:      answer = 10 * 0 + 3 = 3.

Iteration 2 (group = 89):
   initial:     odd = 20 * 3 +1 = 61, remain = 100 * 5 + 89 = 589;
   inner loops: remain = 589 - 61 - 63 - 65 - 67 - 69 - 71 - 73 - 75 = 45, count = 8;
   finaly:      answer = 10 * 3 + 8 = 38.

Iteration 3 (group = 96):
   initial:     odd = 20 * 38 + 1 = 761, remain = 100 * 45 + 96 = 4596;
   inner loops: remain = 4596 - 761 -763 - 765 - 767 - 769 - 771 = 0, count = 6;
   finaly:      answer = 10 * 38 + 6 = 386.

So the square root of 148996 is 386. This answer is exact, because the last remainder is 0.
*/


Here is my C++ Code:

Code: Select all

// We use "" instead of "0" when the number = 0
#include <cstdio>
#include <string>

#define MAX 10000

char X[MAX]="";
char Y[MAX]="";

// strrev() is a restricted function!
char* fnStrRev(char* s)
{
   char t[MAX]="";
   int i,len=strlen(s);

   for(i=0; i<len; i++)
      t[i] = s[len-1-i];

   return strcpy(s,t);
}

char* fnAdd(const char* s1,const char* s2)
{
   int len1=strlen(s1),  len2=strlen(s2);
   int max=len1>len2?len1:len2;
   char s[MAX]="";
   char t1[MAX]="", t2[MAX]="";
   int i,n,cy;//Carry Flag

   strcpy(t1,s1);strcpy(t2,s2);
   fnStrRev(t1);fnStrRev(t2);

   if(len1<len2)
      for(i=len1;i<len2;i++) t1[i]='0';
   else
      for(i=len2;i<len1;i++) t2[i]='0';

   for(i=0,cy=0;i<max;i++)
   {
      n=(t1[i]-48)+(t2[i]-48)+cy;
      s[i]=n%10+48;
      cy=n/10;
   }

   if(cy!=0) s[i]=cy+48;
   
   return fnStrRev(s);
}

//s1 always >= s2
char* fnSubtract(const char* s1,const char* s2)
{
   int len1=strlen(s1),  len2=strlen(s2);
   int max=len1>len2?len1:len2;
   char s[MAX]="";
   char t1[MAX]="", t2[MAX]="";
   int i,n,cy;//Carry Flag

   strcpy(t1,s1);strcpy(t2,s2);
   fnStrRev(t1);fnStrRev(t2);

   for(i=len2;i<len1;i++) t2[i]='0';

   for(i=0,cy=0;i<max;i++)
   {
      if(t1[i] + cy < t2[i])
      {
         n = 10 + t1[i] - t2[i] + cy;
         cy = -1;
      }
      else
      {
         n = t1[i] - t2[i] + cy;
         cy = 0;
      }
      s[i] = n + 48; //s[i]=n%10+48; n always < 10
   }

   // if(cy!=0) s[i]=cy+48; //impossible when s1 always >= s2
   
   //remove leading '0'
   while(s[strlen(s)-1]=='0')
      s[strlen(s)-1]=0;

   return fnStrRev(s);
}

int fnCmp(const char* s1, const char* s2)
{
   int len1 = strlen(s1), len2 = strlen(s2);
   if(len1 == len2)
      return strcmp(s1,s2);
   return len1 - len2;
}

void fnRoot()
{
   int i, count;
   int len = strlen(Y);
   char odd[MAX]="", remain[MAX]="", answer[MAX]="", cat[MAX]="";
   char group[3]="";
   char temp[2]="";
   
   if(len%2) group[0]=Y[0];
   else { group[0]=Y[0]; group[1]=Y[1];}
   
   for(i=len%2?0:1; i<len; i+=2)
   {
      //odd = 20*answer + 1;
      strcpy(cat,answer); //backup for answer
      strcpy(cat, fnAdd(cat, cat));
      if(strcmp(cat,"")) strcat(cat, "0");
      strcpy(odd, fnAdd(cat, "1"));
      
      //remain = 100*remain + group;
      if(strcmp(remain,"")) strcat(remain,"00");
      fnStrRev(group); // remove leading '0'
      while(group[strlen(group)-1]=='0')
         group[strlen(group)-1]=0;
      fnStrRev(group);
      strcpy(remain, fnAdd(remain, group));

      count = 0;
      while(fnCmp(remain, odd)>=0)
      {
         count++;
         
         //remain -= odd;
         strcpy(remain, fnSubtract(remain, odd));
         
         //odd += 2;
         strcpy(odd, fnAdd(odd, "2"));
      }

      //answer = answer*10 + count;
      temp[0] = count + 48;
      if(strcmp(answer,"")) strcat(answer, "0");
      strcpy(answer, fnAdd(answer, temp));

      group[0]=Y[i+1]; group[1]=Y[i+2]; //next group
   }
   
   strcpy(X, answer);
}

void main()
{
   FILE* fp = fopen("Input.txt","r");
   int i,j,n,isfirst=1;

   while(1==fscanf(fp,"%d",&n))
   {
      for(i=0; i<n; i++)
      {
         fscanf(fp, "%s", Y);
         fnRoot();
         printf("%s%s\n", isfirst?"":"\n", X);
         isfirst=0;

         //fnClearPrev Reset
         for(j=0;j<MAX;j++)
            X[j]=Y[j]=0;
      }
   }
}


Or my fnAdd() and fnSubtract() can be improved? In what kind of ways?
Help me.

Thank u in advance.

[20717TZ]

I'm sorry that my code is a little long. But I think it's very clear, coz I'm using functions instead of blocks, and also some remarks are presented.

[snar]

Hi,
It seems that my solution is right and fast enough to pass all the tests, but...I got runtime error.
Here is my C code.

Code: Select all

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>
#define MAX 1003

int scan ( char** A ) {
   int n;
   char c;

   c = getchar ( );
    while (isspace (c))   
      c = getchar ( );

   *A = (char*)malloc(MAX);
   n = 0;

   if (c=='-')   {
      (*A)[n++] = '-';
      c = getchar ( );
   }
   else
      if (c=='+')   {
         (*A)[n++] = '+';
         c = getchar ( );
      }
      else
            (*A)[n++] = '+';

   while (isdigit (c))   {
      (*A)[n++] = c;
      c = getchar ( );
   }   

   (*A)[n] = '\0';      

   return strlen(*A)>1 ? 1:0;
}



void print ( char* A ) {
   int i;

   for (i=A[0]=='-'?0:1;A[i];i++)
      printf ("%c", A[i]);
   putchar ('\n');
}


char* assign ( char* A ) {   
   char* B;

    B = (char*)malloc(MAX);
   strcpy (B, A);
   return B;
}

int equalto ( char* A, char* B ) {   
   return strcmp (A, B) == 0;
}

int lessthan ( char* A, char* B ) {   
   int lA, lB;

   if (A[0]=='+' && B[0]=='-')   
      return 0;

   if (A[0]=='-' && B[0]=='+')   
      return 1;

   lA = strlen (A);
   lB = strlen (B);

   if (A[0]=='+' && B[0]=='+')   {
        if (lA < lB)
         return 1;
      if (lA > lB)
         return 0;

      return strcmp (A+1, B+1) < 0;            
   }
   else {
        if (lA < lB)
         return 0;
      if (lA > lB)
         return 1;

        return strcmp (A+1, B+1) > 0;      
   }
}

char* absolute ( char* A ) {
   char* B;

   B = assign (A);
   if (B[0] == '-') B[0] = '+';

   return B;
}

char* add ( char* A, char* B ) {
   char *C, *rA, *rB, *absA, *absB;
   char c;
    int i, j, lA, lB;

   lA = strlen (A);
   lB = strlen (B);
   rA = assign (A);
   rB = assign (B);   

   for (i=1, j=lA-1; i<j; i++, j--) {rA[i] ^= rA[j];rA[j] ^= rA[i];   rA[i] ^= rA[j];}
    for (i=1, j=lB-1; i<j; i++, j--) {rB[i] ^= rB[j];rB[j] ^= rB[i];   rB[i] ^= rB[j];}   

   if (A[0] == B[0]) {
      C = (char*)malloc (MAX);

        i = 1;
      c = 0;
      while (rA[i] && rB[i]) {
         C[i] = (rA[i]-'0'+rB[i]-'0'+c)%10+'0';
         c = (rA[i]-'0'+rB[i]-'0'+c)/10;
         i++;
      }
      if (rA[i])
         while (rA[i]) {
            C[i] = (rA[i]-'0'+c)%10+'0';
            c = (rA[i]-'0'+c)/10;
            i++;
         }
      else
         while (rB[i]) {
            C[i] = (rB[i]-'0'+c)%10+'0';
            c = (rB[i]-'0'+c)/10;
            i++;
         }
      if (c)
         C[i++] = '1';
      C[i] = '\0';
      C[0] = A[0];   
   }
   else
   {
      absA = absolute (A);
      absB = absolute (B);
        if (equalto (absA, absB))
         C = assign ("+0");
      else
         if (lessthan (absB, absA)) {
            C = (char*)malloc (MAX);

            for (i=lB; rA[i]; i++)
               rB[i] = '0';
            rB[lA] = '\0';

            for (i=1; rA[i]; i++) {
               if (rA[i] >= rB[i])
                  C[i] = (rA[i]-rB[i])%10+'0';
               else {
                  j = i+1;

                  while (rA[j]=='0')
                     rA[j++] = '9';
                  rA[j]--;
                  C[i] = (rA[i]-rB[i]+10)%10+'0';                              
               }
            }   

            C[lA] = '\0';
            i = lA-1;
            while (C[i]=='0' && i>1)
               C[i--] = '\0';
            C[0] = A[0];
         }
         else {
            C = (char*)malloc (MAX);

            for (i=lA; rB[i]; i++)
               rA[i] = '0';
            rA[lB] = '\0';

            for (i=1; rB[i]; i++) {
               if (rB[i] >= rA[i])
                  C[i] = (rB[i]-rA[i])%10+'0';
               else {
                  j = i+1;
                  while (rB[j]=='0')
                     rB[j++] = '9';
                  rB[j]--;
                  C[i] = (rB[i]-rA[i]+10)%10+'0';                              

               }
            }      

            C[lB] = '\0';
            i = lB-1;
            while (C[i]=='0' && i>1)
               C[i--] = '\0';
            C[0] = B[0];
         }      
   }
   for (i=1, j=strlen(C)-1; i<j; i++, j--)   {C[i] ^= C[j];C[j] ^= C[i];C[i] ^= C[j];}
   free (rA);
   free (rB);
   free (absA);
   free (absB);
   return C;
}

char* subtract ( char* A, char* B ) {   
   char *C;

   B[0] = B[0]=='+' ? '-':'+';
   C = add (A, B);
   B[0] = B[0]=='+' ? '-':'+';
   return C;
}

char* multiply ( char* A, char *B ) {
   char *C, *rA, *rB;
   int  lA, lB, i, j, c, u, v;

   if (equalto (A, "+0") || equalto (A, "-0")
      || equalto (B, "+0") || equalto (B, "-0"))
      C = assign ("+0");
   else {
      rA = assign (A);
      rB = assign (B);      
      lA = strlen (A);
      lB = strlen (B);

      for (i=1, j=lA-1; i<j; i++, j--) {rA[i] ^= rA[j];rA[j] ^= rA[i];rA[i] ^= rA[j];}
        for (i=1, j=lB-1; i<j; i++, j--) {rB[i] ^= rB[j];rB[j] ^= rB[i];rB[i] ^= rB[j];}          

        C = (char*)malloc(MAX);
        C[0] = A[0]==B[0] ? '+':'-';

      for (i=1; i<lA+lB-1; i++)
         C[i] = '0';
      
      C[lA+lB-1] = '\0';      
      
      for (i=1; rA[i]; i++) {
         c = 0;         
         for (j=1; rB[j]; j++) {   
            u = C[i+j-1]-'0';
            v = (rA[i]-'0')*(rB[j]-'0');

            C[i+j-1] = (u+v+c)%10+'0';
            c = (u+v+c)/10;
         }
         
         if (c)
            C[i+j-1] = c+'0';
      }            
      i = lA+lB-2;
      while (C[i]=='0' && i>1)
         C[i--] = '\0';        
      for (i=1, j=strlen(C)-1; i<j; i++, j--) {C[i] ^= C[j];C[j] ^= C[i];C[i] ^= C[j];}
   }
   free (rA);
   free (rB);
   return C;
}

char* sqrt ( char* A ) {
    char *B, *C, *X, *Y, *T;
   int lA, lB, lC, i, j;

   if (equalto (A, "+0") || equalto (A, "-0"))
      B = assign ("+0");
   else
      if (lessthan (A, "+0"))
         abort ( );
      else {
         C = (char*)malloc (MAX);
         lC = 0;
         C[lC++] = '+';   
         i = 1;
         C[lC++] = A[i++];
         lA = strlen (A);
         if ((lA-1)%2 == 0)    C[lC++] = A[i++];
            C[lC++] = '\0';         

         X = assign ("+0");
                  
         Y = multiply (X, X);

         while (lessthan (Y, C) || equalto (Y, C)) {
            X[1]++;
            free (Y);
            Y = multiply (X, X);
         }
         X[1]--;   

         free (Y);
         Y = multiply (X, X);

         T = C;
         C = subtract (C, Y);
         free (T);
         free (Y);

         if (equalto (C, "+0"))
                C[1] = '\0';   

         B = (char*)malloc (MAX);
         lB = 0;
         B[lB++] = '+';
         B[lB++] = X[1];
         B[lB] = '\0';                              

            for (j=i; j<lA; j+=2) {
            lC = strlen (C);
            C[lC++] = A[j];
            C[lC++] = A[j+1];
                C[lC] = '\0';

            X[1] = '0';
            
            Y = multiply (B, "+20");
            T = Y;
            Y = add (Y, X);
            free (T);
            T = Y;
            Y = multiply (Y, X);
            free (T);

            while (lessthan (Y, C) || equalto (Y, C)) {
               X[1]++;

               free (Y);
               Y = multiply (B, "+20");
               T = Y;
               Y = add (Y, X);
               free (T);
               T = Y;
               Y = multiply (Y, X);
               free (T);

            }
            X[1]--;               

            free (Y);
            Y = multiply (B, "+20");
            T = Y;
            Y = add (Y, X);
            free (T);
            T = Y;
            Y = multiply (Y, X);
            free (T);

            T = C;
            C = subtract (C, Y);
            free (T);
            free (Y);

            if (equalto (C, "+0"))
               C[1] = '\0';

            B[lB++] = X[1];
            B[lB] = '\0';                        
         }
         free (C);
         free (X);         
      }   
   return B;
}

int main()
{
   char *X, *Y;
   int nt;

   scanf ("%d", &nt);
   while (nt)
   {
      scan (&Y);
      X = sqrt (Y);
        print (X);
      putchar ('\n');
      free (X);
      free (Y);
      nt--;
   }
    return 0;   
}

What do you think about this?

P.S. Also, I think there are many algorithms for finding sqrt of number. Post them here, please.
----------------------
Thanks in advance,

[mukeshtiwari]

hi everybody i tried to solve this problem by pell's method but i m getting TLE plz help me


#include<stdio.h>
#include<string.h>
void sub(char* ,char* ,char* ,int);
void increment(char* );
int increment1(char* );
int check(char* ,int);
void print(char* ,int );
main()
{

int n,i,j,v,l;
char a[1000],b[1000],c[1000],d[1000],ch,temp[1000];
scanf("%d",&n);
scanf("%c",&ch);
for(i=0;i<n;i++)
{
scanf("%c",&ch);
gets(a);
l=strlen(a);
for(j=0;j<l;j++)
temp[l-1-j]=a[j]-'0';
for(j=0;j<l;j++)
a[j]=temp[j];
for(j=0;j<l;j++)
{
if(j==0)
b[j]=1;
else
b[j]=0;
}
for(j=0;j<l;j++)
{
c[j]=0;
d[j]=0;
}
do
{
sub(a,b,c,l);
increment(b);
increment1(d);
for(j=0;j<l;j++)
a[j]=c[j];
}while(check(c,l));

print(d,l);
if(i!=n-1)
printf("\n");
}
}

void increment(char* b)
{
int i=0,p=0,j;
//printf("b=");
b[i]=b[i]+2;
// printf("%d",b[i]);
while(b[i]>9)
{
p=b[i]/10;
b[i]=b[i]%10;
//printf("%d",b[i]);
i++;
b[i]=b[i]+p;
}
//for(j=0;j<=i;j++)
// printf("%d",b[j]);
//printf("\n");
}
int increment1(char* d)
{
int i=0,p=0,j;
//printf("d=");
d[i]=d[i]+1;
//printf("%d",d[i]);
while(d[i]>9)
{
p=d[i]/10;
d[i]=d[i]%10;
//printf("%d",d[i]);
i++;
d[i]=d[i]+p;
}
//for(j=0;j<=i;j++)
// printf("%d",d[j]);
//printf("\n");
return(i);
}

void sub(char* a, char* b, char* c,int l)
{

int j,k=0;
//printf("c=");
for(j=0;j<l;j++)
{
c[j]=(a[j]-b[j]+k+10)%10;
//printf("%d",c[j]);
if(a[j]-b[j]+k<0)
k=-1;
else
k=0;
}
//printf("\n");
}

int check(char* c,int l)
{

int i,w;
for(i=0;i<l;i++)
{
if(c[i]==0)
w=0;
else
{
w=1;
break;
}
}
return(w);
}

void print(char* e,int l)
{
int i;
i=l-1;
while(e[i]==0)
i--;
for(;i>=0;i--)
printf("%d",e[i]);
printf("\n");
}

[Moha]

Use this thread http://online-judge.uva.es/board/viewtopic.php?t=9852&highlight=10023
and please do not create a new thread on existing topics!

[mukeshtiwari]

hi friends i m trying to solve problem 10023 but getting TLE... plz help me.. or suggest some better method....
#include<stdio.h>
#include<string.h>
void initialize(char* ,char* , int);
int fun(char* ,char* ,int );
void fun1(char* ,int );
void fun2(char* ,char* ,int );

main()
{

int i,j,l,k,q,x,v,n;
char a[1001],s[1001],d[1001],ch;

scanf("%d",&n);
scanf("%c",&ch);
for(j=0;j<n;j++)
{
scanf("%c",&ch);
gets(a);
l=strlen(a);
for(i=0;i<l;i++)
a[i]=a[i]-'0';
for(i=0;i<1001;i++)
d[i]=0;
if(l%2==0)
k=1;
else
k=0;
if(k==0 && a[0]==9)
{
for(i=l;i>=1;i--)
a[i]=a[i-1];
a[0]=0;
l=l+1;
k=1;
}
q=0;
initialize(d,s,q);
while(k!=l+1)
{
initialize(d,s,q-1);
for(i=0;i<=9;i++)
{
fun1(s,i);
v=fun(a,s,k);
initialize(d,s,q-1);
if(v==-1)
break;
}

i--;
fun1(s,i);
fun2(a,s,k);

k=k+2;
d[q++]=i;
}

for(x=0;x<q;x++)
printf("%d",d[x]);
printf("\n\n");
}

}



void initialize(char* d,char* s,int q)
{

int i;
for(i=q;i>=0;i--)
s[q-i]=d[i];
for(i=q+1;i<1001;i++)
s[i]=0;

}


int fun(char* a,char* s,int k)
{

int i,v=0;

for(i=k;i>=0;i--)
{
if(a[i]-s[k-i]+v<0)
v=-1;
else
v=0;
}
return(v);
}

void fun2(char* a,char* s,int k)
{

int i,v=0;
char p;
for(i=k;i>=0;i--)
{

p=(a[i]-s[k-i]+v+10)%10;

if(a[i]-s[k-i]+v<0)
v=-1;
else
v=0;
a[i]=p;
}

}

void fun1(char* s,int i)
{

int w,p=0,g;

for(w=0;w<1001;w++)
{
s[w]=s[w]*2+p;
if(s[w]>9)
{
p=s[w]/10;
s[w]=s[w]%10;
}
else
p=0;
}
for(w=1000;w>=1;w--)
s[w]=s[w-1];
s[0]=0;
p=0;
s[0]=s[0]+i;
for(w=0;w<1000;w++)
{

if(s[w]>9)
{
p=s[w]/10;
s[w]=s[w]%10;
s[w+1]=s[w+1]+p;
}
else
p=0;
}

p=0;
for(w=0;w<1001;w++)
{
s[w]=s[w]*i+p;
if(s[w]>9)
{
p=s[w]/10;
s[w]=s[w]%10;
}
else
p=0;
}




}

[mukeshtiwari]

here r some inputs and their out put
input:
15

7206604678144

144

208656190521

15129

121

15241578750190521

975461057789971041

15241627639118169

15241578780673678515622620750190521

975461059740893157555403139789971041

152415787532388367504953515625666819450083828733760097552251181223112635269100015241588876695626775186709466270385625502210030437738149832525529662127724434100289590198780673698753238837762841030565035817735378753241425392470931290961772004267645087943911297546105808629782048750495351663801249845255296452413046792030056393881880810856075598232396311537918506325259738149672762566681955131839663400701113128821825991757354067063252553495076970028382868470725803993861332114065008382874388355434227584209785883249510700807804281329065749257735107038256363915073921712632220703375704923548818777676006706299713153483182563633639381191896050602042816308489602755677492388050602450053345566130163088725499162083798201529504648685062947721717543057492879134281400396281351287913456253619877737844840985032769419628105474075293400618777625383002591070412741960252522481346377076666750190519886267337309751562263087639079520012193273126047859425087639153757049236500533455762536198787501905199875019052100

7206604678144

9152324687831194092834914521

186755313003091766118189319724929

1

outputs:

2684512

12

456789

123

11

123456789

987654321

123456987

123456789123456789

987654321987654321

12345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890

2684512

95667782914789

13665844759951423

1

[ferrizzi]

Hi!
Try to use the function memset. It is very fast to initialize arrays of chars. More information at http://www.cppreference.com/stdstring/memset.html
Hope it helps!

[sakhassan]

Am too suffering from TLE .... don't know ... what's wrong .... .... My head has stoppped.....

Code: Select all


#include<stdio.h>
#include<string.h>
#include<stdlib.h>

#define N 1010


void rev(char from[N], char to[N])
{
   long int len;
   long int i;

   len = strlen(from);
   for(i=0;i<len;i++)
      to[i] = from[len-1-i];
   to[i]='\0';
}



void toa(int n,char t[N])
{
char a[N];
int i=0;
if(n==0)
strcpy(a,"0");
    while(n)
{
      a[i++]= (n%10)+'0';
      n/=10;
}
a[i]='\0';
rev(a,t);
}



void add(char res[N],char a[N], char b[N])
{
   
   long int len1,len2;
   char str1[N],str2[N];
   long int i;
   long int rem;
   long int sum;
   char temp[N];


   len1 = strlen(a);
   len2 = strlen(b);

   rev(a,str1);
   rev(b,str2);

   rem = 0;
   for(i=0;(i<len1 && i<len2); i++)
   {
      sum = (str1[i]-'0') + (str2[i]-'0') + rem;
      temp[i] = sum%10 + '0';
      rem = sum/10;
   }

   for(;i<len1; i++)
   {
      sum = (str1[i]-'0') + rem;
      temp[i] = sum%10 + '0';
      rem = sum/10;
   }

   for(;i<len2; i++)
   {
      sum = (str2[i]-'0') + rem;
      temp[i] = sum%10 + '0';
      rem = sum/10;
   }


   if(rem!=0) temp[i++]= rem +'0';
   temp[i]='\0';
   if(strlen(temp)==0)
      strcpy(temp,"0");
   rev(temp,res);

}
void mul(char result[N],char a[N], char b[N])
{

   char temp[N];
   char str1[N];
   char str2[N];

   long int i,j,k;
   long int len,len1,len2;

   long int res,hold;

   len1 = strlen(a);
   len2 = strlen(b);


   rev(a,str1);
   rev(b,str2);

   len = len1 + len2;

   for(i=0;i<len;i++)
      temp[i]='0';
   temp[i]='\0';


   k=-1;
   for(i=0;i<len2;i++)
   {
      hold = 0;
      for(j=0;j<len1;j++)
      {
         res = ( str1[j]-'0') * (str2[i]-'0') + hold + (temp[i+j]-'0');
         temp[i+j] = res % 10 + '0';
         hold = res/10;
         if(i+j>k)
            k= i+j;
      }

      while(hold!=0)
      {
         res = hold + (temp[i+j]-'0');
         hold = res/10;
         temp[i+j]= res%10 + '0';
         if(i+j>k)
            k = i+j;
         j++;
      }
   }


   for(;k>0 && temp[k]=='0';k--);
    temp[k+1]='\0';

   rev(temp,result);

}

void sub(char res[N],char a[N], char b[N])
{
   char str1[N];
   char str2[N];
   char temp[N];

   long int len1;
   long int len2;
   long int i;
   long int diff,rem;


   len1 = strlen(a);
   len2 = strlen(b);


   rev(a,str1);
   rev(b,str2);

   for(;len2<len1;len2++)
    str2[len2]='0';
   str2[len2]='\0';

       rem = 0;
       for(i=0;i<len1;i++)
       {
    diff = str1[i] - ( str2[i]+rem);
    if(diff<0)
    {
      rem = 1;
      temp[i] = 10 + diff + '0';

    }
    else
    {
      temp[i]=diff + '0';
      rem = 0;
    }
       }

       for(i=len1 - 1 ; i>0;i--)
       {
      if(temp[i]!='0')
       break;
       }

       temp[i+1] = '\0';

       rev(temp,res);

}

int strcmpi(char a[N], char b[N])
{
   int len1,len2;
   int i;

   len1 = strlen(a);
   len2 = strlen(b);
   if(len1>len2)
      return 1;
   else if(len1<len2)
      return -1;
   else
   {
      for(i=0;i<len1;i++)
      {
         if(a[i]>b[i])
            return 1;
         else if(a[i]<b[i])
            return -1;

      }
   }

   return 0;
}


int main()
{


   int cases;
   char odd[N],remain[N],answer[N];
   char group[3];
   int len;
   char str[N];
   int i;
   int count;
   char c[N],temp[N];

   scanf("%d",&cases);
   while(cases--)
   {
   scanf("%s",&str);

   len = strlen(str);
   strcpy(odd,"0");
   strcpy(remain,"0");
   strcpy(answer,"0");
   if(len%2)
   {
        group[0]=str[0];
        i=1;
       group[1]='\0';
   }
   else
   {
        group[0] = str[0];
        group[1] = str[1];
       group[2]='\0';
        i=2;
   }

   for(;i<len;i=i+2)
   {
      /*
      odd = 20*answer + 1;
      remain = 100*remain + group;
      */
      strcpy(temp,"");
      mul(temp,answer,"20");
      add(odd,temp,"1");

      strcpy(temp,"");
      mul(temp,remain,"100");
      add(remain,temp,group);

      count=0;
      while(strcmpi(remain,odd)>=0)//remain>=odd)
      {
         count++;
         sub(remain,remain,odd);
         add(odd,odd,"2");
         //remain-=odd;
         //odd+=2;
      }

      strcpy(temp,"");
      mul(temp,answer,"10");
      toa(count,c);
      
      add(answer,temp,c);
      //answer = 10*answer + count;

      group[0] = str[i];
       group[1] = str[i+1];
      group[2]='\0';
        
      //if(i+2<=len)
      {
         /*
            group = str[i]-'0';
            group = (group*10) + (str[i+1]-'0');
           */
      }
   }

   //if(i>2)
   {
      /*
      odd = 20*answer + 1;
      remain = 100*remain + group;
      count=0;
      while(remain>=odd)
      {
         count++;
         remain-=odd;
         odd+=2;
      }
      answer = 10*answer + count;
*/
      strcpy(temp,"");
      mul(temp,answer,"20");
      add(odd,temp,"1");

      strcpy(temp,"");
      mul(temp,remain,"100");
      add(remain,temp,group);

      count=0;
      while(strcmpi(remain,odd)>=0)//remain>=odd)
      {
         count++;
         sub(remain,remain,odd);
         add(odd,odd,"2");
         //remain-=odd;
         //odd+=2;
      }

      strcpy(temp,"");
      mul(temp,answer,"10");
      toa(count,c);
      add(answer,temp,c);
      
   }

   printf("%s\n",answer);
   //printf("%lld\n",answer);
   }

   return 0;
}


[stalf]

I've implemented it as you say, with pell's equation, but still get TLE..
This is the code:

Code: Select all

int main(){
   string result;
   string input;
   string left;
   string toDo;
   string group;
   string count;
   string a,b;
   int n,x,y;
   cin>>n;
   for(int i=0;i<n;i++){
      cin>>input;
      x = input.length();

      result = "0";
      left = "0";
      toDo = "0";
      group = "00";
      if(x%2 == 1){
         input = "0" + input;
         x++;
      }
      y = x/2;
      for(int j=0;j<y;j++){
         group.assign(input,2*j,2);
         left = sumString(result+"0",result+"0");
         left = sumString(left,"1");
         toDo = toDo + "00";
         toDo = sumString(toDo,group);
         while(toDo[0]=='0')
            toDo.assign(toDo,1,toDo.length()-1);
         while(left[0]=='0')
            left.assign(left,1,left.length()-1);
         count = "0";
         while(!smaller(toDo,left)){
            count = sumString(count,"1");
            toDo = subtract(toDo,left);
            left = sumString(left,"2");
         }
         result = result + "0";
         result = sumString(result,count);
      }
      result.assign(result,1,result.length()-1);
      }
}

I think my sum and subtract functions are slower than they should be.. but can't see how, these are their codes:

Code: Select all

string sumString(string a, string b){
   string c = "";
   string d = "0";
   int x = a.length();
   int y = b.length();
   int i = x-1;
   int j = y-1;
   int carry = 0;
   //cout<<i<<" "<<j<<endl;
   while(i>=0 || j>=0){
      if(i>=0 && j>=0){
         int aux1 = toInt(a[i]);
         int aux2 = toInt(b[j]);
         if(aux1 + aux2 + carry >=10){
            int aux3 = (aux1+aux2+carry-10);
            d[0] = toChar(aux3);
            c = d+c;
            carry = 1;
         }
         else{
            int aux3 = (aux1+aux2+carry);
            d[0] = toChar(aux3);
            c = d+c;
            carry = 0;
         }
      }
      else if(i>=0){
         int aux1 = toInt(a[i]);
         if(aux1 + carry >=10){
            int aux3 = (aux1+carry-10);
            d[0] = toChar(aux3);
            c = d+c;
            carry = 1;
         }
         else{
            int aux3 = (aux1+carry);
            d[0] = toChar(aux3);
            c = d+c;
            carry = 0;
         }
      }
      else{
         int aux1 = toInt(b[j]);
         if(aux1 + carry >=10){
            int aux3 = (aux1+carry-10);
            d[0] = toChar(aux3);
            c = d+c;
            carry = 1;
         }
         else{
            int aux3 = (aux1+carry);
            d[0] = toChar(aux3);
            c = d+c;
            carry = 0;
         }
      }
      i--;
      j--;
   }
   if(carry>0)
      c = '1' + c;
   return c;
}

string subtract(string a, string b){
   string c;
   int aux1, aux2;
   int x = a.length()-1;
   int y = b.length()-1;
   int carry = 0;
   while(x>=0 || y>=0){
      if(x>=0 && y>=0){
         aux1 = toInt(a[x]);
         aux2 = toInt(b[y]);
         if((aux1 +carry) < aux2){
            aux1 = aux1 + 10;
            c = toChar(aux1-aux2+carry) + c;
            carry = -1;
         }
         else{
            c = toChar(aux1-aux2+carry) + c;
            carry = 0;
         }
      }
      else if (x>=0){
         aux1 = toInt(a[x]);
         if((aux1 +carry) < 0){
            aux1 = aux1 + 10;
            c = toChar(aux1+carry) + c;
            carry = -1;
         }
         else{
            c = toChar(aux1+carry) + c;
            carry = 0;
         }
      }
      x--;
      y--;
   }
   while(c[0] == '0' && c.length()!=1){
      c.assign(c,1,c.length()-1);
   }
   return c;
}

[/code]