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



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