My Weblog

SPOJ Problem ABSURD

This problem ask you to find to a integer in range [0.95*c,1.05*c] whose absurdity is less than c. One way is to brute force but this will time limit exceed. Others are you take higher limit and keep putting 5 and 0 on last and check if higher number is still larger than lower and keep calculating absurdity of number this way . Source code for problem.

```#include<cstdio>
#include<iostream>
using namespace std;

int absurdity(int n)
{
int cnt=0;
bool f=0;
while(n%10==0) n/=10;

if(n%10==5) f=1;
while(n) cnt++,n/=10;

if(f==1) return 2*cnt-1;
else  return 2*cnt;

}
string int2string(int n)
{
string s="";
while(n) s=char(n%10+'0') + s,n/=10;
return s;
}
int string2int(string s)
{
int tmp=0;
for(int i=0;i<s.size();i++) tmp=tmp*10+(s[i]-'0');
return tmp;
}
int main()
{
int t,c,abrd_c,abrd_t;
bool f;
for(scanf("%d",&t);t>0;t--)
{
scanf("%d",&c);
abrd_c=absurdity(c);
int l=0.95*c,h=1.05*c;
abrd_t=absurdity(h);
string s=int2string(h);

//cout<<l+1<<" "<<h<<" "<<abrd_c<<endl;
f=1;
string tmp=s;
if(tmp[tmp.size()-1]>='5')
{
char ss=tmp[tmp.size()-1];
tmp[tmp.size()-1]='5';
if(string2int(tmp)>=(l+1)) abrd_t=absurdity(string2int(tmp));
else
{
tmp[tmp.size()-1]=ss;
f=0;
}
}
if(tmp[tmp.size()-1]>='0')
{
char ss=tmp[tmp.size()-1];
tmp[tmp.size()-1]='0';
if(string2int(tmp)>=(l+1)) abrd_t=absurdity(string2int(tmp));
else
{
tmp[tmp.size()-1]=ss;
f=0;
}
}

for(int i=tmp.size()-2;i>=1 && f;i--)
{
char ss=tmp[i];
if(tmp[i]>='5')
{
tmp[i]='5';
if(string2int(tmp)>=(l+1)) abrd_t=absurdity(string2int(tmp));
else //we are not able to decrease this number further
{
tmp[i]=ss;
f=0;
}
}
if(tmp[i]>='0')
{
tmp[i]='0';
if(string2int(tmp)>=(l+1)) abrd_t=absurdity(string2int(tmp));
else
{
tmp[i]=ss;
f=0;
}
}
}

if(abrd_t<abrd_c) cout<<"absurd\n";
else cout<<"not absurd\n";
//till now i have checked for last position.now start from second last keep doing until

/*for(int i=l+1;i<=h;i++) //calculate the min absurdity in the given range
{
abrd_t=absurdity(i);
cout<<i<<" "<<abrd_t<<endl;
if(abrd_t<abrd_c) {f=1;break;}
}
if(f==1) cout<<"absurd\n";
else cout<<"not absurd\n";*/
}

}
```