My Weblog

Blog about programming and math

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";*/
		}	
		
	}
Advertisements

December 6, 2010 - Posted by | Programming

No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: