Wrong<-<-<-<- Slow Answer [SPOJ]

sanddy1911 (45)
I recently here about SPOJ 'Sphere Online Judge' So i signed up and answered the first question and the question was
Question

A positive integer is called a palindrome if its representation in the decimal system is the same when read from left to right and from right to left. For a given positive integer K of not more than 1000000 digits, write the value of the smallest palindrome larger than K to output. Numbers are always displayed without leading zeros.

Input

The first line contains integer t, the number of test cases. Integers K are given in the next t lines.

Output

For each K, output the smallest palindrome larger than K.

Example

Input:
2
808
2133

Output:
818
2222

So i coded the program as best i can and the program is
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
#include <stdio.h>
#include <string.h>
char c[1000000];
void nextpoli()
{
    int m,i=0,tm=0,t2=strlen(c);
    if(!((t2)&1)) {m = t2/2-1; tm++;}
    else m = t2/2;
    if(c[m]<c[m+1]) {c[m]+=1; c[m+1] = c[m]-1;}
    while(i<(m+tm)) {c[t2-i-1]=c[i]; ++i;}
}
main()
{
    int t, i;
    scanf("%d", &t);
    while(t--) {
    fflush(stdin);
    gets(c);
    nextpoli();
    printf("%s\n",c);
}
return 0;
}



But why the hell they are saying the answer is wrong whereas in my PC its run great.

Give me Some !dea to make this program run and make it more short.
Anything you can will be commendable


But why the hell they are saying the answer is wrong whereas in my PC its run great.

New Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
 
#include <stdio.h>
#include <string.h>

#define BOOL short int
#define TRUE 1
#define FALSE 0

#define MAX 1000002
#define PRE c[m-i]
#define NXT c[m+i+tm]

/* t: Number of Cases.
   len: String Length.
   m: Mid of String Length (tm: 1 if even 0 if odd).
   i: Counter.                                      */

char c[MAX];
BOOL increaseIn(int m, short int tm)
{
    int i=-1;
        while(++i<m&&(PRE=='9')) PRE=NXT='0';
    if(PRE=='9') {
            NXT='0';
            c[0]='1';
            c[m+i+tm+1]='1';
            c[m+i+tm+2]='\0';
            return FALSE;
    }
    PRE+=1;
    NXT=PRE;
    return TRUE;
}
void nextpoli()
{
    int len=strlen(c);
    int m=len/2;
    int i=-1;
    short int tm=0;
    if(!(len&1)) {
            tm=1;
            m--;
    }
    while(++i<m&&(PRE==NXT));
    if(PRE>NXT) NXT=PRE;
    else {
        --i;
        if(!increaseIn(m, tm)) return ;
    }

    while(i++<=(m+tm)) NXT=PRE;
}
main()
{
    int t;
    scanf("%d",&t);
    while(t--) {
    scanf("%s",c);
    nextpoli();
    printf("%s\n",c);
}
return 0;
}

Now its Taking 0.11 sec to execute but i want it to execute within 0.03 Sec

Edit: Code.
Last edited on
Duthomhas (13282)
Try your program for k=122 (gives a smaller answer) and k=1 (gives an answer not larger than k).

Also, that fflush(stdin); in there might be causing you grief. That's non-standard stuff and--even if it works--will kill any script the judges are using to test your program. Get rid of it and add a dummy gets(c) between lines 15 and 16.

(I hope you are aware that using gets() is a no-no also, but it shouldn't be an issue here.)

Hope this helps.
sanddy1911 (45)
I don't understand what you want to say by first line but for the second line if i remove fflush(stdin) than it will run only for t-1 cases and after doing all that i get wrong answer on SPOJ.
sanddy1911 (45)
And what do you think about
scanf(" %[^\n]", c);
Duthomhas (13282)
You cannot read half an answer and assume that it is incorrect.

Did you try running your program with 122 and 1 as input for K?
Script Coder (1468)
Topic archived. No new replies allowed.