|
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"); } } |