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

TopCoder practice room(2001 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. match-maker (problem 250)

    /*

    Problem Statement

    THIS PROBLEM WAS TAKEN FROM THE SEMIFINALS OF THE TOPCODER INVITATIONAL
    TOURNAMENT

    DEFINITION
    Class Name: MatchMaker
    Method Name: getBestMatches
    Paramaters: String[], String, int
    Returns: String[]
    Method signature (be sure your method is public):  String[]
    getBestMatches(String[] members, String currentUser, int sf);

    PROBLEM STATEMENT
    A new online match making company needs some software to help find the "perfect
    couples".  People who sign up answer a series of multiple-choice questions.
    Then, when a member makes a "Get Best Mates" request, the software returns a
    list of users whose gender matches the requested gender and whose answers to
    the questions were equal to or greater than a similarity factor when compared
    to the user's answers.

    Implement a class MatchMaker, which contains a method getBestMatches.  The
    method takes as parameters a String[] members, String currentUser, and an int
    sf:
    - members contains information about all the members.  Elements of members are
    of the form "NAME G D X X X X X X X X X X"
       * NAME represents the member's name
       * G represents the gender of the current user.
       * D represents the requested gender of the potential mate.
    * Each X indicates the member's answer to one of the multiple-choice
    questions.  The first X is the answer to the first question, the second is the
    answer to the second question, et cetera.
    - currentUser is the name of the user who made the "Get Best Mates" request.
    - sf is an integer representing the similarity factor.

    The method returns a String[] consisting of members' names who have at least sf
    identical answers to currentUser and are of the requested gender.  The names
    should be returned in order from most identical answers to least.  If two
    members have the same number of identical answers as the currentUser, the names
    should be returned in the same relative order they were inputted.

    TopCoder will ensure the validity of the inputs.  Inputs are valid if all of
    the following criteria are met:
    - members will have between 1 and 50 elements, inclusive.
    - Each element of members will have a length between 7 and 44, inclusive.
    - NAME will have a length between 1 and 20, inclusive, and only contain
    uppercase letters A-Z.
    - G can be either an uppercase M or an uppercase F.
    - D can be either an uppercase M or an uppercase F.
    - Each X is a capital letter (A-D).
    - The number of Xs in each element of the members is equal.  The number of Xs
    will be between 1 and 10, inclusive.
    - No two elements will have the same NAME.
    - Names are case sensitive.
    - currentUser consists of between 1 and 20, inclusive, uppercase letters, A-Z,
    and must be a member.
    - sf is an int between 1 and 10, inclusive.
    - sf must be less than or equal to the number of answers (Xs) of the members.

    NOTES
    The currentUser should not be included in the returned list of potential mates.

    EXAMPLES

    For the following examples, assume members =
    {"BETTY F M A A C C",
     "TOM M F A D C A",
     "SUE F M D D D D",
     "ELLEN F M A A C A",
     "JOE M F A A C A",
     "ED M F A D D A",
     "SALLY F M C D A B",
     "MARGE F M A A C C"}

    If currentUser="BETTY" and sf=2, BETTY and TOM have two identical answers and
    BETTY and JOE have three identical answers, so the method should return
    {"JOE","TOM"}.

    If currentUser="JOE" and sf=1, the method should return
    {"ELLEN","BETTY","MARGE"}.

    If currentUser="MARGE" and sf=4, the method should return [].
    Definition

    Class:
    MatchMaker
    Method:
    getBestMatches
    Parameters:
    vector <string>, string, int
    Returns:
    vector <string>
    Method signature:
    vector <string> getBestMatches(vector <string> param0, string param1, 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 <string>
    #include <stdio.h>
    #include <vector>

    using namespace std;
    typedef vector<string> StringVector;
    typedef vector<int> IntVector;
    typedef vector<StringVector> StringVectorVector;

    void display(StringVector strVect);

    class MatchMaker
    {
    public:
    	StringVectorVector table;
    	void parseString(string& input, StringVector& output);
    //public:
    	StringVector getBestMatches(StringVector input, string member, int sf);
    };

    void MatchMaker::parseString(string& input, StringVector& output)
    {
    	string::size_type pos=0, start=0;
    	string result;

    	while (true)
    	{
    		pos=input.find_first_of(' ', start);
    		if (pos==string::npos)
    		{
    			pos=input.size();
    		}
    		result.assign(input, start, pos-start);
    		output.push_back(result);
    		start=pos+1;
    		if (start>=input.size())
    		{
    			break;
    		}
    	}
    }

    StringVector MatchMaker::getBestMatches(StringVector input, string member, int sf)
    {
    	int i, j, index=-1, counter;
    	StringVector output;
    	IntVector priority;
    	for (i=0; i<input.size(); i++)
    	{
    		output.clear();
    		parseString(input[i], output);
    		table.push_back(output);
    		if (member.compare(output[0])==0)
    		{
    			index=i;
    		}
    	}

    	output.clear();
    	if (index==-1)
    	{
    		printf("error");
    		return output;
    	}

    	for (i=0; i<table.size(); i++)
    	{
    		//here they don't care about the "selected matching's feeling"
    		//if (i!=index&&table[index][1].compare(table[i][2])==0&&table[index][2].compare(table[i][1])==0)
    		if (i!=index&&table[index][2].compare(table[i][1])==0)
    		{
    			counter=0;
    			for (j=3; j<table[i].size(); j++)
    			{
    				if (table[i][j].compare(table[index][j])==0)
    				{
    					counter++;
    				}
    			}
    			if (counter>=sf)
    			{
    				output.push_back(table[i][0]);
    				priority.push_back(counter);
    			}
    		}
    	}
    	printf("display output\n");
    	display(output);
    	printf("display output\n");
    	for (i=0; i<priority.size(); i++)
    	{
    		counter=priority[i];
    		index=i;
    		for (j=i+1; j<priority.size(); j++)
    		{
    			if (counter<priority[j])
    			{
    				counter=priority[j];
    				index=j;
    			}
    		}
    		//result.push_back(output[index]);
    		counter=priority[i];
    		priority[i]=priority[index];
    		priority[index]=counter;

    		output[i].swap(output[index]);
    	}

    	return output;
    }

    void display(StringVector strVect)
    {
    	for (int i=0; i<strVect.size(); i++)
    	{
    		printf("%s\n", strVect[i].c_str());
    	}
    	printf("\n");
    }

    /*
    char* members[8] =
    {
    	"BETTY F M A A C C",
    	"TOM M F A D C A",
    	"SUE F M D D D D",
    	"ELLEN F M A A C A",
    	"JOE M F A A C A",
    	"ED M F A D D A",
    	"SALLY F M C D A B",
    	"MARGE F M A A C C"
    };
    */
    char* members[5] =
    {
    	"SUE F M D A C B",
    	"JOE M F D C C A",
    	"GEORGE M F D A C B",
    	"BOB M F D A C B",
    	"ED M F D C B A"
    };

    int main()
    {
    	int len=5;
    	StringVector input, output;
    	string curMember="SUE";
    	MatchMaker matchMaker;
    	for (int i=0; i<len; i++)
    	{
    		input.push_back(string(members[i]));

    	}
    	display(input);
    	output=matchMaker.getBestMatches(input, curMember, 1);
    	display(output);
    	/*
    	for (i=0; i<matchMaker.table.size(); i++)
    	{
    		display(matchMaker.table[i]);
    	}
    	*/

    	return 0;
    }

    2. Tothello (problem 500)

    /*

    Problem Statement

    THIS PROBLEM WAS TAKEN FROM THE SEMIFINALS OF THE TOPCODER INVITATIONAL
    TOURNAMENT

    Class Name: Tothello
    Method Name: bestMove
    Parameters: String[], String[], String
    Returns: int
    Method signature (be sure your method is public):  int bestMove(String[]
    redPieces, String[] blackPieces, String whoseTurn);

    PROBLEM STATEMENT
    The game Tothello is a TopCoder modified version of the board game Othello.
    The game is played on an 8 x 8 grid with two players, Black and Red.  The
    players alternate turns placing one piece representing their color in one empty
    square of the grid.  When the Red player puts a red piece down, any black
    pieces that end up between the piece that was placed on the board and any other
    red piece already on the board should be changed to red.  If the change in
    color from black to red of any piece on the board causes other black pieces to
    lie between two red pieces, those black pieces should also be changed to red.
    The changing of black pieces will continue until no one black piece lies
    between two red pieces.  The manner that pieces change color apply when the
    Black player places a piece on the grid, however, the pieces would then change
    from red to black.  A player also has the option of passing - not putting any
    pieces down - on his turn, in which case the other player just gets to go twice
    in a row.

    You are to write a program that helps a player determine their best possible
    move - the move that results in the most pieces being that player's color at
    the end of the move.

    Implement a class Tothello that contains a method bestMove.  bestMove inputs
    the current state of the grid before a specified player's move and outputs the
    number of the player's pieces on the board as a result of the player's best
    move.

    NOTES
    - redPieces is a String[] representing the current positions of red pieces on
    the board.
    - blackPieces is a String[] representing the current positions of black pieces
    on the board.
    - The board is an 8x8 grid with the columns referred to by the uppercase
    letters A-H and the rows referred to by the numbers 1-8 (inclusive).  The
    column is specified before the row.  A1 is in the upper left.  H8 is in the
    lower right.
    - redPieces and blackPieces are not necessarily the same length (players may
    have passed on moves).
    - A black piece is between two red pieces if a red piece can be found before an
    empty square on either side by following the horizontal, vertical, or either
    diagonal out from the Black piece.  For example:

    - - - R - - - -
    - - - B - - - -
    - - - B - - - -    All three Black pieces are between two red pieces.
    - - - B - - - -
    - - - R - - - -

    - - - R - - - -
    - - - B B - - -
    - - - B - B - -   All four Black pieces are between two Red pieces.
    - - - R R R R R

    - - - R - - - -
    - - - B R - - -
    - - - - - - - -   The Black piece is not between two Red pieces.
    - - - R R - - -

    R R R R R R R R
    R - - - - - - R
    R - B B - B - R
    R - B B B B - R   None of the Black pieces are between two Red pieces.
    R - - - - - - R
    R R R R R R R R

    TopCoder will ensure the validity of the inputs.  Inputs are valid if all of
    the following criteria are met:
    - Both redPieces and blackPieces contain between 0 and 50 elements (inclusive).
    - All elements of redPieces and blackPieces consist of uppercase letters A-H
    and numbers 1-8 (inclusive).
    - All elements of redPieces and blackPieces are in the form of letter-number
    pairs with each letter representing the column and each number representing the
    row of the piece's position (i.e. "A2" where 'A' is the column and '2' is the
    row of the piece's position).
    - whoseTurn is a String that is equal to either "Red" or "Black" representing
    the player for which the method is being run.
    - The current state of the board represented by redPieces and blackPieces
    contains no red pieces between any black pieces and no black pieces between any
    red pieces (a state where there were black pieces between red pieces is
    impossible at the start of a move, assuming the game has been played
    correctly.)
    - The elements are unique in redPieces and blackPieces, and redPieces and
    blackPieces do not contain any of the same elements.
    - The game board must start with at least one unoccupied space.

    EXAMPLES
    If redPieces=[C2,C3,C4,C5,D4,E4,F2,F3,F4,F5,G6] and
    blackPieces=[B1,E1,G1,C6,H7,G4] and whoseTurn="Black",
    Before the player's move, the board is:

      A B C D E F G H
    1 - B - - B - B -
    2 - - R - - R - -
    3 - - R - - R - -
    4 - - R R R R B -
    5 - - R - - R - -
    6 - - B - - - R -
    7 - - - - - - - B
    8 - - - - - - - -

    Black's best move is C1, which results in:

    A B C D E F G H       A B C D E F G H       A B C D E F G H      A B C D E F
    G H
    1 - B - - B - B -     1 - B B - B - B -     1 - B B - B - B -     1-BB-B-B-
    2 - - R - - R - -     2 - - B - - R - -     2 - - B - - R - -     2 - - B - - R
    - -
    3 - - R - - R - -     3 - - B - - R - -     3 - - B - - R - -     3 - - B - - R
    - -
    4 - - R R R R B - --> 4 - - B R R R B - --> 4 - - B B B B B - --> 4 - - B B B B
    B -
    5 - - R - - R - -     5 - - B - - R - -     5 - - B - - R - -     5 - - B - - B
    - -
    6 - - B - - - R -     6 - - B - - - R -     6 - - B - - - R -     6 - - B - - -
    B -
    7 - - - - - - - B      7 - - - - - - - B     7 - - - - - - - B     7 - - - - -
    - - B
    8 - - - - - - - -     8 - - - - - - - -     8 - - - - - - - -     8 - - - - - -
    - -

    There end up being 16 black pieces, so the method should return 16.

    If redPieces=[A1,B8,C6,C8,D8] and blackPieces=[B2,C2,C3,C4,C5] and
    whoseTurn="Red", Red's best move is C1, and the method should return 11.

    Definition

    Class:
    Tothello
    Method:
    bestMove
    Parameters:
    vector <string>, vector <string>, string
    Returns:
    int
    Method signature:
    int bestMove(vector <string> param0, vector <string> param1, string 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.
    <<<<<<<<<<<<<total time is about 2 hours! I am too slow!>>>>>>>>>>>
    */

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

    using namespace std;

    typedef vector<string> StringVector;
    const unsigned int BoardSize=8;

    struct Coord
    {
    	int row;
    	int col;
    };

    typedef vector<Coord> CoordVector;

    #define NW		0
    #define N		1
    #define NE		2
    #define E		3
    #define SE		4
    #define S		5
    #define SW		6
    #define W		7

    class Tothello
    {
    private:
    	char playerColor;

    	CoordVector coordVector;
    	char board[BoardSize][BoardSize];
    	void parseCoord(string& str, int& row, int& col);

    	bool isEnemy(int row, int col, char myColor);

    	void changeColor(int row, int col, char newColor);
    	void init(StringVector& redState, StringVector& blackState, string player);
    	bool getCoord(int& row, int& col, int dir);
    	bool startSearch(int row, int col, char myColor, int dir);
    	int calculateMove(int row, int col, char myColor);
    	int forEachMove(StringVector enemyState, char myColor);
    public:
    	int bestMove(StringVector redState, StringVector blackState, string player);
    };

    bool Tothello::isEnemy(int row, int col, char myColor)
    {
    	if (myColor=='B')
    	{
    		return board[row][col]=='R';
    	}
    	else
    	{
    		return board[row][col]=='B';
    	}
    }

    int Tothello::calculateMove(int row, int col, char myColor)
    {
    	int nextRow, nextCol, curRow, curCol;
    	int i;
    	char enemyColor;
    	CoordVector path;

    	coordVector.clear();

    	changeColor(row, col, myColor);
    	do
    	{
    		curRow=coordVector.back().row;
    		curCol=coordVector.back().col;
    		path.push_back(coordVector.back());
    		coordVector.pop_back();
    		for (i=0; i<8; i++)
    		{
    			nextRow=curRow;
    			nextCol=curCol;
    			if (getCoord(nextRow, nextCol, i))
    			{
    				if (isEnemy(nextRow, nextCol, myColor))
    				{
    					//if the enemy cannot survive then apply recursion
    					startSearch(nextRow, nextCol, myColor, i);
    				}
    			}
    		}
    	}
    	while (!coordVector.empty());
    	//now let's restore

    	enemyColor=(myColor=='R')?'B':'R';

    	//because the first one is "empty", starting from second
    	for (i=1; i<path.size(); i++)
    	{
    		board[path[i].row][path[i].col]=enemyColor;
    	}
    	board[row][col]='E';//restore the empty place
    	return path.size();//this is how many enemy we converted
    }

    int Tothello::forEachMove(StringVector enemyState, char myColor)
    {
    	int currentBest=0, result;
    	int row, col, nextRow, nextCol;
    	int i, j;
    	for (i=0; i<enemyState.size(); i++)
    	{
    		//the interested place is always around our enemey piece
    		parseCoord(enemyState[i], row, col);
    		//check around enemy
    		for (j=0; j<8; j++)
    		{
    			nextRow=row;
    			nextCol=col;
    			if (getCoord(nextRow, nextCol, j))
    			{
    				if (board[nextRow][nextCol]=='E')
    				{
    					result=calculateMove(nextRow, nextCol, myColor);
    					if (result>currentBest)
    					{
    						currentBest=result;
    					}
    				}
    			}
    		}
    	}
    	return currentBest;
    }

    int Tothello::bestMove(StringVector redState, StringVector blackState, string player)
    {
    	int result;
    	init(redState, blackState, player);
    	if (playerColor=='R')
    	{
    		result=forEachMove(blackState, playerColor);
    		result+=redState.size();
    	}
    	else
    	{
    		result=forEachMove(redState, playerColor);
    		result+=blackState.size();
    	}
    	return result;
    }

    void Tothello::changeColor(int row, int col, char newColor)
    {
    	Coord coord;
    	coord.row=row;
    	coord.col=col;
    	coordVector.push_back(coord);
    	board[row][col]=newColor;
    }

    //this is a survival checking, so we start checking enemy color
    bool Tothello::startSearch(int row, int col, char enemyColor, int dir)
    {
    	int nextRow=row, nextCol=col;
    	//boom, we hit enemy, it means we are died
    	if (board[row][col]==enemyColor)
    	{
    		return false;
    	}
    	if (board[row][col]=='E')
    	{
    		//it is empty, we survival
    		return true;
    	}

    	//lucky we hit a wall
    	if (!getCoord(nextRow, nextCol, dir))
    	{
    		return true;
    	}
    	//from below it means we need our buddy to continue checking
    	if (!startSearch(nextRow, nextCol, enemyColor, dir))
    	{
    		//here let's save some time by changing the color
    		//board[row][col]=enemyColor;
    		changeColor(row, col, enemyColor);
    		return false;
    	}
    	else
    	{
    		return true;
    	}
    }

    bool Tothello::getCoord(int& row, int& col, int dir)
    {
    	switch (dir)
    	{
    	case NW:
    		row--;
    		col--;
    		break;
    	case N:
    		row--;
    		break;
    	case NE:
    		row--;
    		col++;
    		break;
    	case E:
    		col++;
    		break;
    	case SE:
    		col++;
    		row++;
    		break;
    	case S:
    		row++;
    		break;
    	case SW:
    		row++;
    		col--;
    		break;
    	case W:
    		col--;
    		break;
    	}
    	return row>=0&&row<BoardSize&&col>=0&&col<BoardSize;
    }

    void Tothello::parseCoord(string& str, int& row, int& col)
    {
    	col=str[0]-'A';
    	row=str[1]-'1';
    }

    void Tothello::init(StringVector& redState, StringVector& blackState, string player)
    {
    	int i;
    	int row, col;
    	for (i=0; i<BoardSize; i++)
    	{
    		memset(board[i], 'E', BoardSize);

    	}
    	for (i=0; i<redState.size(); i++)
    	{
    		parseCoord(redState[i], row, col);

    		board[row][col]='R';
    	}
    	for (i=0; i<blackState.size(); i++)
    	{
    		parseCoord(blackState[i], row, col);
    		board[row][col]='B';
    	}
    	if (player.compare("Black")==0)
    	{
    		playerColor='B';

    	}
    	else
    	{
    		playerColor='R';

    	}

    }

    /*
    char* redState[5]=
    {
    	"A1", "B8", "C6", "C8", "D8"
    };

    char* blackState[5]=
    {
    	"B2", "C2", "C3", "C4", "C5"
    };
    */

    char* redState[]=
    {
    	"C2", "C3", "C4", "C5", "D4", "E4", "F2", "F3", "F4", "F5", "G6"
    };

    char* blackState[]=
    {
    	"B1", "E1", "G1", "C6", "H7", "G4"
    };

    int main()
    {
    	int i, redLen=11, blackLen=6, result;
    	StringVector red, black;
    	Tothello top;
    	for (i=0; i<redLen; i++)
    	{
    		red.push_back(string(redState[i]));
    	}
    	for (i=0; i<blackLen; i++)
    	{
    		black.push_back(string(blackState[i]));
    	}

    	result=top.bestMove(red, black, string("Black"));
    	printf("result=%d\n", result);

    	return 0;
    }

    3. ChessCover (problem 1000)

    /*

    Problem Statement

    THIS PROBLEM WAS TAKEN FROM THE SEMIFINALS OF THE TOPCODER INVITATIONAL
    TOURNAMENT

    PROBLEM STATEMENT
    In a game of chess, the king is always looking out for his safety, trying to
    stay out of the path of the opponent's attacking pieces.  Given an x by y
    rectangular chess board, with z opponent pieces placed on the board, determine
    how many safe squares are left on the board, where the king may be placed.
    Safe squares are squares that are not in the path of attack of one or more
    opponent piece(s).

    Discription of piece movement:
    - A queen's path of attack is any square contained in a horizontal, vertical,
    or diagonal line crossing the square on which it stands.
    - A rook's path of attack is any square contained in a horizontal or vertical
    line crossing the square on which it stands.
    - A bishop's path of attack is any square contained in a diagonal line crossing
    the square on which it stands.
    - A knight's path of attack is the last square of an L shaped movement
    (described below) starting from the square it is standing on.
    - A pawns path of attack is the first diagonal square in *all four directions*
    starting from the square it is standing on.

    The following must be true for a valid L shaped movement:
    1. Start from the square the knight is standing on.
    2. If the knight moves m square(s) horizontally then it must move n square(s)
    vertically
    3. If the knight moves m square(s) vertically then it must move n square(s)
    horizontally
    4. If m equals 1 then n must equal 2
    5. If n equals 1 then m must equal 2

    The input will be a String[] representing the squares on a rectangular chess
    board.  Each square is represented by a character having one of the following
    values:
    'U' will represent an unoccupied square (there are no pieces located in that
    square)
     'Q' will represent a queen in that square
     'R' will represent a rook in that square
     'B' will represent a bishop in that square
     'K' will represent a knight in that square
     'P' will represent a pawn in that square

    The following diagrams are meant to show how the pieces can move.  The pieces
    are represented as above, 'X' represents a square in the path of attack of the
    piece and '+' represents a safe square.

        Queen           Rook         Bishop         Knight          Pawn
    X + + X + + X  + + + X + + +  X + + + + + X  + + + + + + +  + + + + + + +
    + X + X + X +  + + + X + + +  + X + + + X +  + + X + X + +  + + + + + + +
    + + X X X + +  + + + X + + +  + + X + X + +  + X + + + X +  + + X + X + +
    X X X Q X X X  X X X R X X X  + + + B + + +  + + + K + + +  + + + P + + +
    + + X X X + +  + + + X + + +  + + X + X + +  + X + + + X +  + + X + X + +
    + X + X + X +  + + + X + + +  + X + + + X +  + + X + X + +  + + + + + + +
    X + + X + + X  + + + X + + +  X + + + + + X  + + + + + + +  + + + + + + +

    Implement a class ChessCover which contains a method getSafe.  getSafe should
    return the number of safe squares on the board.

    DEFINITION
    Class name: ChessCover
    Method name: getSafe
    Parameters:  String[]
    Returns: int
    Method signature (be sure your method is public):  int getSafe (String[]
    boardLayout);

    NOTES
    - The king is not on the board.  The purpose is to count the number of
    available safe squares on which the king can placed.
    - The board may be full, i.e. every square on the board can have a piece on it
    (z <= x*y).
    - There are five types of pieces: queen, rook, bishop, knight, and pawn.
    - The same type of piece may be placed on the board multiple times (i.e. there
    may be 5 queens on the board etc.).
    - The square on which a piece sits is not a safe square.
    - A Piece can block another piece's path of attack.
    - A knight is the only piece that can jump over another piece(s).
    - A pawn's path of attack differs from regular chess rules.  The pawn path of
    attack is the first diagonal square in *all four directions* starting from the
    square it is standing on.
    - The board is not necessarily square.  The number of rows could be the
    different than the number of columns.

    TopCoder will ensure the validity of the inputs.  Inputs are valid if all of
    the following criteria are met:
    - Each element of boardLayout will have a length between 1 and 10 (inclusive).
    - Each element of boardLayout will be of equal length.
    - Each element of boardLayout will consist of characters from the following
    list: 'U', 'Q', 'R', 'B', 'K', 'P'.
    - boardLayout will have between 1 and 10 elements, inclusive.

    EXAMPLES
    U U -> + + -> 4 safe squares
    U U    + +

    U U U U U    X X X X X
    U Q U Q U -> X Q X Q X -> 0 safe squares
    U U U U U    X X X X X

    U U U    X + X
    U P U -> + P + -> 4 safe squares
    U U U    X + X

    U U U U    X + X +
    U U U U    X X + +
    Q U U U -> Q X X X -> 6 safe squares
    U U U U    X X + +

    U U U U U Q    X X X X X Q
    U U U U U U    + X X X X X
    B U R U U U -> B X R X X X -> 6 safe squares
    U U K U U U    + X K + + X
    U U U U U U    X + X + X X

    U B U K U U U B U U -> + B + K + X X B X X -> 4 safe squares
    U U U U B U U Q U R    X X X + B X X Q X R
    Definition

    Class:
    ChessCover
    Method:
    getSafe
    Parameters:
    vector <string>
    Returns:
    int
    Method signature:
    int getSafe(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.

      <<<<<<<<<<<<<<<<<<it took me about 2 hours to finish, similar to level 500 problem>>>>>>>>>

    */

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

    using namespace std;

    typedef vector<string> StringVector;

    #define NW		0
    #define N		1
    #define NE		2
    #define E		3
    #define SE		4
    #define S		5
    #define SW		6
    #define W		7

    class ChessCover
    {
    private:
    	unsigned int width;
    	unsigned int height;
    	char**board;
    	char**place;
    	bool getCoord(int& row, int& col, int dir);
    	void init(StringVector& layout);
    	void boardSearch(int row, int col, int dir, char piece);
    	void calculateMove(int row, int col, char piece);
    public:
    	int getSafe(StringVector layout);
    };

    int ChessCover::getSafe(StringVector layout)
    {
    	int row, col;
    	int result=0;
    	init(layout);
    	for (row=0; row<height; row++)
    	{
    		for (col=0; col<width; col++)
    		{
    			if (board[row][col]!='U')
    			{
    				place[row][col]='N';
    				calculateMove(row, col, board[row][col]);
    			}
    		}
    	}

    	for (row=0; row<height; row++)
    	{
    		for (col=0; col<width; col++)
    		{
    			if (place[row][col]=='Y')
    			{
    				result++;
    			}
    		}
    		delete[]board[row];
    		delete[]place[row];
    	}
    	return result;
    }

    void ChessCover::calculateMove(int row, int col, char piece)
    {
    	int i;
    	for (i=0; i<8; i++)
    	{
    		switch (piece)
    		{
    		case 'Q':
    		case 'K':
    			boardSearch(row, col, i, piece);
    			break;//all dir
    		case 'R':
    			if (i%2==1)
    			{
    				boardSearch(row, col, i, piece);
    			}
    			break;
    		case 'B':
    		case 'P':
    			if (i%2==0)
    			{
    				boardSearch(row, col, i, piece);
    			}
    			break;
    		}
    	}
    }

    void ChessCover::boardSearch(int row, int col, int dir, char piece)
    {
    	int nextRow=row, nextCol=col;
    	switch (piece)
    	{
    	case 'Q':
    	case 'B':
    	case 'R':
    		if (getCoord(nextRow, nextCol, dir))
    		{
    			place[nextRow][nextCol]='N';
    			if (board[nextRow][nextCol]=='U')
    			{
    				boardSearch(nextRow, nextCol, dir, piece);
    			}
    		}
    		break;
    	case 'P':
    		if (getCoord(nextRow, nextCol, dir))
    		{
    			place[nextRow][nextCol]='N';
    		}
    		break;
    	case 'K':
    		if (getCoord(nextRow, nextCol, dir))
    		{
    			if (getCoord(nextRow, nextCol, (dir+1)%8))
    			{
    				place[nextRow][nextCol]='N';
    			}
    		}
    		break;
    	}
    }

    bool ChessCover::getCoord(int& row, int& col, int dir)
    {
    	switch (dir)
    	{
    	case NW:
    		row--;
    		col--;
    		break;
    	case N:
    		row--;
    		break;
    	case NE:
    		row--;
    		col++;
    		break;
    	case E:
    		col++;
    		break;
    	case SE:
    		col++;
    		row++;
    		break;
    	case S:
    		row++;
    		break;
    	case SW:
    		row++;
    		col--;
    		break;
    	case W:
    		col--;
    		break;
    	}
    	return row>=0&&row<height&&col>=0&&col<width;
    }

    void ChessCover::init(StringVector& layout)
    {
    	int i;
    	height=layout.size();
    	width=layout[0].size();
    	board=new char* [height];
    	place=new char*[height];
    	for (i=0; i<height; i++)
    	{
    		place[i]=new char[width];
    		board[i]=new char[width];
    	}

    	for (i=0; i<layout.size(); i++)
    	{
    		memcpy(board[i], layout[i].c_str(), width);
    		memset(place[i], 'Y', width);
    	}
    }

    /*
    char* board[]=
    {
    	"UU",
    	"UU"
    };
    */

    /*
    char* board[]=
    {
    	"UUUUU",
    	"UQUQU",
    	"UUUUU"
    };
    */

    char* board[]=
    {
    	"UUUUUQ",
    	"UUUUUU",
    	"BURUUU",
    	"UUKUUU",
    	"UUUUUU",
    };

    void createString(StringVector& strVect)
    {
    	for (int i=0; i<5; i++)
    	{
    		strVect.push_back(string(board[i]));
    	}
    }

    int main()
    {
    	ChessCover chess;
    	StringVector strVect;
    	createString(strVect);

    	printf("result=%d\n", chess.getSafe(strVect));

    	return 0;
    }

    ¡¡

    /////////////////////////////////////

    //inivitaion semi C-D

    ////////////////////////////////

    4. Checker (problem 250)

    ¡¡

    /*

    Problem Statement

    THIS PROBLEM WAS TAKEN FROM THE SEMIFINALS OF THE TOPCODER INVITATIONAL
    TOURNAMENT

    PROBLEM STATEMENT

    Checkers is a board game played with two players on an 8 by 8 board.  Player 1
    is represented by red game pieces and player 2 is represented by black game
    pieces.

    There are two types of moves for a game piece.  The first will be referred to
    as a simple move.  It involves moving a game piece diagonally 1 space. This
    means that the piece would be moved either up 1 space and right 1 space or up 1
    space and left 1 space.  Here are examples of a simple move.  ('-' is an
    unoccupied space, 'R' is a red piece, 'B' is a black piece, complete board may
    not be shown in diagram)

    - - - - - - - -        - - - - - - - -
    - - - - - - - -  --->  - - R - - - - -
    - R - - - - - -        - - - - - - - -
                      or
    - - - - - - - -        - - - - - - - -
    - - - - - - - -  --->  R - - - - - - -
    - R - - - - - -        - - - - - - - -

    The second type of move is referred to as a jump.  A jump involves moving over
    *one* of the opponents pieces and landing in an empty space.  A jump to the
    right would involve a piece moving diagonally two spaces to the right(right two
    and up two). Similarly, a jump to the left would involve a piece moving
    diagonally two spaces to the left(left two and up two).  See the following
    diagrams.

    - - - - - - - -        - - - - - - - -
    - - - - - - - -  --->  - - - - R - - -
    - B - B - - - -        - B - B - - - -
    - - R - - - - -        - - - - - - - -
                      or
    - - - - - - - -        - - - - - - - -
    - - - - - - - -  --->  R - - - - - - -
    - B - B - - - -        - B - B - - - -
    - - R - - - - -        - - - - - - - -

    Implement a class Checkers containing a method compute.  compute should return
    an int representing the fewest number of moves it will take for player 1 to
    move his red piece to the opposite end of the board.  If player 1 cannot get to
    the opposite end of the board using the moves described above, compute should
    return -1.

    DEFINITION
    Class Name: Checkers
    Method Name: compute
    Parameters: String, String[]
    Returns: int
    Method signature (be sure your method is public): int compute (String startPos,
    String[] pieces);

    TopCoder will ensure the validity of the inputs.  Inputs are valid if all of
    the following criteria are met:
    - pieces will contain between 0 and 50, inclusive, elements.
    - Each element of pieces will be in the form "column,row" (quotation marks are
    for clarity only) where column and row are integers between 0 and 7, inclusive.
    - startPos will be in the form "column,row" (quotation marks are for clarity
    only) where column and row are integers between 0 and 7, inclusive.
    - No two elements of pieces or startPos can have the same "column,row" value
    (that is, no two pieces may be placed on the same square of the board).

    NOTES
    - Consecutive jumps count as 1 move.
    - A game piece's location is not restricted the way it is in "real" checkers
    (pieces can be placed at or moved to any unoccupied location on the board).
    - To successfully perform either type of move, the destination square must be
    on the board and not occupied by another piece.
    - Input will be in coordinate format "x,y" (quotation marks are for clarity
    only) where the bottom left spot on the board is "0,0", the bottom right spot
    on the board is "7,0", the top left is "0,7" and the top right is "7,7".
    - The opposite end of the board is defined as the top row of the board,
    specifically, any location on the board where the y (row) coordinate is 7.
    -  The red piece can only move or jump in the direction of the opposite end of
    the board.  For example, each move or jump (including subsequent jumps in the
    case of multiple jumps) must have a row value that is greater than that of the
    previous position of that piece.

    EXAMPLES
    1.
            Fig. 1               Fig. 2              Fig. 3              Fig. 4
      7 - - - - - - - -    7 - - - - - - - -   7 - - - - - - - -   7 - - - - - - R -
      6 - - - - - B - -    6 - - - - - B - -   6 - - - - - B - -   6 - - - - - B - -
      5 - - - - - - - -    5 - - - - - - - -   5 - - - - R - - -   5 - - - - - - - -
      4 - - - - - - - -    4 - - - - - R - -   4 - - - - - - - -   4 - - - - - - - -
      3 B - - - B - - -    3 B - - - B - - -   3 B - - - B - - -   3 B - - - B - - -
      2 - - - - B - - -    2 - - - - B - - -   2 - - - - B - - -   2 - - - - B - - -
      1 - - B - - - - -    1 - - B - - - - -   1 - - B - - - - -   1 - - B - - - - -
      0 - R - - - - - -    0 - - - - - - - -   0 - - - - - - - -   0 - - - - - - - -
        0 1 2 3 4 5 6 7      0 1 2 3 4 5 6 7     0 1 2 3 4 5 6 7     0 1 2 3 4 5 6 7

      startPos = "1,0"
      pieces = {"2,1", "0,3", "4,3", "5,6", "4,2"}

      Fig. 1: The initial setup of the board.  Move count = 0;
    Fig. 2: The red piece has made a jump from 1,0 to 3,2 and then from 3,2 to
    5,4.  Remember, this only counts as a single move.  Move count = 1;
    Fig. 3: The red piece has made a simple move from 5,4 to 4,5.  Move count =
    2;
      Fig. 4: The red piece has jumped from 4,5 to 6,7.  Move count = 3;

      So the output is: 3
    Because the fewest number of moves from startPos to the opposite end of the
    board is 3.

    2.
      startPos = "4,4"
      pieces = {}
      return: 3

    3.
      startPos = "4,4"
      pieces = {"6,6", "5,5", "3,5", "2,6"}
      return: -1

    4.
      startPos = "4,1"
      pieces = {"2,4", "3,4", "4,4", "5,4", "2,6", "3,6", "4,6", "5,6"}
      return: 3

    Definition

    Class:
    Checkers
    Method:
    compute
    Parameters:
    string, vector <string>
    Returns:
    int
    Method signature:
    int compute(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 <string>
    #include <vector>

    using namespace std;

    typedef vector<string> StringVector;

    const unsigned int BoardSize=8;

    class Checkers
    {
    private:
    	char board[BoardSize][BoardSize];
    	void init(StringVector& pieces);
    	bool doSearch(int row, int col, int& stepCounter, bool isSimple);
    	bool simpleMove(int& row, int& col, int dir);
    	bool complexMove(int& row, int& col, int dir);
    public:
    	int compute(string startPos, StringVector pieces);
    };

    void Checkers::init(StringVector& pieces)
    {
    	int i, j, r, c;
    	for (i=0; i<BoardSize; i++)
    	{
    		for (j=0; j<BoardSize; j++)
    		{
    			board[i][j]='N';
    		}
    	}
    	for (i=0; i<pieces.size(); i++)
    	{
    		c=pieces[i].c_str()[0]-'0';
    		r=pieces[i].c_str()[2]-'0';
    		board[r][c]='Y';
    	}
    }

    int Checkers::compute(string startPos, StringVector pieces)
    {
    	int row, col, stepCounter=0;
    	init(pieces);

    	col=startPos.c_str()[0]-'0';
    	row=startPos.c_str()[2]-'0';

    	if (doSearch(row, col, stepCounter, true))
    	{
    		return stepCounter;
    	}
    	else
    	{
    		return -1;
    	}
    }

    //left=0, right=1
    bool Checkers::doSearch(int row, int col, int& stepCounter, bool isSimple)
    {
    	int currentStep, curRow, curCol, bestStep=-1, i;
    	bool result;
    	if (row==BoardSize-1)
    	{
    		return true;
    	}
    	for (i=0; i<2; i++)
    	{
    		currentStep=stepCounter;
    		curRow=row;
    		curCol=col;

    		if (simpleMove(curRow, curCol, i))
    		{
    			currentStep=stepCounter+1;
    			result=doSearch(curRow, curCol, currentStep, true);
    			if (result&&bestStep==-1||currentStep<bestStep)
    			{
    				bestStep=currentStep;
    			}
    		}

    	}
    	for (i=0; i<2; i++)
    	{
    		currentStep=stepCounter;
    		curRow=row;
    		curCol=col;
    		if (complexMove(curRow, curCol, i))
    		{
    			if (isSimple)
    			{
    				currentStep=stepCounter+1;
    			}
    			result=doSearch(curRow, curCol, currentStep, false);
    			if (result&&bestStep==-1||currentStep<bestStep)
    			{
    				bestStep=currentStep;
    			}
    		}

    	}
    	if (bestStep!=-1)
    	{
    		stepCounter=bestStep;
    		return true;
    	}
    	else
    	{
    		return false;
    	}

    }

    bool Checkers::complexMove(int& row, int& col, int dir)
    {
    	if (dir==0)
    	{
    		col--;
    	}
    	else
    	{
    		col++;
    	}
    	row++;
    	if (col<0||col==BoardSize||row==BoardSize)
    	{
    		return false;
    	}
    	if (board[row][col]!='Y')
    	{
    		return false;
    	}
    	if (dir==0)
    	{
    		col--;
    	}
    	else
    	{
    		col++;
    	}
    	row++;
    	if (col<0||col==BoardSize||row==BoardSize)
    	{
    		return false;
    	}
    	return board[row][col]!='Y';

    }

    bool Checkers::simpleMove(int& row, int& col, int dir)
    {
    	if (dir==0)
    	{
    		col--;
    	}
    	else
    	{
    		col++;
    	}
    	row++;
    	if (col<0||col==BoardSize||row==BoardSize)
    	{
    		return false;
    	}
    	return board[row][col]!='Y';
    }

    char*  pieces[]=
    {
    	//"2,1", "0,3", "4,3", "5,6", "4,2"
    	//"6,6", "5,5", "3,5", "2,6"
    	"2,4", "3,4", "4,4", "5,4", "2,6", "3,6", "4,6", "5,6"
    };

    void createString(StringVector& strVect)
    {
    	for (int i=0; i<8; i++)
    	{
    		strVect.push_back(string(pieces[i]));
    	}
    }

    int main()
    {
    	StringVector strVect;
    	Checkers checker;
    	int result;

    	createString(strVect);
    	result=checker.compute(string("4,1"), strVect);
    	printf("result=%d\n", result);

    	return 0;
    }

    5. ArgParser (problem 500)

    /*

    Problem Statement

    THIS PROBLEM WAS TAKEN FROM THE SEMIFINALS OF THE TOPCODER INVITATIONAL
    TOURNAMENT

    PROBLEM STATEMENT
    One of the problems that TopCoder has run into is how to parse a String[] from
    the command line. To do this, we've adopted the following convention for a
    String representation of a String[] (quotes are used for clarity only):
    "{<element1>, <element2>, ... , <elementN>}", where the input String begins
    with a beginning curly brace,  each String element in the input String (except
    the last one) is followed by a comma and a space, and the last one is followed
    by an end curly brace. However, there are a couple of tricks:

    * each individual String element may contain commas or curly braces (or both).
    In each case, an escape character ('\') will precede commas and curly braces
    that are actually *within* the String element.
    * a backslash ('\') does not necessarily mean the following character needs to
    be escaped. If it does not precede a comma or curly brace, it is to be
    considered part of the String element.
    * an empty String element is a valid parameter, and is indicated by no
    character preceding a delimiting comma and a space (see examples below).
    * "{}" returns an array with an empty String element {""}.

    Additionally, there are certain cases where the input String is invalid that
    you will need to catch. Those situations are:
    * if the input string doesn't begin with an open curly brace and end with a
    closed curly brace
    * if any curly brace inside the opening and closing curly braces are not
    escaped.
    * if any comma that serves as a delimiter fails to have a space after it

    In cases such as these, return a String[] consisting of exactly one element:
    "INVALID"

    Your task is to create a class ArgParser that includes a method parse. This
    method will take a String representation of a String[], and return the
    corresponding String[].

    DEFINITION
    Class Name:  ArgParser
    Method Name:  parse
    Parameters:  String
    Returns:  String[]
    Method signature (be sure your method is public):  String[] parse(String input);

    TopCoder will ensure that the input string will only contain characters A-Z,
    a-z, 0-9, '{', '}', spaces (' '), commas (',') and backslashes ('\').  The
    String should have a length between 0 and 50, inclusive.

    EXAMPLES
    "{a, b, c}" -> {"a", "b", "c"} (3 items)
    "{a\,b, c}" -> {"a,b", "c"} (2 items)
    "{, , a, }" -> {"", "", "a", ""} (4 items)
    "{\\, \,\, }" -> {"\, ,, "} (1 item)
    "{\ , \,, }" -> {"\ ", ",", ""} (3 items)
    "{}" -> {""} (1 item)
    Definition

    Class:
    ArgParser
    Method:
    parse
    Parameters:
    string
    Returns:
    vector <string>
    Method signature:
    vector <string> parse(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 <stdio.h>
    #include <vector>

    using namespace std;

    #define StartState		0
    #define EndState		1
    #define InsideString	2
    #define EscapeState		4
    #define Delimiter		5
    #define InvalidState	6
    //#define EscapeEnd		7

    typedef vector<string> StringVector;

    class ArgParser
    {
    private:
    	StringVector result;
    	string current;
    	int transferRule(int state, char ch);

    public:
    StringVector parse(string param);
    };

    StringVector ArgParser::parse(string param)
    {
    	int state=StartState;
    	char ch;
    	for (int i=0; i<param.size(); i++)
    	{
    		ch=param[i];
    		state=transferRule(state, ch);

    		if (state==InvalidState)
    		{
    			current.assign("INVALID");
    			result.clear();
    			result.push_back(current);
    			return result;
    		}
    	}
    	if (state!=EndState)
    	{
    		current.assign("INVALID");
    		result.clear();
    		result.push_back(current);
    		return result;
    	}
    	return result;
    }

    int ArgParser::transferRule(int state, char ch)
    {
    	switch (state)
    	{
    	case StartState:
    		switch (ch)
    		{
    		case '{':
    			result.clear();
    			current.assign("");
    			return InsideString;
    		default:
    			return InvalidState;
    		}
    		break;
    	case InsideString:
    		switch (ch)
    		{
    		case '}':
    			result.push_back(current);
    			current.assign("");
    			return EndState;
    		case '\\':
    			return EscapeState;
    		case ',':
    			result.push_back(current);
    			current.assign("");
    			return Delimiter;
    		default:
    			current.append(1, ch);
    			return InsideString;
    		}
    		break;
    	case EscapeState:
    		switch (ch)
    		{
    		case ',':
    		case '{':
    		case '}':
    			current.append(1, ch);
    			return InsideString;
    			break;
    		case '\\':
    			current.append(1, '\\');
    			return EscapeState;
    		default:
    			current.append(1, '\\');
    			current.append(1, ch);
    			return InsideString;
    			break;
    		}
    		break;

    	case Delimiter:
    		switch (ch)
    		{
    		case ' ':
    			return InsideString;
    		default:
    			return InvalidState;
    		}
    		break;
    	case EndState:
    		return InvalidState;
    		break;
    	}
    	return InvalidState;
    }

    void display(StringVector& strVect)
    {
    	for (int i=0; i<strVect.size(); i++)
    	{
    		printf("%s;\n", strVect[i].c_str());
    	}
    }

    int main()
    {
    	StringVector strVect;
    	ArgParser parser;
    	strVect=parser.parse(string("{}"));
    	display(strVect);

    	return 0;
    }

    6. LongCalc (problem 1000)

    /*

    Problem Statement

    THIS PROBLEM WAS TAKEN FROM THE SEMIFINALS OF THE TOPCODER INVITATIONAL
    TOURNAMENT

    PROBLEM STATEMENT
    Create a class LongCalc that will perform arithmetic operations on two whole
    numbers, represented by Strings. The operation to be performed is indicated by
    op, which will be 1 for addition, 2 for subtraction, 3 for multiplication, and
    4 for integer division. The value returned from this operation will be a
    numeric value held in a String (which may begin with a negative sign if
    necessary).

    DEFINITION
    Class Name: LongCalc
    Method Name: process
    Parameters: String, String, int
    Returns: String
    Method signature (be sure your method is public): String process(String a,
    String b, int op);

    The operation that will be performed is <a op b>.

    TopCoder will ensure the validity of the inputs.  Inputs are valid if all of
    the following criteria are met:
    - Both a and b will consist of only digits, and that the first digit of each
    number is greater than 0.
    - Both a and b will have length between 1 and 50, inclusive.
    - op will be either 1, 2, 3, or 4

    JAVA NOTE
    java.math.* will not be allowed

    EXAMPLES
    process("100", "50", 1) -> "150"
    process("100000000000000000000000000000000",
    "400000000000000000000000000000000", 1) -> "500000000000000000000000000000000"
    process("3", "4", 2) -> "-1"
    process("29", "465", 3) -> "13485"
    process("15", "2", 4) -> "7"
    Definition

    Class:
    LongCalc
    Method:
    process
    Parameters:
    string, string, int
    Returns:
    string
    Method signature:
    string process(string param0, string param1, 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 <stdio.h>
    #include <stdlib.h>
    #include <string>
    #include <vector>

    using namespace std;

    class LongCalc
    {
    private:
    	char* buffer;
    	char sign;
    	int length;
    	string ret;
    	void init(string& first, string& second, int op);
    	void addition(const char* str1, const char* str2, int length1, int length2);
    	void subtraction(const char* str1, const char* str2, int length1, int length2);
    	void multiply(const char* str1, const char* str2, int length1, int length2);
    	void divide(const char* str1, const char* str2, int length1, int length2);
    	int compare(const char* str1, const char* str2, int length1, int length2);
    	void doSubtraction(char* str1, char* str2, int length1, int length2);
    public:
    	string process(string first, string second, int op);
    };

    void LongCalc::doSubtraction(char* str1, char* str2, int length1, int length2)
    {
    	char carryon=0;
    	int i=length1-1, j=length2-1;
    	while (i>=0&&j>=0)
    	{
    		if (str1[i]>=str2[j]+carryon)
    		{
    			str1[i]-=str2[j]+carryon;
    			carryon=0;
    		}
    		else
    		{
    			str1[i]=10+str1[i]-str2[j]-carryon;
    			carryon=1;
    		}
    		i--;
    		j--;

    	}
    	if (carryon>0)
    	{
    		str1[i]--;
    	}
    }

    int LongCalc::compare(const char* str1, const char* str2, int length1, int length2)
    {
    	if (length1!=length2)
    	{
    		return length1-length2;
    	}
    	for (int i=0; i<length1; i++)
    	{
    		if (str1[i]!=str2[i])
    		{
    			return str1[i]-str2[i];
    		}
    	}
    	return 0;
    }

    void LongCalc::divide(const char* str1, const char* str2, int length1, int length2)
    {
    	char* divident, * divisor, *quotient;
    	int i, result, counter, offset;
    	int dividentLength, quotientLength;
    	//sign+NULL
    	divident=new char[length1];
    	divisor=new char[length2];

    	for (i=0; i<length1; i++)
    	{
    		divident[i]=str1[i]-'0';
    	}
    	for (i=0; i<length2; i++)
    	{
    		divisor[i]=str2[i]-'0';
    	}

    	result=compare(divident, divisor, length2, length2);
    	if (result>=0)
    	{
    		dividentLength=length2;
    		quotientLength=length1-length2+1;
    	}
    	else
    	{
    		dividentLength=length2+1;
    		quotientLength=length1-length2;
    	}
    	if (sign=='-')
    	{
    		offset=1;
    	}
    	else
    	{
    		offset=0;
    	}

    	//plus NULL
    	quotient=new char[quotientLength+offset+1];
    	memset(quotient, 0, quotientLength+offset+1);

    	for (i=0; i<quotientLength; i++)
    	{
    		counter=0;

    		while (true)
    		{
    			if (divident[i]!=0)
    			{
    				result=compare(divident+i, divisor, dividentLength, length2);
    			}
    			else
    			{
    				result=compare(divident+i+1, divisor, length2, length2);
    			}

    			if (result>=0)
    			{
    				doSubtraction(divident+i, divisor, dividentLength, length2);
    				counter++;
    			}
    			else
    			{
    				break;
    			}
    		}

    		quotient[i+offset]=counter;
    	}

    	//keep last NULL
    	for (i=quotientLength+offset-1; i>=offset; i--)
    	{
    		quotient[i]+='0';
    	}

    	if (sign=='-')
    	{
    		quotient[0]=sign;
    	}
    	ret.assign(quotient);
    	delete[] divisor;
    	delete[]divident;
    	delete[]quotient;
    }

    void LongCalc::addition(const char* str1, const char* str2, int length1, int length2)
    {
    	char first, second, sum, carryon=0;
    	int length=length1>length2?length1:length2;
    	int i, j, k;

    	//carryon, sign, NULL
    	length+=1+1+1;
    	buffer=new char[length];
    	buffer[length-1]='\0';
    	i=length1-1;
    	j=length2-1;

    	k=length-2;
    	carryon=0;

    	while (i>=0||j>=0)
    	{
    		if (i<0)
    		{
    			first=0;
    		}
    		else
    		{
    			first=str1[i]-'0';
    		}
    		if (j<0)
    		{
    			second=0;
    		}
    		else
    		{
    			second=str2[j]-'0';
    		}
    		sum=first+second+carryon;
    		if (sum>=10)
    		{
    			buffer[k]=sum-10+'0';
    			carryon=1;
    		}
    		else
    		{
    			buffer[k]=sum+'0';
    			carryon=0;
    		}
    		i--;
    		j--;
    		k--;
    	}
    	if (carryon!=0)
    	{
    		buffer[k]=carryon+'0';
    		k--;
    	}
    	if (sign=='-')
    	{
    		buffer[k]=sign;
    		k--;
    	}
    	ret.assign(buffer+k+1);
    	delete[]buffer;
    }

    void LongCalc::subtraction(const char* str1, const char* str2, int length1, int length2)
    {
    	char first, second, carryon=0;
    	int length=length1>length2?length1:length2;
    	int i, j, k;

    	//carryon, sign, NULL
    	length+=1+1+1;
    	buffer=new char[length];
    	buffer[length-1]='\0';
    	i=length1-1;
    	j=length2-1;

    	k=length-2;
    	carryon=0;

    	while (i>=0||j>=0)
    	{
    		if (i<0)
    		{
    			first=0;
    		}
    		else
    		{
    			first=str1[i]-'0';
    		}
    		if (j<0)
    		{
    			second=0;
    		}
    		else
    		{
    			second=str2[j]-'0';
    		}

    		if (first>=second+carryon)
    		{
    			buffer[k]=first-second-carryon+'0';
    			carryon=0;
    		}
    		else
    		{
    			buffer[k]=10+first-second-carryon+'0';
    			carryon=1;
    		}
    		i--;
    		j--;
    		k--;
    	}

    	if (sign=='-')
    	{
    		while (buffer[k+1]=='0')
    		{
    			k++;
    		}
    		buffer[k]=sign;
    	}
    	else
    	{
    		k++;
    	}
    	ret.assign(buffer+k);
    	delete[]buffer;
    }

    void LongCalc::multiply(const char* str1, const char* str2, int length1, int length2)
    {
    	//sign+NULL+carryon
    	int length=length1+length2+1+1+1;
    	char first, second, subVal, carryon;
    	buffer=new char[length];
    	int i, j, k;

    	memset(buffer, 0, length);
    	carryon=0;

    	for (i=0; i<length1; i++)
    	{
    		carryon=0;
    		for (j=0; j<length2; j++)
    		{
    			first=str1[length1-1-i]-'0';
    			second=str2[length2-1-j]-'0';
    			//excluding NULL
    			k=length-2-i-j;
    			subVal=first*second+carryon+buffer[k];
    			carryon=subVal/10;
    			buffer[k]=subVal%10;
    		}
    		buffer[k-1]=carryon;
    	}
    	if (carryon!=0)
    	{
    		k--;
    		//buffer[k]=carryon;
    	}
    	for (i=length-2; i>=k; i--)
    	{
    		buffer[i]+='0';
    	}

    	if (sign=='-')
    	{
    		k--;
    		buffer[k]=sign;
    	}

    	ret.assign(buffer+k);
    	delete[] buffer;
    }

    void LongCalc::init(string& first, string& second, int op)
    {
    	int result;
    	switch (op)
    	{
    	case 1:
    		if (first[0]=='-'&&second[0]=='-')
    		{
    			sign='-';
    			addition(first.c_str()+1, second.c_str()+1, first.size()-1, second.size()-1);
    		}
    		else
    		{
    			if (first[0]!='-'&&second[0]!='-')
    			{
    				sign='+';
    				addition(first.c_str(), second.c_str(), first.size(), second.size());
    			}
    			else
    			{
    				if (first[0]=='+')
    				{
    					sign='+';
    					subtraction(second.c_str(), first.c_str()+1, second.size(), first.size()-1);
    				}
    				else
    				{
    					sign='+';
    					subtraction(first.c_str(), second.c_str()+1, first.size(), second.size());
    				}
    			}
    		}
    		break;
    	case 2:
    		if (first[0]=='-'&&second[0]=='-')
    		{
    			result=compare(first.c_str()+1, second.c_str()+1, first.size()-1, second.size()-1);
    			if (result==0)
    			{
    				ret.assign("0");
    				return;
    			}
    			if (result>0)
    			{
    				sign='-';
    				subtraction(first.c_str()+1, second.c_str()+1, first.size()-1, second.size()-1);
    			}
    			else
    			{
    				sign='+';
    				subtraction(second.c_str()+1, first.c_str()+1, second.size()-1, first.size()-1);
    			}
    		}
    		else
    		{

    			if (first[0]!='-'&&second[0]!='-')
    			{
    				result=compare(first.c_str(), second.c_str(), first.size(), second.size());
    				if (result==0)
    				{
    					ret.assign("0");
    					return;
    				}
    				if (result>0)
    				{
    					sign='+';
    					subtraction(first.c_str(), second.c_str(), first.size(), second.size());
    				}
    				else
    				{
    					sign='-';
    					subtraction(second.c_str(), first.c_str(), second.size(), first.size());
    				}
    			}
    			else
    			{
    				if (first[0]=='-')
    				{
    					sign='-';
    					addition(second.c_str(), first.c_str()+1, second.size(), first.size()-1);
    				}
    				else
    				{
    					sign='+';
    					addition(first.c_str(), second.c_str()+1, first.size(), second.size()-1);
    				}
    			}
    		}
    		break;
    	case 3://*
    		if (first[0]=='-'&&second[0]=='-')
    		{
    			sign='+';
    			multiply(first.c_str()+1, second.c_str()+1, first.size()-1,second.size()-1);
    		}
    		else
    		{
    			if (first[0]!='-'&&second[0]!='-')
    			{
    				sign='+';
    				multiply(first.c_str(), second.c_str(), first.size(), second.size());
    			}
    			else
    			{
    				if (first[0]=='-')
    				{
    					sign='-';
    					multiply(first.c_str()+1, second.c_str(), first.size()-1, second.size());
    				}
    				else
    				{
    					sign='-';
    					multiply(first.c_str(), second.c_str()+1, first.size(), second.size()-1);
    				}
    			}
    		}
    		break;
    	case 4:
    		if (first[0]=='-'&&second[0]=='-')
    		{
    			sign='+';
    			divide(first.c_str()+1, second.c_str()+1, first.size()-1,  second.size()-1);
    		}
    		else
    		{
    			if (first[0]!='-'&&second[0]!='-')
    			{
    				sign='+';
    				divide(first.c_str(), second.c_str(), first.size(), second.size());
    			}
    			else
    			{
    				if (first[0]=='-')
    				{
    					sign='-';
    					divide(first.c_str()+1, second.c_str(), first.size()-1, second.size());
    				}
    				else
    				{
    					sign='-';
    					divide(first.c_str(), second.c_str()+1, first.size(), second.size()-1);
    				}
    			}
    		}
    		break;
    	}
    }

    string LongCalc::process(string first, string second, int op)
    {
    	int result;
    	switch (op)
    	{
    	case 1:
    		sign='+';
    		addition(first.c_str(), second.c_str(), first.size(), second.size());
    		break;
    	case 2:
    		result=compare(first.c_str(), second.c_str(), first.size(), second.size());
    		if (result==0)
    		{
    			ret.assign("0");
    			return ret;
    		}
    		if (result>0)
    		{
    			sign='+';
    			subtraction(first.c_str(), second.c_str(), first.size(), second.size());
    		}
    		else
    		{
    			sign='-';
    			subtraction(second.c_str(), first.c_str(), second.size(), first.size());
    		}
    		break;
    	case 3://*

    		sign='+';
    		multiply(first.c_str(), second.c_str(), first.size(), second.size());
    		break;
    	case 4:
    		result=compare(first.c_str(), second.c_str(), first.size(), second.size());
    		if (result==0)
    		{
    			ret.assign("1");
    			return ret;
    		}
    		if (result<0)
    		{
    			ret.assign("0");
    			return ret;
    		}
    		sign='+';
    		divide(first.c_str(), second.c_str(), first.size(), second.size());
    		break;
    	}
    	return ret;
    }

    int main()
    {
    	LongCalc calc;

    	string str1="100000000000000000", str2="100000000000000000000";
    	string result;
    	result=calc.process(str1, str2, 2);
    	printf("result=%s\n", result.c_str());
    	return 0;
    }