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] ); } }
No comments yet.
Leave a comment