TopCoder practice room(2002 Invitation Semi)

A. First Edition
These are problems from topCoder practice room and for the "1000" problem usually I need 2-6 hours because sometimes I feel
so tired and simply wait for tomorrow.:) I am a slow coder after all.
B.The problem

See below.

 
C.The idea of program
 
D.The major functions
 
E.Further improvement
 
F.File listing
 
1. chooser (problem 250)
/*

Version:0.9 StartHTML:-1 EndHTML:-1 StartFragment:0000000111 EndFragment:0000004346 

Problem Statement

    
PROBLEM STATEMENT
When putting together a problem set, a writer must keep in mind the difficulty
and length of a problem.  A good problem set is one with an easy, a middle, and
a hard problem, but doesn't take too much or too little time to complete.

You will be given an input of three int[].  The first int[] consists of easy
problem times, the second consists of middle problem times, and the third
consists of hard problem times.  Return the number of legal problem set
combinations, where a legal set contains exactly 1 easy, 1 middle and 1 hard
problem, and the total time is between 60 and 75 inclusive.

DEFINITION
Class name: Chooser
Method name: numSets
Parameters: int[], int[], int[]
Returns: int
The method signature is:
int numSets(int[] easy, int[] middle, int[] hard)
Be sure your method is public.

TopCoder will ensure the following:
*Each int[] will contain between 0 and 10 elements, inclusive.
*Each element of easy will be an int between 5 and 15, inclusive.
*Each element of middle will be an int between 15 and 45, inclusive.
*Each element of hard will be an int between 30 and 55, inclusive.

EXAMPLES
{5,10,15}
{15,25}
{45}
There are 3*2*1=6 possible sets.  However, since 10+25+45=80 and 15+25+45=85,
two of the sets are illegal, so the method returns 4.

{5,5,5}
{15,15,15}
{45,45,45}
There are 3*3*3=27 possible sets, all legal.  The return value is 27.

{5,5,5}
{15,15,15}
{45,45,35}
There are 27 possible sets again, but for this input any set with the 35 minute
hard problem is too short.  Therefore there are only 3*3*2=18 legal sets, and
the return value is 18.

{}
{15,25}
{30,35,40}
Since there are no easy problems, there are no legal problem sets.  The return
value is 0.

Definition

    
Class: Chooser
Method: numSets
Parameters: vector <int>, vector <int>, vector <int>
Returns: int
Method signature: int numSets(vector <int> param0, vector <int> param1, vector <int> param2)
(be sure your method is public)
    
 

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

*/


	
#include <vector>
#include <stdio.h>


using namespace std;

typedef vector<int> IntVector;

class Chooser
{
public:
	int numSets(IntVector easy, IntVector middle, IntVector hard);
};

int Chooser::numSets(IntVector easy, IntVector middle, IntVector hard)
{
	int sum;
	int counter=0;
	for (int i=0; i<easy.size(); i++)
	{
		for (int j=0; j<middle.size(); j++)
		{
			for (int k=0; k<hard.size(); k++)
			{
				sum=easy[i]+middle[j]+hard[k];
				if (sum<=75&&sum>=60)
				{
					counter++;
				}
			}
		}
	}
	return counter;
}


2. CheckData (problem 500)
/*
Problem Statement
    
PROBLEM STATEMENT
For every problem given on TopCoder, there are restrictions on the input that
TopCoder checks.  For the most simple inputs, this could be as easy as ensuring
that a single int is between 1 and 50, inclusive.  On more complicated
problems, this CheckData() method (as it is called) becomes more difficult.

Implement a class Checker with a method CheckData() that will take a String[]
as an argument.  You must ensure that the String[] is a valid input for the
following "problem description":

****** BEGIN PSUEDO-PROBLEM DESCRIPTION ******
You are given a String[] lovers representing a love triangle.  Each element in
this String[] will be formatted as follows:
"NAME1 LOVES NAME2"
(quotes added for clarity only).

Checker will ensure the following:
*lovers will contain between 2 and 20 elements, inclusive.
*Each element of lovers will contain less than or equal to 40 characters and
will be formatted as
 "NAME1 LOVES NAME2" (quotes added for clarity again)
with the capital word LOVES and only one space between words, and no leading
or trailing spaces.
*NAME1 and NAME2 will be names of non-zero length.
*NAME1 and NAME2 will not be identical (everyone loves themselves anyway).
*NAME1 and NAME2 will contain only capital letters [A-Z] and/or hyphens '-'.
*For each NAME2 there will be a corresponding NAME1 in lovers.  That is,
everyone loves someone else in the problem.

Notes:
*One person may love multiple people (repeated NAME1 in different elements) and
one person may be loved by multiple people (repeated NAME2 in different
elements).
*It is possible for two elements to be identical.
 (ex {"A LOVES B","A LOVES B","B LOVES A"} is valid).
****** END PSUEDO-PROBLEM STATEMENT ******

DEFINITION
Class name: Checker
Method name: CheckData
Parameters: String[]
Returns: boolean
The method signature is:
boolean CheckData(String[] lovers)
Be sure your method is public.

For technical reasons, TopCoder will ensure the following:
*lovers contains 0 to 50 elements.
*each element of lovers contains 0 to 50 characters, inclusive.
*each element of lovers contains characters ([a-z][A-Z][0-9]), spaces, or any
of the characters (quotes added for clarity) "<>./?;:{}[]=+-_|".

EXAMPLES
{"D-G LOVES M",
 "M LOVES D-G",
 "T LOVES G",
 "G LOVES D-G"}
This input matches the above criteria, so CheckData returns true.

{"D LOVES M",
 "D LOVES C",
 "G LOVES M",
 "M LOVES T",
 "T LOVES D"}
Since C is loved but never appears as NAME1, this returns false.

{"D LOVES M",
 "C LOVES C",
 "G LOVES M",
 "M LOVES T",
 "T LOVES D"}
Now we see that C desperately tries loving himself, but that is not allowed so
the method returns false.

{"N LOVES C",
 "C LOVES D",
 "D LOVES M",
 "M LOVES g",
 "g LOVES N"}
g has lowercase letters in his name and therefore the method returns false.

{"A LOVES B",
 "A LOVES C",
 "C LOVES A",
 "B  LOVES A"}
Element 3 has a badly formatted string (two spaces where only one is allowed),
so the result is false.

{"ME LOVES YOU"}
Since 2-20 elements (inclusive) are necessary, this returns false.

{"ME LOVES YOU",
 "ME LOVES YOU"}
This has the correct number of elements, and the repeat is legal.  However,
since YOU never exists as NAME1, the result is still false.

{"ME LOVES YOU",
 "ME LOVES YOU",
 "YOU LOVES ME"}
The above situation remedied.  This returns true.

{"I LOVE YOU",
 "YOU LOVE I"}
Both Strings are incorrectly formatted (LOVE instead of LOVES), so the method
returns false.
Definition
    
Class:
Checker
Method:
CheckData
Parameters:
vector <string>
Returns:
bool
Method signature:
bool CheckData(vector <string> param0)
(be sure your method is public)
    

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.
*/

#include <string>
#include <set>
#include <vector>
#include <stdio.h>

using namespace std;

struct StringComp
{
	bool operator()(const string& first, const string& second) const
	{
		return first.compare(second)<0;
	}
};

typedef vector<string> StringVector;
typedef set<string, StringComp> StringSet;

class Checker
{
private:
	StringSet left;
	StringSet right;
	bool checkString(string& input);
	bool checkElement();
public:
	bool CheckData(StringVector param);
};

bool Checker::CheckData(StringVector param)
{
	if (param.size()<2||param.size()>20)
	{
		return false;
	}
	for (int i=0; i<param.size(); i++)
	{
		if (!checkString(param[i]))
		{
			return false;
		}
	}
	return checkElement();
}

bool Checker::checkElement()
{
	StringSet::iterator it;
	
	for (it=right.begin(); it!=right.end(); it++)
	{
		if (left.find(*it)==left.end())
		{
			return false;
		}
	}
	return true;
}
	

bool Checker::checkString(string& input)
{
	int i;
	char ch;
	string leftStr, rightStr;
	int first=-1, second=-1;
	if (input.size()>40)
	{
		return false;
	}
	for (i=0; i<input.size(); i++)
	{
		ch=input.at(i);
		if (!(ch>='A'&&ch<='Z'||ch==' '||ch=='-'))
		{
			return false;
		}
		
		if (ch==' ')
		{
			if (first==-1)
			{
				first=i;
			}
			else
			{
				if (second==-1)
				{
					second=i;
				}
				else
				{
					return false;
				}
			}
		}
	}
	
	if (first==-1||second==-1||second-first!=6)
	{
		return false;
	}
	if (input.compare(first+1, 5, "LOVES")!=0)
	{
		return false;
	}
	
	leftStr.assign(input, 0, first);
	rightStr.assign(input, second+1, input.size()-second-1);
	if (leftStr.compare(rightStr)==0)
	{
		return false;
	}
	if (leftStr.size()==0||rightStr.size()==0)
	{
		return false;
	}
	left.insert(leftStr);
	right.insert(rightStr);
	return true;
}

	
3. Solver (problem 1000)
/*
Version:0.9 StartHTML:-1 EndHTML:-1 StartFragment:0000000111 EndFragment:0000006102 

Problem Statement

    
PROBLEM STATEMENT
After writing a careful and correct data checking method, a problem writer then
has to code a solution.  This is what you should now do.

Implement a class Solver with a method largest() that will take a String[]
lovers as an argument.  Each element of lovers will be formatted as follows:
"NAME1 LOVES NAME2" (quotes added for clarity).
With the capital word LOVES in between names, and the names containing only
capital letters [A-Z] and/or hyphens '-'.

For each NAME2 in lovers there will be a corresponding NAME1.  One person may
love multiple people (repeated NAME1), multiple people may love one person
(repeated NAME2), but no person may love themselves (NAME1 equals NAME2).

Return the number of people involved in the largest love triangle.  That is,
the largest chain of people such that:
A LOVES B
B LOVES C
C LOVES D
D LOVES E
E LOVES A
until the last person loved (NAME2--in this example A) appears somewhere else
in the chain as NAME1, at which point the triangle starts and ends with that
name.
The triangle above consists of 5 people (A B C D and E).

A love triangle can consist of 2 or more people.

DEFINITION
Class name: Solver
Method name: largest
Parameters: String[]
Returns: int
The method signature is:
int largest(String[] lovers)
Be sure your method is public.

TopCoder will ensure the following (there is no difference between these and
the 500 point problem psuedo-restrictions):
*lovers will contain between 2 and 20 elements, inclusive.
*Each element of lovers will contain less than or equal to 40 characters and
will be formatted as
 "NAME1 LOVES NAME2" (quotes added for clarity again)
 with the capital word LOVES and only one space between words.
*NAME1 and NAME2 will be names of non-zero length.
*NAME1 and NAME2 will not be identical (everyone loves themselves anyway).
*NAME1 and NAME2 will contain only capital letters [A-Z] and/or hyphens '-'.
*For each NAME2 there will be a corresponding NAME1 in lovers.  That is,
everyone loves someone else in the problem.
*One person may love multiple people (repeated NAME1 in different elements) and
one person may be loved by multiple people (repeated NAME2 in different
elements).

*It is possible for two elements to be identical.
 (ex {"A LOVES B","A LOVES B","B LOVES A"} is valid).

EXAMPLES
{"D LOVES M",
 "M LOVES D",
 "T LOVES G",
 "G LOVES D"}
The largest love triangle (between D and M) is 2.

{"ME LOVES YOU",
 "ME LOVES YOU",
 "YOU LOVES ME"}
The largest triangle is between YOU and ME, so the method returns 2.

{"A LOVES B",
 "B LOVES C",
 "C LOVES A",
 "B LOVES D",
 "D LOVES E",
 "E LOVES C",
 "E LOVES F",
 "F LOVES G",
 "G LOVES F"}
This looks as follows:

/---<---\
|       |
A->-B->-C
    |   ^
    v   |
    D->-E
        |
        v
    G<->F

A->B->D->E->C->A is the largest triangle, which is of size 5.

{"A LOVES B",
 "B LOVES C",
 "C LOVES B",
 "B LOVES A"}

Either A->B->A or B->C->B are legal, and both of size 2.  We see that
A->B->C->B->A is not legal since, by the above definition of triangle, once
person B appears as both NAME2 and NAME1 in the triangle, the triangle can go
no further and must start and end with person B (giving B->C->B).  The method
should return 2.

Definition

    
Class: Solver
Method: largest
Parameters: vector <string>
Returns: int
Method signature: int largest(vector <string> param0)
(be sure your method is public)
    
 

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

*/

#include <string>
#include <map>
#include <vector>
#include <stdio.h>

using namespace std;


struct StringComp
{
	bool operator()(const string& first, const string& second) const
	{
		return first.compare(second)<0;
	}
};


typedef vector<string> StringVector;
typedef multimap<string, string, StringComp> StringMap;


class Solver
{
private:
	StringMap myMap;
	void checkString(string& input);
	int checkCircle(string);
	int doCheckCircle(string name, StringVector path);
public:
	int largest(StringVector param);
};


int Solver::largest(StringVector param)
{
	int i;
	int result=0, length;
	StringVector path;
	StringMap::iterator it;
	string prev;
	for (i=0; i<param.size(); i++)
	{
		checkString(param[i]);
	}
	for (it=myMap.begin(); it!=myMap.end(); it++)
	{
		if (it->first.compare(prev)!=0)
		{
			prev.assign(it->first);
			path.clear();
			length=doCheckCircle(it->first, path);
			if (length>result)
			{
				result=length;
			}
		}
	}
	return result;
}
	
int Solver::doCheckCircle(string name, StringVector path)
{
	int i;
	int result=0, length;
	StringMap::iterator it;
	for (i=0; i<path.size(); i++)
	{
		if (path[i].compare(name)==0)
		{
			return path.size()-i;
		}
	}
	path.push_back(name);
	for (it=myMap.find(name); it!=myMap.end(); it++)
	{
		if (it->first.compare(name)==0)
		{
			//path is passed by value
			length=doCheckCircle(it->second, path);
			if (length>result)
			{
				result=length;
			}
		}
		else
		{
			break;
		}
	}
	return result;
}

void Solver::checkString(string& input)
{
	int i;
	char ch;
	string leftStr, rightStr;
	for (i=0; i<input.size(); i++)
	{
		ch=input.at(i);	
		
		if (ch==' ')
		{		
			break;
		}
	}	
	
	leftStr.assign(input, 0, i);
	rightStr.assign(input, i+7, input.size());
	myMap.insert(make_pair(leftStr, rightStr));	
}
/////////////////////////////////////
//inivitaion semi C-D
////////////////////////////////
4. LetterRange (problem 250)
/*

Problem Statement
    
PROBLEM STATEMENT

A letter range is a set of alphabetically consecutive letters taken from the
lowercase alphabetic characters 'a' through 'z'. The lowest and highest letters
of the range, separated by a colon (the character ':'), are used to represent a
letter range. For example, the range "a:c" represents the consecutive letters
'a', 'b', and 'c'. (quotes are not part of the range). The range "w:z"
represents the letters 'w', 'x', 'y', and 'z'. The range "m:m" respresents the
single letter 'm'.  

Given an input String, return the letter ranges ordered alphabetically by the
low value of each range. Letter ranges contained in the result must represent
the largest possible sequences of increasing consecutive letters found in the
input text. The letters of the input do not have to appear in alphabetical
order. Ignore space characters and duplicate letters contained in the input.
For example, the text "fb xee ac" has three letter ranges, "a:c" (the letters
a, b, and c), "e:f" (the letters e and f) and "x:x" (the letter x). Please
refer to the examples.

DEFINITION
Class: LetterRange
Parameters: String
Returns: String[]
Method signature: String[] ranges(String text);

(be sure your method is public)

TopCoder will ensure the validity of the inputs.  Inputs are valid if all of
the following criteria are met:

* text may only contain lowercase letters (a-z) and the space character, ' '.
* text will contain between 0 and 50 characters, inclusive.

NOTES
- When determining a letter range, please keep in mind that the alphabet ends
with 'z' and does not wrap (i.e. 'a' does not come after 'z'). Since the range
must be increasing you cannot have a range that begins with a letter located
near or at end of the alphabet and ends with a letter at or near the beginning
of the alphabet.

EXAMPLES
(Note that the quote characters are for clarity only.)
E1: "" ==> {}      
E2: "  " ==> {}    
E3: "aha" ==> {"a:a","h:h"}
E4: "xyzzy" ==> {"x:z"}
E5: "and toto too" ==> {"a:a","d:d","n:o","t:t"}
E6: "topcoder quiz" ==> {"c:e","i:i","o:r","t:u","z:z"}
E7: "the quick brown fox jumps over the lazy dog" ==> {"a:z"}


Definition
    
Class:
LetterRange
Method:
ranges
Parameters:
string
Returns:
vector <string>
Method signature:
vector <string> ranges(string param0)
(be sure your method is public)
    

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.
*/

#include <vector>
#include <string>
#include <set>

using namespace std;



typedef vector<string> StringVector;

class LetterRange
{
private:
	bool range[26];	
	void addRange(char ch);
public:
	StringVector ranges(string param);
};

StringVector LetterRange::ranges(string param)
{
	int i;
	StringVector result;
	char ch, start, end;
	string str;
	for (i=0; i<26; i++)
	{
		range[i]=false;
	}
	for (i=0; i<param.size(); i++)
	{
		ch=param[i];
		if (ch!=' ')
		{
			range[ch-'a']=true;
		}
	}
	i=0;
	start=-1;
	end=-1;
	for (i=0; i<26; i++)
	{
		if (range[i])
		{
			if (start==-1)
			{
				start='a'+i;
			}
		}
		else
		{
			if (start!=-1)
			{
				end='a'+i-1;
				str.assign(1, start);
				str.append(1, ':');
				str.append(1, end);
				result.push_back(str);
				start=-1;
				end=-1;
			}
		}
	}
	if (start!=-1)
	{
		end='z';
		str.assign(1, start);
		str.append(1, ':');
		str.append(1, end);
		result.push_back(str);
	}
	
	return result;
}
		
5. Intervals (problem 500)
/*
Problem Statement
    
PROBLEM STATEMENT

An interval is a set of consecutive integers. The lowest and highest integers,
separated by a single colon, (the character ':'), are used to represent the
interval. The low number appears first, before the ':'. The high number appears
second, after the ':'. For example, the interval "1:3" represents the set of
integers 1, 2, and 3. (double quotes are for clarity). The interval "100:199"
represents the set of integers greater than or equal to 100 and less than or
equal to 199. The interval "5:5" respresents the set containing the single
integer 5. Note that the high value of the interval must always be greater than
or equal to the low value of the interval. 

Write a method that takes a list of intervals and partitions the intervals so
that every interval in the result:

* is pairwise disjoint (no two intervals contain the same integer), 
* every integer appearing in the original input is represented exactly once in
exactly one of the resulting intervals, 
* no integer appears in a result interval that does not also appear in at least
one input interval, 
* the minimum number of resulting intervals is used, 
* each interval in the orignal input can be recreated by combining one or more
intervals from the result. 

Return the intervals ordered by the low value of each range. Note that the
input may contain duplicate intervals, but the result will not. 

DEFINITION
Class: Intervals
Parameters: String[]
Returns: String[]
Method signature: String[] partition(String[] intervals);

(be sure your method is public)

TopCoder will ensure the validity of the inputs.  Inputs are valid if all of
the following criteria are met:

* The input will contain from 0 to 20 elements, inclusive.
* Each element of intervals will contain two integers (no leading zeros)
separated by a single colon (character ':').
* Each element of intervals will have neither leading nor trailing spaces.
* Each integer in an interval will be from 0 to 9999, inclusive.
* The high value of each interval will be greater than or equal to the low
value of that interval.

EXAMPLES

E1: {1:5,3:8} ==> {1:2,3:5,6:8} 

The input has two intervals. The first interval contains the integers 1, 2, 3,
4 and 5. The second interval contains the integers 3, 4, 5, 6, 7, and 8. Since
two input intervals contain the integers 3, 4, and 5, the intervals are not
pairwise disjoint. By creating the new interval, "3:5", and removing the
elements 3, 4, and 5 from the two original intervals, the original intervals
are now correctly partitioned into the three intervals "1:2", "3:5", and "6:8".
Note that other partitionings are possible, such as {1:2,3:4,5:5,6:8} which
uses four intervals, but the minimum number of partitions must be used. A
partitioning such as {1:2,3:6,7:8} is incorrect because the interval "1:5" from
the original input cannot be formed by combining one or more of the result
intervals. Thus, the only correct solution is the list of intervals
{1:2,3:5,6:8}. 
  
E2: {} ==> {} 
E3: {0:9999} ==> {0:9999} 
E4: {10:21,10:21} ==> {10:21}
E5: {6:10,3:10} ==> {3:5,6:10} 
E6: {1:10,3:5} ==> {1:2,3:5,6:10}
E7: {6:7,1:8,2:4,5:7,2:3} ==> {1:1,2:3,4:4,5:5,6:7,8:8}
E8: {1:99,6:10,3:10} ==> {1:2,3:5,6:10,11:99}



Definition
    
Class:
Intervals
Method:
partition
Parameters:
vector <string>
Returns:
vector <string>
Method signature:
vector <string> partition(vector <string> param0)
(be sure your method is public)
    

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.
*/

#include <stdio.h>
#include <string>
#include <vector>
#include <set>

using namespace std;

typedef pair<int, int> IntPair;

struct IntPairComp
{
	bool operator()(const IntPair& first, const IntPair& second) const
	{
		return first.second<second.first;
	}
};

typedef vector<string> StringVector;
typedef set<IntPair, IntPairComp> IntPairSet;

class Intervals
{
private:
	IntPairSet mySet;
	void addInterval(string& str);
	void doAddInterval(IntPair& intPair);
public:
	StringVector partition(StringVector param);
};


StringVector Intervals::partition(StringVector param)
{
	char buf[16];
	IntPairSet::iterator it;
	StringVector result;
		
	for (int i=0; i<param.size(); i++)
	{
		addInterval(param[i]);
	}
	for (it=mySet.begin(); it!=mySet.end(); it++)
	{
		sprintf(buf, "%d:%d", it->first, it->second);
		
		result.push_back(string(buf));
	}
	return result;
}
		
	

void Intervals::doAddInterval(IntPair& intPair)
{
	IntPairSet::iterator it;
	IntPair left,middle, right;
	
	pair<IntPairSet::iterator, bool> result;

	result=	mySet.insert(intPair);
	if (result.second)
	{
		return;
	}
	else
	{
		it=result.first;		
	}
	if (intPair.first==it->first&&intPair.second==it->second)
	{
		return;
	}
	left.first=min (intPair.first, it->first);
	right.second=max (intPair.second, it->second);
	middle.first=max (intPair.first, it->first);
	middle.second=min (intPair.second, it->second);
	
	left.second=max(left.first, middle.first-1);
	right.first=min(right.second, middle.second+1);

	mySet.erase(it);
	if (left.second<middle.first)
	{
		doAddInterval(left);
	}
	if (right.first>middle.second)
	{
		doAddInterval(right);
	}
	doAddInterval(middle);
}	


void Intervals::addInterval(string& str)
{
	bool isFirst=true;
	IntPair intPair;
	intPair.first=intPair.second=0;
	for (int i=0; i<str.size(); i++)
	{
		if (isFirst)
		{
			if (str[i]!=':')
			{
				intPair.first*=10;
				intPair.first+= str[i]-'0';
			}
			else
			{
				isFirst=false;
			}
		}
		else
		{
			intPair.second*=10;
			intPair.second+=str[i]-'0';
		}
	}
	doAddInterval(intPair);
}

	
6. AlephNull (problem 1000)
/*

Problem Statement
    
PROBLEM STATEMENT

The logician Charles Sanders Pierce proposed a procedure for generating and
ordering all of the positive rational numbers. A rational number is an integer
divided by an integer (n/m where both n and m are integers and m does not equal
zero). 

The procedure proceeds as follows. Start with the two rationals 0/1 and 1/0
(disregarding the fact that 1/0 is not a valid number). Call this generation 1.
To produce the next generation, insert a new rational in between each pair of
rationals in the current generation by summing the numerators (the number being
divided) of the adjacent rationals to produce the new numerator, and by summing
the denominators (the number doing the dividing) of the adjacent rationals to
produce the new denominator. By repeating this procedure indefinitely, all of
the positive rational numbers will be produced in order in their simplest
rational form. 

The first few generations proceed as follows:

G1: 0/1 1/0
G2: 0/1 1/1 1/0
G3: 0/1 1/2 1/1 2/1 1/0
G4: 0/1 1/3 1/2 2/3 1/1 3/2 2/1 3/1 1/0
G5: 0/1 1/4 1/3 2/5 1/2 3/5 2/3 3/4 1/1 4/3 3/2 5/3 2/1 5/2 3/1 4/1 1/0 

Code a method that given a generation number and a zero based index, returns
the numerator and denominator of the rational number at the position indicated
by the index within the generation. If the index is not within the range of
values for the given generation, return the special error value having zero for
both the numerator and denominator.

DEFINITION
Class: AlephNull
Parameters: int, int
Returns: int[]
Method signature: int[] rational(int generation, int item)

(be sure your method is public)

TopCoder will ensure the validity of the inputs.  Inputs are valid if all of
the following criteria are met:

* generation is from 1 to 30 inclusive.
* item is from 0 to 999999999 inclusive. 

HINT
The number of elements in a given generation can be computed as follows:
elements = (2 ^ (generation - 1)) + 1. (The '^' symbol indicates
exponentiation. For example:
Generation 1: 2^0 + 1 = 2 
Generation 2: 2^1 + 1 = 3 
Generation 3: 2^2 + 1 = 5 
Generation 4: 2^3 + 1 = 9
Generation 9: 2^8 + 1 = 257

EXAMPLES
E1:  1,0        ==> [0,1]
E2:  1,1        ==> [1,0]
E3:  1,2        ==> [0,0]      //error value
E4:  4,1        ==> [1,3]
E5:  4,6        ==> [2,1]
E6:  5,11       ==> [5,3]
E7:  8,70       ==> [9,7]
E8:  10,467     ==> [43,12]
E9:  23,4190316 ==> [438,43]
E10: 30,100     ==> [7,157]
Definition
    
Class:
AlephNull
Method:
rational
Parameters:
int, int
Returns:
vector <int>
Method signature:
vector <int> rational(int param0, int param1)
(be sure your method is public)
    

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.
*/


#include <vector>
#include <string>
#include <math.h>

using namespace std;

typedef pair<int, int> IntPair;
typedef vector<IntPair> IntPairVector;
typedef vector<int> IntVector;

class AlephNull
{
	IntPairVector genVector[2];
	int current;
	void init();
	void doGenerate();
public:
	IntVector rational(int gen, int index);
};


void AlephNull::init()
{
	current=0;
	genVector[current].push_back(make_pair(0, 1));
	genVector[current].push_back(make_pair(1, 0));
}

void AlephNull::doGenerate()
{
	int prev=current;
	IntPair intPair;
	current=(current+1)%2;
	genVector[current].clear();
	for (int i=0; i<genVector[prev].size(); i++)
	{
		genVector[current].push_back(genVector[prev][i]);
		if (i!=genVector[prev].size()-1)
		{
			intPair.first=genVector[prev][i].first+genVector[prev][i+1].first;
			intPair.second=genVector[prev][i].second+genVector[prev][i+1].second;
			genVector[current].push_back(intPair);
		}
	}
}

IntVector AlephNull::rational(int gen, int index)
{
	IntVector result;
	if (index>pow(2, (gen-1)))
	{
		result.push_back(0);
		result.push_back(0);
		return result;
	}
		
	init();
	for (int i=1; i<gen; i++)
	{
		doGenerate();
	}
	result.push_back(genVector[current][index].first);
	result.push_back(genVector[current][index].second);
	return result;
}
7. DiceChecker(problem 250)
    
PROBLEM STATEMENT

The results of rolling a die a number of times is given.  If one particular
value comes up more than 1/4 of the time, or comes up less than 1/10 of the
time, the die is considered to be loaded (Loaded means weighted in such a way
as to make the die show a particular number more or less often than is
statistically acceptable).  

Given a sample of die rolls, decide whether or not the die is loaded, and if
so, return the numbers that came up too many or too few times.

DEFINITION

Class Name: DiceChecker
Method Name: badValues
Parameters: int[]
Returns: int[]

Method signature: int[] badValues(int[] values)
Be sure your method is public.

TopCoder will ensure the validity of the inputs.  Inputs are valid if all of
the following criteria are met:
 *values has between 1 and 50 elements, inclusive.
 *each element of values is between 1 and 6, inclusive.

Return an int[] that contains the numbers between 1 and 6 (inclusive) that were
in the int[] too few or too many times.

NOTES
 - If the die is not loaded, return an empty int[].
 - Sort the output ascending ( { 1, 2 }, not { 2, 1 } ).

Examples:

values: { 1, 2, 3, 4, 5, 6, 1, 2, 3, 4 }
1 comes up 1/5 of the time.
2 comes up 1/5 of the time.
3 comes up 1/5 of the time.
4 comes up 1/5 of the time.
5 comes up 1/10 of the time.
6 comes up 1/10 of the time.
No value comes up more than 1/4 of the time or less than 1/10 of the time.
The die is not loaded so return {} (empty int[]).

values: { 3, 1, 5 }
1 comes up 1/3 of the time.
2 does not comes up.
3 comes up 1/3 of the time.
4 does not comes up.
5 comes up 1/3 of the time.
6 does not comes up.
2, 4, and 6 come up less than 1/10 of the time, and 1, 2, and 3 come up more
than 1/4 of the time so return { 1, 2, 3, 4, 5, 6 }.

values : { 1, 1, 1, 1, 1, 1, 1, 2, 2, 2 }
1 comes up 7/10 of the time.
2 comes up 3/10 of the time.
3 does not comes up.
4 does not comes up.
5 does not comes up.
6 does not comes up.
All values are out of the range specified for an unloaded die (> 1/4 or < 1/10).
return { 1, 2, 3, 4, 5, 6 }.

values : { 1, 1, 3, 3, 4, 4, 2, 2, 5, 5, 6, 6 }
1 comes up 1/6 of the time.
2 comes up 1/6 of the time.
3 comes up 1/6 of the time.
4 comes up 1/6 of the time.
5 comes up 1/6 of the time.
6 comes up 1/6 of the time.

All values are in the range specified for an unloaded die (> 1/4 or < 1/10)
return {}.
Definition
    
Class:
DiceChecker
Method:
badValues
Parameters:
vector <int>
Returns:
vector <int>
Method signature:
vector <int> badValues(vector <int> param0)
(be sure your method is public)
    

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

	
#include <vector>
#include <stdio.h>

using namespace std;

typedef vector<int> IntVector;

class DiceChecker
{
	int array[6];
public:
	IntVector badValues(IntVector param);
};

IntVector DiceChecker::badValues(IntVector param)
{
	int i;
	IntVector result;
	for (i=0; i<6; i++)
	{
		array[i]=0;
	}
	for (i=0; i<param.size(); i++)
	{
		array[param[i]-1]++;
	}
	
	for (i=0; i<6; i++)
	{
		if (array[i]*10<param.size()||array[i]*4>param.size())
		{
			result.push_back(i+1);
		}
	}
	return result;
}
8.  Birds(problem 500)
Problem Statement
    
PROBLEM STATEMENT:

A Bird is considered migratory if it can be found in two regions in different
parts of the year.  Of course, it must stay in those regions for a minimum
amount of time (one day in Barbados does not make a migration).  The bird can
travel inside those regions and that travel is unimportant (The bird can leave
Alaska for Florida and spend some time in both southern and northern Florida
but those COULD just be considered part of spending time in Florida).  The bird
can also travel when not in those regions and that travel can be ignored (The
bird can spend the summer in Alaska and the winter in Brazil, and if the bird
is in England in the spring, who cares?).  In this problem we will specify that
the time a bird must spend in a region is at least 90 days.  The distance
between these regions must be at least 1000 miles for the bird to be considered
migratory.

To put it precisely, the bird is migratory if there exist 2 blocks of time in
the same calendar year that are each at least 90 contiguous days in length in
which all areas the bird is at in time period 1 are at least 1000 miles away
from all areas the bird is at in time period 2.

Write a class Birds which contains a method isMigratory.  isMigratory should
determine whether the given set of bird moves describe a migratory bird.  If
so, return 1, otherwise return 0.

Example:

If the bird is in New York in January, and in Connecticut from February through
April, and then spends the rest of the year in Brazil, (which is at least 1000
miles from both New York and Connecticut) that Bird would be considered
migratory because it is spending 31 + 28 + 31 + 30 = 120 consecutive days in
the region containing New York and Connecticut and 365 - 120 = 245 consecutive
days in Brazil.

DEFINITION:

Class Name: Birds
Method Name: isMigratory
Parameters: String[]
Returns: int

Method Signature: int isMigratory(String[] birdMoves)
(be sure your method is public)

TopCoder will enforce the following rules:
 *birdMoves has between 1 and 15 elements, inclusive.
 *each element of birdMoves will contain between 1 and 50 characters, inclusive.
*each String in birdMoves is of the form
"<gridCoordinateX>,<gridCoordinateY>,<month>,<day>" where <gridCoordinateX>,
<gridCoordinateY>, <month>, and <day> all represent integer values.  (The
quotes and angle-brackets are for clarity only).
*<gridCoordinateX> and <gridCoordinateY> will each be between 0 and 30000,
inclusive.  The pair <gridCoordinateX>, <gridCoordinateY> represents a location
where the bird begins to reside at the point in time represented by the pair
<month>, <day>.
 *<month> will be between 1 and 12, inclusive.
*<day> will be appropriate to the month on a non leap year.  That is, if
<month> is 2, then <day> will be restricted to being between 1 and 28, inclusive.
 *grid coordinates represent one mile for each unit.
*the distance between a grid cordinate (x1, y1) and (x2, y2) is given by the
square root of the value ((x2 - x1)^2 + (y2 - y1)^2).
 *two different elements of birdMoves cannot contain the same date.

NOTES:
 *Sort birdMoves by date.
*Assume that the bird begins to exist on the earliest day given in the
birdMoves.
 *The bird begins that day at the associated grid coordinate.
*Then, the bird moves instantly, at midnight on the date represented by the
next element of birdMoves to the position represented by the next element of
birdMoves.
*The bird will exist at the location given by the last element of birdMoves
until and including the entire day of December 31.
*January(1), March(3), May(5), July(7), August(8), October(10), December(12)
each have 31 days.
 *April(4), June(6), September(9), November(11) each have 30 days.
 *February(2) has 28 days.

WORKED EXAMPLES:

birdMoves = { "0,0,1,1", "1000,1000,6,1" }
The bird is at grid coordinate (0,0) from January 1 through May 31.  Then, the
bird is at grid coordinate (1000,1000) through December 31.  The distance
between (0,0) and (1000,1000) is sqrt( (1000 - 0) ^ 2  +  (1000 - 0) ^ 2 ) =
sqrt(2000000) >= 1000.  The number of days spent at (0,0) is 31 + 28 + 31 + 30
+ 31 = 151 >= 90, and the number of days spent at (1000,1000) is 365 - 151 =
214 >= 90.  Return 1.

birdMoves = { "0,0,1,1", "100,100,6,1" }
The bird is at grid coordinate (0,0) from January 1 through May 31.  Then, the
bird is at grid coordinate (100,100) through December 31.  The distance between
(0,0) and (100,100) is sqrt( (100 - 0) ^ 2  +  (100 - 0) ^ 2 ) = sqrt(20000) <
1000.  Return 0.

birdMoves = { "1000,0,2,1", "1000,1000,1,1", "10000,30000,7,1" }
The bird is at (1000,1000) for 31 days, then at (1000,0) for 150 days, then at
(10000,30000) for 184 days.
The distance from (1000,0) to (10000,30000) is 31320.919...
Thus, the bird spends 150 consecutive days (at 1000,0) at least 1000 miles away
from where the bird spends 184 consecutive days (at 10000,30000).  Return 1.

{ "30000,30000,9,1", "0,0,1,1", "1000,1000,5,1" } returns 1.
In this case, the bird is migratory based on any of three distance checks.  The
bird spends 4 months at (0,0), 4 months at (1000,1000), and 4 months at
(30000,30000).  Each of these three spots is at least 1000 miles from the
others.  The amount of time spent by the bird in each spot is at least 90 days.
 Return 1.

TEST CASES:

{ "0,0,1,1", "00708,708,6,1" } returns 1.
{ "200,400,7,1", "100,0,1,1", "200,200,3,1", "0,400,11,1", "407,308,5,1",
"100,600,9,1" } returns 0.
Definition
    
Class:
Birds
Method:
isMigratory
Parameters:
vector <string>
Returns:
int
Method signature:
int isMigratory(vector <string> param0)
(be sure your method is public)
    

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.
#include <vector>
#include <string>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

using namespace std;

typedef vector<string> StringVector;
typedef vector<int> IntVector;

int dayOfMonth[12]=
{
	31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31
};

struct MyBird
{
	int month;
	int day;
	int x;
	int y;
	int dayCount;
};

int birdComp(const void* first, const void* second)
{
	MyBird* ptr1, *ptr2;
	ptr1=(MyBird*)first;
	ptr2=(MyBird*)second;
	if (ptr1->month!=ptr2->month)
	{
		return ptr1->month-ptr2->month;
	}
	return ptr1->day-ptr2->day;
}

class Birds
{
private:
	IntVector remoteGroup[15];
	MyBird myBird[15];
	int birdCount;
	
	bool insideGroup(int element, int groupIndex);
	void calculateGroup(int index);
	void calculateStay(int index);
	int dayBetween(int month1, int day1, int month2, int day2);
	void readString(StringVector param);
	bool scanIndex(int index);
	bool existPeriod(IntVector group);
public:
	int isMigratory(StringVector param);
};

bool Birds::insideGroup(int element, int groupIndex)
{
	for (int i=0; i<remoteGroup[groupIndex].size(); i++)
	{
		if (element==remoteGroup[groupIndex][i])
		{
			return true;
		}
	}
	return false;
}

bool Birds::existPeriod(IntVector group)
{
	bool isElement;
	int prev=-1;
	int days=0;
	int current;
	for (int i=0; i<remoteGroup[group[0]].size(); i++)
	{		
		isElement=true;
		current=remoteGroup[group[0]][i];
		for (int j=1; j<group.size(); j++)
		{
			if (!insideGroup(current, group[j]))
			{
				isElement=false;
				break;
			}
		}
		//common element condition
		if (!isElement)
		{
			days=0;
			prev=-1;
		}
		else
		{
			//continueous condition
			if (prev==-1||prev+1==current)
			{
				days+=myBird[current].dayCount;
				prev=current;
			}
			else
			{
				prev=-1;
				days=0;
			}
			if (days>=90)
			{
				return true;
			}
		}
	}
	return false;
}		
		

int Birds::isMigratory(StringVector param)
{
	int i;
	
	readString(param);
	for (i=0; i<birdCount; i++)
	{
		calculateGroup(i);
		calculateStay(i);
	}
	for (i=0; i<birdCount; i++)
	{
		if (scanIndex(i))
		{
			return 1;
		}
	}
	return 0;
}

bool Birds::scanIndex(int index)
{
	IntVector group;
	int days=0;
	for (int i=index; i<birdCount; i++)
	{
		days+=myBird[i].dayCount;
		group.push_back(i);
		if (days>=90)
		{
			return existPeriod(group);
		}
	}
	return false;
}
			
		

void Birds::calculateGroup(int index)
{
	for (int i=index+1; i<birdCount; i++)
	{
		if (sqrt((myBird[index].x-myBird[i].x)*(myBird[index].x-myBird[i].x)+
			(myBird[index].y-myBird[i].y)*(myBird[index].y-myBird[i].y))>=1000)
		{
			remoteGroup[index].push_back(i);
		}
	}
}

int Birds::dayBetween(int month1, int day1, int month2, int day2)
{
	int result=0;
	if (month1==month2)
	{
		return day2-day1;
	}
	result+=dayOfMonth[month1-1]-day1+1;
	for (int i=month1+1; i<month2; i++)
	{
		result+=dayOfMonth[i-1];
	}
	result+=day2-1;
	return result;
}
		

void Birds::calculateStay(int index)
{
	int month1, month2, day1, day2;
	if (index+1==birdCount)
	{
		month2=12;
		day2=32;		
	}
	else
	{
		month2=myBird[index+1].month;
		day2=myBird[index+1].day;		
	}
	month1=myBird[index].month;
	day1=myBird[index].day;
	myBird[index].dayCount=dayBetween(month1, day1, month2, day2);
}			

void Birds::readString(StringVector param)
{
	for (int i=0; i<param.size(); i++)
	{
		sscanf(param[i].c_str(), "%d,%d,%d,%d", &myBird[i].x, &myBird[i].y, &myBird[i].month, 
			&myBird[i].day );
	}
	birdCount=param.size();
	
	qsort(myBird, birdCount, sizeof(MyBird), birdComp);
}
9. RuleEngine(problem 1000)
Problem Statement
    
PROBLEM STATEMENT:

A rule engine is simply a warehouse of tests.  Based on the result of these
tests, actions are taken.  When a set of rules causes an action to be taken,
the rule set is said to "fire".

EXAMPLE Rule Sets:

Example 1:
If the monkey is hungry and the monkey has a banana in it's hand, then the
monkey eats the banana.  The rule set has two rules:
IF:
	(RULE) monkey is hungry
	(RULE) monkey has banana
THEN:
	(ACTION) monkey eats banana.

Example 2:
If X = 2, and Y is between 10 and 15, and Z = 5, then Z = 4.  The rule set has
three rules:
IF:
	(RULE) X = 2
	(RULE) Y between 10 and 15
	(RULE) Z = 5
THEN:
	(ACTION) set Z = 4

DEFINITION:

It is often very important to know when a given state will cause two different
rule sets to fire.  You will be given two rule sets.  Determine whether there
are any data sets that will cause both rule sets to fire. If so, return the
number of such sets within a set of given bounds.  If not, return "0".
The elements of the rule sets are of the form "<X><comparison>data1,data2" or
"<X><comparison>data1" where <comparison> can be "==", "<", "<=", ">", ">=",
"!=", or "B". <X> is a variable name, a single capital letter 'A'-'Z'. The
element would be TRUE if the comparison of the value in <X> to data1 (or data1
and data2) was true. If all elements of the rule set are TRUE, then the rule
set fires (Double-quotes and angle-brackets are for clarity only).

<comparison> legend:
==	X == data1
<	X < data1
<=	X <= data1
>	X > data1
>=	X >= data1
!=	X != data1
B	X is between data1 and data2, inclusive

X represents an integer variable whose range of possible values are specified
by the below rules.

Method signature: String countSets(String[] ruleSet1, String[] ruleSet2)
Be sure your method is public.

TopCoder will enforce the validity of the inputs.  Inputs are considered valid
if all of the following criteria are met:
  *ruleSet1 and ruleSet2 each have between 1 and 7 elements, inclusive.
*each element of ruleSet1 and ruleSet2 is either of the form
"<X><comparison><data1>" where <comparison> is not the letter "B", or of the
form "<X>B<data1>,<data2>" (quotes and angle-brackets are shown for clarity,
they do not appear in the input).
  *<X> is a letter between 'A' and 'Z', inclusive (upper-case only).
*<data1> and <data2> are integers between -9 and 9, inclusive.  Leading zeros
are possible.
  *<comparison> is one of the following: "==", "<", "<=", ">", ">=", "!=", "B".
*If the <comparison> code is 'B', then <data1> will be less than or equal to
<data2>.

Return the number of distinct data sets made up of values between -10 and 10,
inclusive that will cause both rules to fire.
Format the return value as a String.

WORKED EXAMPLES:

ruleSet1 = { "A<1", "B>2" }, ruleSet2 = { "A>1", "BB1,2" }.
Here ruleSet1 will fire if the value in A is less than 1, and the value in B is
greater than 2.  ruleSet2 will fire if the value in A is greater than 1, and
the value in B is between 1 and 2.  The rule sets are mutually exclusive, for A
cannot be both greater than and less than 1 so return "0".

ruleSet1 = { "A<0" }, ruleSet2 = { "A<0" }.
Both rulesets will fire for any value of A between -10 and -1, inclusive.
There are 10 such values, so return "10".

ruleSet1 = { "A==1", "X>=4", "F<1" }, ruleSet2 = { "X>=5", "ZB2,9" }.
ruleSet1 will fire when A is 1, X is greater or equal to 4, and F is less than
1.  ruleSet2 will fire when X is greater than or equal to 5, and Z is between 2
and 9, inclusive.  Both rule sets will fire when:
A is 1.
X is greater than or equal to 5.
F is less than or equal to 0.
Z is between 2 and 9, inclusive.

Hence, the rule sets are not mutually exclusive, so calculate the number of
distinct data sets that can cause the rule set to fire, in which the values are
between -10 and 10, inclusive:

A can only be 1 (1 possible element).
X can be between 5, and 10 inclusive (6 possible elements).
F can be between -10 and 0 inclusive (11 possible elements). 
Z can be between 2 and 9 inclusive (8 possible elements).

The number of distinct data sets that can cause both rule sets to fire within
the given bounds is: 1 * 6 * 11 * 8 = 528.  Return "528".

TEST CASES:

{ "A<1", "B==2", "C>4", "D>=6", "E<=9", "FB1,2", "J!=6" }, { "E>9" } returns "0".
{ "A<01", "B==2", "C>4", "D>=2", "E<=9", "FB1,2", "J!=6" }, { "A<9", "B>=2" }
returns "475200".
{ "A<=9", "B<=9", "C<=9", "D<=9", "E<=9", "F<=9", "G<=9" }, { "H<=9", "I<=9",
"J<=9", "K<=9", "L<=9", "M<=9", "N<=9" } returns "1638400000000000000".
{ "KB-09,5", "K<3" }, { "Y>4" } returns "72".
Definition
    
Class:
RuleEngine
Method:
countSets
Parameters:
vector <string>, vector <string>
Returns:
string
Method signature:
string countSets(vector <string> param0, vector <string> param1)
(be sure your method is public)
    

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.
#include <stdio.h>
#include <vector>
#include <set>
#include <string>

using namespace std;
typedef vector<string> StringVector;
typedef set<int> IntSet;
typedef pair<char, IntSet> Rule;
typedef vector<Rule> RuleVector;


enum Operation
{
	Equal, Smaller, SmallerEqual, Greater, GreaterEqual, NotEqual, Between
};
	
class RuleEngine
{
	RuleVector rule1, rule2;
	void parseRule(string input, RuleVector& ruleVector);	
	void addNumber(const char* number, Operation op, IntSet& intSet);
	void commonSet(IntSet first, IntSet second, IntSet& result);
public:
	string countSets(StringVector param1, StringVector param2);
};

void RuleEngine::commonSet(IntSet first, IntSet second, IntSet& result)
{	
	IntSet::iterator src, dest;

	for (src=first.begin(); src!=first.end(); src++)
	{
		dest=second.find(*src);
		if (dest!=second.end())
		{
			result.insert(*src);
		}
	}
}


void RuleEngine::addNumber(const char* number, Operation op, IntSet& intSet)
{
	int first, second, i;
	int length;
	length=strlen(number);
	if (op!=Between)
	{
		if (number[0]=='-')
		{		
			first=-(number[length-1]-'0');		
		}
		else
		{
			first=number[length-1]-'0';
		}			
		switch (op)
		{
		case Equal:
			intSet.insert(first);
			break;
		case Greater:
			for (i=first+1; i<=10; i++)
			{
				intSet.insert(i);
			}
			break;
		case GreaterEqual:
			for (i=first; i<=10; i++)
			{
				intSet.insert(i);
			}
			break;
		case Smaller:
			for (i=-10; i<first; i++)
			{
				intSet.insert(i);
			}
			break;
		case SmallerEqual:
			for (i=-10; i<=first; i++)
			{
				intSet.insert(i);
			}
			break;
		case NotEqual:
			for (i=-10; i<=10; i++)
			{
				if (i!=first)
				{
					intSet.insert(i);
				}
			}
			break;
		}
	}
	else
	{
		//find ','
		for (i=0; i<4; i++)
		{
			if (number[i]==',')
			{
				break;
			}
		}
		if (number[0]=='-')
		{
			first=-(number[i-1]-'0');
		}
		else
		{
			first=number[i-1]-'0';
		}
		if (number[i+1]=='-')
		{
			second=-(number[length-1]-'0');
		}
		else
		{
			second=number[length-1]-'0';
		}
		for (i=first; i<=second; i++)
		{
			intSet.insert(i);
		}
	}
}
	

void RuleEngine::parseRule(string input, RuleVector& ruleVector)
{
	char ch;
	IntSet intSet, common;
	ch=input[0];
	switch (input[1])
	{
	case '=':
		addNumber(input.c_str()+3, Equal, intSet);
		break;
	case '<':
		if (input[2]=='=')
		{
			addNumber(input.c_str()+3, SmallerEqual, intSet);
		}
		else
		{	
			addNumber(input.c_str()+2, Smaller, intSet);
		}
		break;
	case '>':
		if (input[2]=='=')
		{
			addNumber(input.c_str()+3, GreaterEqual, intSet);
		}
		else
		{
			addNumber(input.c_str()+2, Greater, intSet);
		}
		break;
	case '!':
		addNumber(input.c_str()+3, NotEqual, intSet);
		break;
	case 'B':
		addNumber(input.c_str()+2, Between, intSet);
		break;
	}

	for (int i=0; i<ruleVector.size(); i++)
	{
		if (ch==ruleVector[i].first)
		{
			commonSet(ruleVector[i].second, intSet, common);
			ruleVector[i].second.clear();
			copy(common.begin(), common.end(), 
				inserter(ruleVector[i].second, ruleVector[i].second.begin()));
			return;
		}
	}
	ruleVector.push_back(make_pair(ch, intSet));
}

string RuleEngine::countSets(StringVector param1, StringVector param2)
{
	int i;

	char buffer[20];
	IntSet intSet;
	//long long result=1;
	unsigned long long result=1;
	RuleVector::iterator it;

	for (i=0; i<param1.size(); i++)
	{
		parseRule(param1[i], rule1);
	}
	for (i=0; i<param2.size(); i++)
	{
		parseRule(param2[i], rule2);
	}
	for (i=0; i<rule1.size(); i++)
	{
		it=rule2.begin();
		while (it!=rule2.end())
		{
			if (rule1[i].first==it->first)
			{	
				intSet.clear();
				commonSet(rule1[i].second, it->second, intSet);
				if (intSet.size()==0)
				{
					return string("0");
				}
				rule1[i].second.clear();
				rule2.erase(it);
				it=rule2.begin();
				copy(intSet.begin(), intSet.end(), 
					inserter(rule1[i].second, rule1[i].second.begin()));
				
			}
			else
			{
				it++;
			}
		}	
	}

	for (i=0; i<rule1.size(); i++)
	{
		result*=(unsigned long long)rule1[i].second.size();		
	}
	for (i=0; i<rule2.size(); i++)
	{
		result*=(unsigned long long)rule2[i].second.size();
	}
	sprintf(buffer, "%llu", result);
	return string(buffer);
}

					 back.gif (341 bytes)       up.gif (335 bytes)         next.gif (337 bytes)