SPOJSolutions/PALIN.cpp at master · narutoamu/SPOJSolutions · GitHub

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include <iostream>
#include <string.h>

using namespace std;

void ShowArray(char x[], int n)
{
	for (int i = 0; i < n; ++i)
		cout<<x[i];
	cout<<endl;
}

bool IsAllNines(char x[], int n)
{
	for (int i = 0; i < n; ++i)
		if(x[i] != '9')
			return false;
	return true;
}

bool IsPalindrome(char x[], int n)
{
	for (int i = 0; i < n; ++i)
		if(x[i] != x[n-i-1])
			return false;
	return true;
}

bool Add(char x[], int index, int n)
{
	x[index]++;
	if(n-index-1 != index)
		x[n-index-1]++;

	if(x[index] == ':')
	{
		x[index] = '0';
		x[n-index-1] = '0';
		return true;
	}
	return false;
}

void Next(char x[], int n)
{
	int i = (n-1)/2;
	while(Add(x, i, n))
		i--;
}

bool MGreater(char m[], char x[], int n)
{
	for(int i = 0; i < n; i++)
		if(m[i] > x[i])
			return true;
		else if(m[i] < x[i])
			return false;
}

void ShowNextPalindrome(char x[], int n)
{
	if(IsAllNines(x, n))
	{
		cout<<1;
		for(int i = 0; i < n-1; i++)
			cout<<0;
		cout<<1<<endl;
	}

	else if(IsPalindrome(x, n))
	{
		Next(x, n);
		ShowArray(x, n);
	}

	else
	{
		char m[1000001];

		for(int i = 0; i < n/2 ; i++)
			m[i] = x[i];
		for(int i = n/2; i < n; i++)
			m[i] = x[n-i-1];

		if(MGreater(m, x, n))
			ShowArray(m, n);
		else
			ShowNextPalindrome(m, n);
	}
}

int main()
{
	int t;
	cin>>t;
	while(t-- && t >= 0)
	{
		char x[1000001];
		cin>>x;
		ShowNextPalindrome(x, strlen(x));
	}
	return 0;
}