Областная олимпиада по информатике 2013-2014

Натуральное число называется если читается слева направо и справа налево одинаково. Вам дано одно натуральное число $N$, которое состоит из не более чем $10^6$ цифр. Найдите наименьший палиндром, который строго больше $N$.

Входные данные

В единственной строке входного файла содержится одно натуральное число $N$. $N$ не содержит лидирующих нулей и состоит из не более чем $10^6$ цифр.

Выходные данные

Выведите одно целое число – наименьший палиндром, который строго больше N.

Примеры:

Вход:

365

Ответ:

373

Вход:

999999

Ответ:

1000001

Комментарий/решение

AC

показать/скрыть код

#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
  string a,k,ans="";
  long long int e=0;
  bool ok=0;
  string calc(string a){
  reverse(a.begin(),a.end());
  k.clear();
  ans.clear();
  e=1;
  for(int i=0;i<a.size();i++){
    k+=(((a[i]-48)+e)%10)+48;
    e=((a[i]-48)+e)/10;
  }
  if(e==1)ans+='1';
  reverse(k.begin(),k.end());
  ans+=k;
  return ans;
  }
int main(){
  cin>>a;
  a=calc(a);
  if(a.size()&1){
    string w="";
  	for(int i=0;i<a.size()/2;i++)w+=a[i];
  	string k1=w+a[a.size()/2];
  	reverse(w.begin(),w.end());
  	k1+=w;
  	reverse(w.begin(),w.end());
  	string k2=calc(w+a[a.size()/2]),t="";
  	for(int i=0;i<k2.size()-1;i++)t+=k2[i];
  	k2+=t;
  	if(a<k1)cout<<k1;
  	else cout<<k2;
  }
  else {
  	string w="";
  	for(int i=0;i<a.size()/2;i++)w+=a[i];
  		reverse(w.begin(),w.end());
  		string k1=w;
  		reverse(w.begin(),w.end());
  		k1=w+k1;
  		w=calc(w);
  		reverse(w.begin(),w.end());
  		string k2=w;
  		reverse(w.begin(),w.end());
  		k2=w+k2;
  		if(a<k1)cout<<k1;
  		else cout<<k2;
  		return 0;
  }
}

C++

Copy

показать/скрыть код

#include<bits/stdc++.h>
using namespace std;
#define ll long long
stringstream f;
bool ff(string c){
    ll ans=0, i=0;
    if(c.size()%2!=0){
    while(i<c.size()/2+1){
        if(c[i]==c[c.size()-i-1])ans++;
        i++;
    }
    if(c.size()%2==0){
        if(ans==c.size()/2)return true;
    }
    else {
        if(ans==c.size()/2+1)return true;
    }}
    if(c.size()%2==0){
    while(i<c.size()/2){
        if(c[i]==c[c.size()-i-1])ans++;
        i++;
    }
    if(c.size()%2==0){
        if(ans==c.size()/2)return true;
    }
    else {
        if(ans==c.size()/2+1)return true;
    }}
}
ll check(ll m){
 string s;
 while(m<1000001)
    {
        m++;
        f<<m;
        f>>s;
        if(ff(s)){
           return  m;
        }f.clear();s.clear();

 }
}
int main () {
	ios_base::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	ll n;
	cin>>n;
	cout<<check(n);
        	}

C++

Copy

n=int(input())+1

n_str=str(n)

a=n_str[::]

b=n_str[::-1]

while a!=b:

n+=1

n_str=str(n)

a=n_str[::]

b=n_str[::-1]

print(n)