My Weblog

Blog about programming and math

SPOJ GLJIVE

GLJIVE statement is not very clear but in order means contiguous starting from first . Starting from first , keep adding next element and check its proximity to 100 and the one which is more near to 100 is answer . For test case , the contiguous sequence is 10 + 20 + 30 + 40 not the last 100 .

#include<cstdio>
#include<iostream>
#include<vector>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
int v[10] ;
int ret[10] , val ;
vector<int> diff_p , diff_n;
int main()
	{
		memset ( ret , 0 , sizeof ret );
		diff_p.clear() , diff_n.clear();

		for(int i=0;i<10;i++) scanf("%d",&v[i]);
		for(int i=0 ;i <10 ; i++) ret[i] = v[i];

		for(int i = 1 ; i < 10 ; i++) ret[i] += ret[i-1];
		for(int i=0 ; i<10 ; i++) if ( ret[i] < 100 ) diff_n.push_back( ret[i] - 100 ); else diff_p.push_back( ret[i] - 100 );
		
		sort( diff_n.rbegin() , diff_n.rend() );
		sort( diff_p.begin() , diff_p.end());
		if( diff_p.empty() ) cout << 100 + diff_n[0] <<endl;
		else if ( diff_n.empty() ) cout << 100 + diff_p[0] <<endl;
		else if ( diff_p[0] <= abs ( diff_n[0] ) ) cout<< 100 + diff_p[0] <<endl;
		else cout<<100 +  diff_n[0] <<endl;
		
	}

Accepted Haskell code for this problem.

import Data.List

solve :: [Integer] -> String
solve xs = show y ++"\n" where 
	(p , q) = span ( < 0 ) . map ( \x -> x - 100 ) . tail . scanl (+) 0 $ xs 
	p' = sortBy ( \ x y -> compare y x ) p 
	q' = sort q 
	y = if null q' then 100 + head p' 
	       else 
		 if null p' then 100 + head q' 
		   else 
		     if ( head q' ) <= ( abs.head $ p' ) then 100 + head q'  else 100 + head p'


main = interact $  solve . map read . concat . map words . lines
	
Advertisements

May 20, 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: