IdeaMonk

thoughts, ideas, code and other things...

Wednesday, July 09, 2008

SPOJ PALIN

#include <iostream>
#include <vector>
using namespace std;

bool compare(vector<int> n1,vector<int> n2,int half){
// if n1>n2 for problem size(n1) == size(n2)
for (int i=n1.size()-1;i>=half;i--){
if (n1[i]!=n2[i])
return n1[i]>n2[i];
}
return false;
}

void work(vector<int>& num, int pos1, int pos2) {
if (pos1 < 0) {
num[num.size()-1] = 1;
num.insert(num.begin(), 1);
return;
} else
if (num[pos1] < 9) {
num[pos1] = num[pos2] = num[pos1] + 1;
return;
} else {
num[pos1] = num[pos2] = 0;
work(num, pos1-1, pos2+1);
return;
}
}

main (){
char n;
vector<int> num,old;
int half,ssize;

n=getc(stdin);
while (n!='\n'){
num.push_back(n-'0');
n=getc(stdin);
}
while (num.size()>=1 && num[0]!=0){
old = num;
ssize=num.size();
if (ssize%2==0){
//even
half=ssize/2;
//mirror into vector
for (int i=0;i<half;i++){
num[ssize-1-i]=num[i];
}
if (compare(num,old,half)){
for (int i=0;i<ssize;i++){
printf ("%d",num[i]);
}
printf ("\n");
} else {
work (num,half-1,half);
ssize=num.size();
for (int i=0;i<ssize;i++){
printf ("%d",num[i]);
}
printf ("\n");
}
} else {
//odd
half=ssize/2 ;
//mirror into vector
for (int i=0;i<half;i++){
num[ssize-1-i]=num[i];
}
if (compare(num,old,half)){
for (int i=0;i<ssize;i++){
printf ("%d",num[i]);
}
printf ("\n");
} else {
work (num,half,half);
ssize=num.size();
for (int i=0;i<ssize;i++){
printf ("%d",num[i]);
}
printf ("\n");
}
}
num.clear();
n=getc(stdin);
while (n!='\n'){
num.push_back(n-'0');
n=getc(stdin);
}
}
}
Don't start smiling at the code above, thinking that you've got the solution!
The problem with the above is that its a TLE for SPOJ. If you can spot or fix the problem with the code, the points are free for you to grab. And if you are a little benevolent then do consider hinting me too on the shortcomings of this problem.
Adios

Labels: ,

0 Comments:

Post a Comment

Subscribe to Post Comments [Atom]

<< Home