top coder practice room(practice room1-16)(2001 invi-semi)

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);
    }