fork(3) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int digits(char* number){
  6.     int cnt=0;
  7.     for(int i=0; number[i]!='\0'; i++){
  8.         cnt++;
  9.     }
  10.     return cnt;
  11. }
  12.  
  13. void generatePalindrome(char* number){
  14.     int k=0;
  15.     int checknum=0;
  16. //if all the numbers are 9.
  17.     for(k=0; number[k]!='\0'; k++){
  18.         if(number[k]=='9'){
  19.             checknum++;
  20.         }
  21.     }
  22.  
  23.     if(checknum==k){
  24.             number[0]='1';
  25.             for(int j=1; j<k; j++){
  26.                 number[j]='0';
  27.             }
  28.             number[k]='1';
  29.             number[k+1]='\0';
  30.             return;
  31.         }
  32.  
  33.     if(k==2 && (int)number[0]<(int)number[1]){
  34.         number[0]++;
  35.         number[1]=number[0];
  36.         return;
  37.     }
  38.  
  39.     int middle = digits(number)/2;
  40. //case::EVEN NUMBER of digits.
  41.  
  42.     if(digits(number)%2==0){
  43.  
  44. //if the number to left of the middle is 
  45. //greater than the number in the right of the middle.
  46.  
  47.         if((int)number[middle-1]>(int)number[middle]){
  48.             int i = middle-1, j = middle;
  49.             while(i>=0){
  50.                 number[j]=number[i];
  51.                 i--;
  52.                 j++;
  53.             }
  54.             return;
  55.         }else{
  56.  
  57.             //if the left of middle is less than or equal to right.
  58.  
  59.             int i = middle-1, j = middle;
  60.             int temp1=i, temp2=j;
  61.  
  62.             // if there are successive equal numbers in the middle 
  63.             //check for the first unequal number to the left to be 
  64.             //greater than the first unequal right.
  65.  
  66.             if(number[temp1]==number[temp2] && temp1!=0){
  67.                 while((int)number[temp1]==(int)number[temp2] && temp1!=-1){
  68.                     temp1--;
  69.                     temp2++;
  70.                 }
  71.                 //copy all numbers to the left to the right
  72.                 if((int)number[temp1]>(int)number[temp2] && temp1!=-1){
  73.                     while(temp1>=0){
  74.                         number[temp2]=number[temp1];
  75.                         temp1--;
  76.                         temp2++;
  77.                     }
  78.                     return;
  79.                 }
  80.             }
  81. // special case if the number is 9,, make that number 0 and 
  82. // increse the next (!9) by 1.
  83.             if(number[i]!='9'){
  84.                 number[i]++;
  85.                 while(i>=0){
  86.                     number[j]=number[i];
  87.                     i--;
  88.                     j++;
  89.                 }
  90.                 return;
  91.             }else{
  92.                 int temp1=i;
  93.                 while(number[temp1]=='9'){
  94.                     number[temp1]='0';
  95.                     temp1--;
  96.                 }
  97.                 number[temp1]++;
  98.                 while(i>=0){
  99.                     number[j]=number[i];
  100.                     i--;
  101.                     j++;
  102.                 }
  103.                 return;
  104.             }
  105.  
  106.  
  107.         }
  108.  
  109.     }else{
  110.  
  111.         //similar for ODD NUMBERS IN THE SAME ORDER AS EVEN NUNBERS;
  112.         //Except....increase the middle number by one if the number
  113.         //to the left is less than the number to the right.
  114.  
  115.         if((int)number[middle-1]>(int)number[middle+1]){
  116.             int i=middle-1, j=middle+1;
  117.             while(i>=0){
  118.                 number[j]=number[i];
  119.                 i--;
  120.                 j++;
  121.             }
  122.             return;
  123.         }else{
  124.             int i=middle-1, j=middle+1;
  125.             int temp1 = i, temp2=j;
  126.             if(number[middle]!='9'){
  127.  
  128.                if(number[temp1]==number[temp2] && temp1!=0){
  129.                     while((int)number[temp1]==(int)number[temp2] && temp1!=-1){
  130.                         temp1--;
  131.                         temp2++;
  132.                     }
  133.                     if((int)number[temp1]>(int)number[temp2] && temp1!=-1){
  134.                         while(temp1>=0){
  135.                             number[temp2]=number[temp1];
  136.                             temp1--;
  137.                             temp2++;
  138.                         }
  139.                         return;
  140.                     }
  141.  
  142.                }
  143.  
  144.                 number[middle]++;
  145.                 while(i>=0){
  146.                     number[j]=number[i];
  147.                     i--;
  148.                     j++;
  149.                 }
  150.                 return;
  151.             }else{
  152.  
  153.                 if(number[temp1]==number[temp2] && temp1!=0){
  154.                     while((int)number[temp1]==(int)number[temp2] && temp1!=-1){
  155.                         temp1--;
  156.                         temp2++;
  157.                     }
  158.                     if((int)number[temp1]>(int)number[temp2] && temp1!=-1){
  159.                         while(temp1>=0){
  160.                             number[temp2]=number[temp1];
  161.                             temp1--;
  162.                             temp2++;
  163.                         }
  164.                         return;
  165.                     }
  166.  
  167.                }
  168.  
  169.                 number[middle]='0';
  170.                 number[i]++;
  171.  
  172.                 while(i>=0){
  173.                     number[j]=number[i];
  174.                     i--;
  175.                     j++;
  176.                 }
  177.                 return;
  178.  
  179.             }
  180.         }
  181.     }
  182. }
  183.  
  184. int main(){
  185.     ios_base::sync_with_stdio(false);
  186.     cin.tie(NULL);
  187.  
  188.     int t;
  189.     cin>>t;
  190.     cin.ignore();
  191.  
  192.     while(t--){
  193.         char number[1000000];
  194.         cin.getline(number,1000000);
  195.  
  196.         int checklead = 0;
  197.         if(number[0]=='0'){
  198.             for(int k=0; number[k]=='0'; k++){
  199.                 checklead++;
  200.             }
  201.         }
  202.  
  203.         if(digits(number)==0){
  204.             printf("\n");
  205.             continue;
  206.         }
  207.  
  208.         if(digits(number+checklead)==1){
  209.             if(number[0+checklead]!='9'){
  210.                 number[0+checklead]++;
  211.             }else{
  212.                 number[0+checklead]='1';
  213.                 number[1+checklead]='1';
  214.                 number[2+checklead]='\0';
  215.             }
  216.             printf("%s\n", number+checklead);
  217.             continue;
  218.         }
  219.         generatePalindrome(number+checklead);
  220.         printf("%s\n", number+checklead);
  221.     }
  222.  
  223.     return 0;
  224. }
  225.  
Success #stdin #stdout 0s 4524KB
comments (?)
stdin
copy 
5
000003
808
9999
0000
123495123
stdout
copy 
4
818
10001
1
123505321
https://ideone.com/GzRS81
problem PALIN, based on SPOJ submission 25665239 (CPP14), 2020-03-31 14:13:25
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!