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");
}
}
Re: EDUCATIONAL DISCUSSION - spoj problem (response to post by gvnavin32_4u) | Reply
First
1. You should use cpp tags for posting your codes
2. You should post a link to problem so that everyone can understand , what problem you are taking about.

Second:

About the problem , your code is too slow .

I am giving you a pseudocode
input : s[1...N]
output : next palindrome
Algorithm :
         len <- s.length
         i <- 1 , j <- N
         while i < j:
             if s[i]>=s[j]:
                       s[j] <- s[i]
             else
                Add(s, 10^(len-j+1))
                s[i] <- s[j]
             i <- i+1
             j <- j-1
 
         print s
 
Here a^b mean a raise to the power b.
Re: EDUCATIONAL DISCUSSION - spoj problem (response to post by FameofLight) | Reply
thank you very much
Re: EDUCATIONAL DISCUSSION - spoj problem (response to post by gvnavin32_4u) | Reply
another sopj problem...........
i coded it.......
it shows something runtime error..........

the question is here
https://www.spoj.pl/AU4/problems/KWORK/ (pls visit)

here is my code tell me what error i made pls.................

the error i got is
runtime error
(SIGSEGV)

pls explain about this kind of errors............

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

int main()
{
while(1)
{
int n,k;

scanf("%d %d",&n,&k);

if( n == 0 && k == 0 ) break;

int a[1000],i,j;

for(i = 0 ; i < n ; i++ )
scanf("%d",&a[i]);

long long int max = 0;

for( i = 0 ; i < k+1 ; i++ )
{
long long int sum = 0;

for( j = i ; j < n ; j = j + k + 1 )
sum = sum + a[j] ;

if( sum > max )
max = sum ;
}

printf("%lld\n",max);
}

return 0;
}
Re: EDUCATIONAL DISCUSSION - spoj problem (response to post by FameofLight) | Reply
see this question also pls
https://www.spoj.pl/AU4/problems/FCFS/

in that selecting the minimum quantum to convert the round robin into fcfs....for that i used to select the maximunm quantum value.......
is it correct approach....or my approach is wrong....
pls tell me

i got wrong answer...........

my code is:

#include<iostream>
#include<cstdio>
#include<cassert>
using namespace std;

main()
{
while(1)
{
int n;
scanf("%d",&n);

if(n == 0)
break;

int max,t;

scanf("%d",&max);
n--;

while(n--)
{
scanf("%d",&t);

if( t > max )
max = t;
}

printf("%d\n",max);
}
}
Re: EDUCATIONAL DISCUSSION - spoj problem (response to post by gvnavin32_4u) | Reply
┬┐Can you please stop spamming this forum? This forum is dedicated to explain the max-flow algorithm. Also, you have no intention of following the rules, as you are not using the cpp tag (that FameofLight shown you).

Also, using extra dots is bad seen around here, and probably there are existing posts for the problems you are asking for.

And finally, you cross posted the PALIN question. If you read well, above the posting box there is this warning:

Please do not cross post, most people read all posts and will not appreciate reading yours twice.

I think admins should make that one Arial Black 36.
Re: EDUCATIONAL DISCUSSION - spoj problem (response to post by FameofLight) | Reply
if we apply your algorithm to "54123400" the answer will be "54444445".
but the next palindrome will be "54200245".
correct me if I am wrong.
Re: EDUCATIONAL DISCUSSION - spoj problem (response to post by gvnavin32_4u) | Reply
my code is:
minimum quantum to convert the round robin into fcfs university assignment help
#include<iostream>
#include<cstdio>
#include<cassert>
using namespace std;

main()
{
while(1)
{
int n;
scanf("%d",&n);

if(n == 0)
break;

int max,t;

scanf("%d",&max);
n--;

while(n--)
{
scanf("%d",&t);

if( t > max )
max = t;
}

printf("%d\n",max);
}
}
RSS