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
| #include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define INF 1<<30
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
string func(string a,string b) {
string ret;
if(a.size() < b.size()) swap(a,b);
reverse(a.begin(),a.end());
reverse(b.begin(),b.end());
int carry = 0;
rep(i,b.size()) {
int x = a[i] - '0';
int y = b[i] - '0';
int z = x + y + carry;
carry = z / 10;
ret.push_back('0' + (z%10));
}
REP(i,b.size(),a.size()) {
int x = a[i] - '0';
int z = x + carry;
carry = z / 10;
ret.push_back('0' + (z%10));
}
if(carry) ret.push_back('0' + carry);
reverse(ret.begin(),ret.end());
return ret;
}
class NextPalindromicNumber {
public:
string getNext(string n) {
int sz = n.size();
string s = n.substr(0, (sz + 1) / 2), t;
if(sz % 2 == 0) {
t = s;
} else {
t = s.substr(0, s.size()-1);
}
reverse(t.begin(), t.end());
t = s + t;
if(sz == t.size() && t > n) {
return t;
}
string a = func(s, "1");
string b;
if(a.size() == (sz + 1) / 2) {
if(sz % 2 == 0) {
b = a;
} else {
b = a.substr(0, a.size()-1);
}
} else {
b = a.substr(0, a.size()-1);
if(sz % 2 == 1) {
a = a.substr(0, a.size()-1);
}
}
// if(sz % 2 == 0 && a.size() == (sz + 1) / 2) {
// b = a;
// } else {
// b = a.substr(0, a.size()-1);
// }
reverse(b.begin(), b.end());
return a + b;
}
};
|