TopCoder Forums

Get Time

Member Search

forums

		Search \| Watch Thread \| My Post History \| My Watches \| User Settings View: Flat (newest first) \| Threaded \| Tree Previous Thread \| Next Thread
Forums Tutorial Discussions Maximum Flow tutorial EDUCATIONAL DISCUSSION - spoj problem

Mon, Aug 10, 2009 at 10:19 AM EDT

EDUCATIONAL DISCUSSION - spoj problem | Reply

gvnavin32_4u
18 posts

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

Tue, Aug 11, 2009 at 12:13 PM EDT

Re: EDUCATIONAL DISCUSSION - spoj problem (response to post by gvnavin32_4u) | Reply

FameofLight
534 posts

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.

Wed, Aug 12, 2009 at 8:15 AM EDT Re: EDUCATIONAL DISCUSSION - spoj problem (response to post by FameofLight) \| Reply
gvnavin32_4u 18 posts	thank you very much

Wed, Aug 12, 2009 at 8:24 AM EDT

Re: EDUCATIONAL DISCUSSION - spoj problem (response to post by gvnavin32_4u) | Reply

gvnavin32_4u
18 posts

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

Wed, Aug 12, 2009 at 8:29 AM EDT

Re: EDUCATIONAL DISCUSSION - spoj problem (response to post by FameofLight) | Reply

gvnavin32_4u
18 posts

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

1 edit | Thu, Aug 13, 2009 at 2:15 PM EDT

Re: EDUCATIONAL DISCUSSION - spoj problem (response to post by gvnavin32_4u) | Reply

jbernadas
561 posts

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

Sat, Oct 16, 2010 at 8:49 AM EDT Re: EDUCATIONAL DISCUSSION - spoj problem (response to post by FameofLight) \| Reply
navinag 10 posts	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.

Wed, Jul 26, 2017 at 7:30 AM EDT Re: EDUCATIONAL DISCUSSION - spoj problem (response to post by gvnavin32_4u) \| Reply
hennerywatson 2 posts	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); } }

Forums Tutorial Discussions Maximum Flow tutorial EDUCATIONAL DISCUSSION - spoj problem
Previous Thread | Next Thread