[ create a new paste ] login | about

Link: http://codepad.org/K0V8GfTs    [ raw code | fork ]

C++, pasted on Oct 22:
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

// will loop endlessly if a/b == c/d
inline bool greaterOrEqualPositiveFraction(int a,int b,int c,int d);
inline bool greaterPositiveFraction(int a,int b,int c,int d);
inline bool greaterFraction(int a,int b,int c,int d);

inline bool greaterOrEqualPositiveFraction(int a,int b,int c,int d)
{
	if(b == 0)
	{
		return true;
	}
	if(d == 0)
	{
		return false;
	}
	if(a*d > b*c)
	{
		return true;
	}
	if(a*d < b*c)
	{
		return false;
	}
	return !greaterFraction(b,a%b,d,c%d);
}
inline bool greaterPositiveFraction(int a,int b,int c,int d)
{
	if(d == 0)
	{
		return false;
	}
	if(b == 0)
	{
		return true;
	}
	if(a*d > b*c)
	{
		return true;
	}
	if(a*d < b*c)
	{
		return false;
	}
	return !greaterOrEqualPositiveFraction(b,a%b,d,c%d);
}
inline bool greaterFraction(int a,int b,int c,int d)
{
	if(b<0)
	{
		b = -b;
		a = -a;
	}
	if(d<0)
	{
		d = -d;
		c = -c;
	}
	if(a<0 && c<0)
	{
		return greaterPositiveFraction(-c,d,-a,b);
	}
	if(a<0)
	{
		return false;
	}
	if(c<0)
	{
		return true;
	}
	return greaterPositiveFraction(a,b,c,d);
}

char seq[1000005];

int main()
{	
	int T;
	scanf("%d", &T);
	for(int t=0; t<T; t++)
	{
		memset(seq, '\0', 1000005);
		scanf("%s", seq);
		int sz = strlen(seq);

		int pus[sz], pyr[sz], cnt_pus=0, cnt_pyr=0;
		for(int i=0; i<sz; i++)
		{
			if(seq[i]=='A' || seq[i]=='G')
			{
				cnt_pus++;
			}
			else
			{
				cnt_pyr++;
			}
			pus[i] = cnt_pus;
			pyr[i] = cnt_pyr;
		}

		int max_pus=pus[0], max_pyr=pyr[0];
		for(int i=0; i<sz; i++)
		{
			for(int j=i; j<sz; j++)
			{
				int num_pus = pus[j] - (i-1<0?0:pus[i-1]);
				int num_pyr = pyr[j] - (i-1<0?0:pyr[i-1]);
//				printf("[%d-%d]: %d/%d > %d/%d\n", i,j,num_pus,num_pyr,max_pus,max_pyr);
				if(num_pyr==0 && max_pyr==0)
				{
					max_pus = max(max_pus,num_pus);
				}
				else if(num_pyr==0)
				{
					// max sure wins
				}
				else if(max_pyr==0)
				{
					// num sure wins
					max_pus = num_pus;
					max_pyr = num_pyr;
				}
				else
				{
					// num_pyr!=0, max_pyr!=0
					if(max_pus*num_pyr == num_pus*max_pyr)
					{
						// take longer sequence
						if(num_pus+num_pyr > max_pus+max_pyr)
						{
							max_pus = num_pus;
							max_pyr = num_pyr;
						}
					}
					else if(greaterFraction(num_pus,num_pyr,max_pus,max_pyr))
					{
						max_pus = num_pus;
						max_pyr = num_pyr;
					}
				}
			}
		}
		printf("%d %d\n", max_pus,max_pyr);
	}
	return 0;
}


Create a new paste based on this one


Comments: