My Weblog

Blog about programming and math

SPOJ Sort fractions

Sort fractions requires a bit of optimization. Don’t generate the whole series , just generate up to the half [ num = 1 and denum = 2 ] and calculate other half from this. Also i got TLE for vectors so don’t use it. This code is merely transformation of python code given on wiki.

#include<cstdio>
#include<iostream>
#include<vector>
using namespace std;
int v_n[7800000] , v_d[7800000] ;

void generate_seq(int n )
	{
		
		v_n[0] = 0 , v_n[1] = 1 ;
		v_d[0] = 1  ,v_d[1] =  n  ;
		if(n<2) return ;
		if( n == 2 ) { v_n[2] = 1 ; v_d[2] = 1  ; return ; } 
		int k , k_1 , k_2 , ne = 2 ;
		for(int i=2 ; ; i++ )
		 {
			k = ( n + v_d[i-2] ) / v_d[i-1] ;
			k_1 = k * v_n[i-1] - v_n[i-2] ;
			k_2 = k * v_d[i-1] - v_d[i-2] ;
			v_n[i] = k_1 ;
			v_d[i] = k_2 ;
			ne++;
			if(k_1 == 1 and k_2 == 2 ) break;
			 
		}
		
	
		for(int i = ne-2 ; i >= 0 ; i--) 
		{
			k_1 = v_d[i] - v_n[i];
			v_n[ne] = k_1 ;
			v_d[ne] = v_d[i] ;
			ne++;
		}
			
		return;
	}

int main()
	{	
		int n , m , t , k ;
		for(scanf( "%d" , &t ) ; t > 0 ; t-- )
		{
			scanf("%d%d",&n, &m);
			generate_seq( n );
			for( ; m > 0 ; m-- ) scanf("%d" , &k) , printf("%d/%d\n", v_n[k-1] , v_d[k-1] ); 
		}
	}

	
		
Advertisements

May 17, 2011 - 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: