JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat  | Threaded  | Tree
Previous Thread  |  Next Thread
EDUCATIONAL DISCUSSION - spoj problem | Reply
i tried to solve next palindrome problem in that number length 10^6
so i used string manipulation i get tle . problem name palin 5 th problem in spoj

here is my code..........
sorry my code is two large..........
can anyone suggest the another way to solve it

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cstdlib>
#define all(v) (v).begin() , (v).end()
#define MAX 1000000
using namespace std;

string add1 (char a[],char b[],int &x)
{
string c;
int d;
int i,j;

for( j = strlen(b) - 1, i = strlen(a) - 1 ; j >= 0 ; i--, j-- )
{
d = (a[i]-'0') + (b[j]-'0') + x ;
x = d %10 ;
c = c + (char)(x + '0');
x = d/10 ;
}

reverse( all(c) );
return c;
}

string add2(char c[],int &x)
{
int d ,a = 0;
string str;
for(int i = strlen(c) - 1; i >= 0; i--)
{
d = ( c[i] - '0' ) + x + a;
str = str + (char) ( (d % 10 )+ '0');
x = x / 10 ;
a = d / 10 ;
}
reverse( all(str) );
x = a;
return str;
}

string add(char a[],char b[])
{

char c[MAX];
int x = 0;

c[abs( (long int) ( strlen(a)-strlen(b) ) )]='\0';
string s;

if( strlen(a)!= strlen(b) )
{
s = add1(strlen(a) > strlen(b) ? a : b,strlen(a) < strlen(b) ? a : b ,x);
strncpy(c,strlen(a) > strlen(b) ? a : b,abs( (long int) ( strlen(a)-strlen(b) ) ) ) ;
s = add2(c,x) + s;
if(x != 0) s = (char)(x + '0')+s;

}
else
{
s = add1(a, b ,x);
if(x != 0) s = (char)(x + '0')+s;
}

return s;
}

bool check9(char *a)
{
int i;
for( i = 0 ; i < (int)strlen(a) ; i++ )
{
if( a[i] != '9' )
return false;
}
return true;
}

void rev(string str)
{
for(int i = str.length()-1 ; i >= 0 ; i--)
cout<<str[i];
}

int checkodd(char a[],int mid)
{

for( int i = 1 ; i ><= mid ; i++ )
{
if( a[mid - i] != a[mid + i] )
{
if( (a[mid-i]-'0') > (a[mid+i]-'0') )
return 1;
else
return 2;
}
}
return 0;
}

int checkeven(char a[],int mid)
{
for(int i = 0 ; i < mid ; i++ )
{
if( a[mid-i-1] != a[mid+i] )
{
if(a[mid-i-1] > a[mid+i])
return 1;
else
return 2;
}
}
return 0;
}

int main()
{
int n;
scanf("%d",&n);
while(n--)
{
char a[MAX],b[MAX];
scanf("%s",a);

if( check9(a) )
{
b[0]='2';
b[1]='\0';
cout<<add(a,b);
}
else if( strlen(a) % 2 != 0 ) // odd
{
int mid = strlen(a) / 2 ;
char c[MAX],midch;
strncpy(c,a,mid);
c[mid] = '\0';

switch( checkodd(a,mid) )
{
case 0: //both sides equal
case 2: // second side greater
if( a[mid] == '9' )
{
midch = '0';
b[0]='1';
b[1]='\0';
string str = add(c,b);
cout><<str<<midch;
rev(str);
}
else if (a[mid] >< '9')
{
cout<<c><<a[mid]-'0' + 1;
rev((string)c);
}
break;

case 1: // first side greater
cout<<c><<a[mid];
rev((string)c);
break;

}
}
else // even
{
int mid = strlen(a)/2;
char c[MAX];
switch( checkeven(a,mid) )
{
case 1:

strncpy(c,a,mid);
c[mid] = '\0';
cout<<c;
rev((string)c);
break;

case 2: //second side greater
case 0: //equal
strncpy(c,a,mid);
c[mid] = '\0';

char b[2];

b[0] = '1';
b[1] = '\0';
string str = add(c,b);
cout><<str;
rev(str);
break;
}

}
printf("\n");
}
}
Subject Author Date
EDUCATIONAL DISCUSSION - spoj problem gvnavin32_4u Aug 10, 2009 at 10:19 AM EDT
Re: EDUCATIONAL DISCUSSION - spoj problem FameofLight Aug 11, 2009 at 12:13 PM EDT
Re: EDUCATIONAL DISCUSSION - spoj problem gvnavin32_4u Aug 12, 2009 at 8:15 AM EDT
Re: EDUCATIONAL DISCUSSION - spoj problem gvnavin32_4u Aug 12, 2009 at 8:24 AM EDT
Re: EDUCATIONAL DISCUSSION - spoj problem gvnavin32_4u Aug 12, 2009 at 8:29 AM EDT
Re: EDUCATIONAL DISCUSSION - spoj problem jbernadas Aug 13, 2009 at 2:15 PM EDT
Re: EDUCATIONAL DISCUSSION - spoj problem navinag Oct 16, 2010 at 8:49 AM EDT
Re: EDUCATIONAL DISCUSSION - spoj problem hennerywatson Jul 26, 2017 at 7:30 AM EDT
RSS