A. First Edition

These are problems from topCoder practice room and for the "1000" problem sometimes it is not that kind of hard as the problem varies so much depending 

on people.

B.The problem

See below.

D.The major functions

E.Further improvement

F.File listing

1. chooser (problem 250)

Problem Statement
    
A permutation p[0], p[1], ..., p[n-1] is a sequence containing each number from 0 to n-1 exactly once. The result of applying permutation p to an array a of length n is an array b of length n, where b[p[i]] = a[i] (0-based indices). Given an array a, find a permutation which has the effect of sorting the elements of a in non-descending order, i.e., an order where each element is greater than or equal to the previous one. If there are several suitable permutations return the lexicographically smallest one. The permutation p[0], p[1], ..., p[n-1] is considered lexicographically smaller than the permutation q[0], q[1], ..., q[n-1] if there is an index i such that p[i] < q[i] and the equation p[j] = q[j] holds for all j < i.
Definition
    
Class:
SortingWithPermutation
Method:
getPermutation
Parameters:
vector <int>
Returns:
vector <int>
Method signature:
vector <int> getPermutation(vector <int> a)
(be sure your method is public)
    

Constraints
-
a will contain between 1 and 50 elements, inclusive.
-
Each element of a will be between 1 and 1000, inclusive.
Examples
0)

    
{2, 3, 1}
Returns: {1, 2, 0 }
The element that is originally at position 0 goes to position 1. The elements originally at positions 1 and 2 go to positions 2 and 0, respectively.
1)

    
{2, 1, 3, 1}
Returns: {2, 0, 3, 1 }
There are two suitable permutations - {2, 0, 3, 1} and {2, 1, 3, 0}. The first one is lexicographically smaller.
2)

    
{4, 1, 6, 1, 3, 6, 1, 4}
Returns: {4, 0, 6, 1, 3, 7, 2, 5 }

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 <set>
#include <vector>

using namespace std;

struct Node
{
	int value;
	int index;
};

struct SetIntComp
{
	bool operator()(const Node& left, const Node& right) const
	{
		if (left.value != right.value)
		{
			return left.value < right.value;
		}
		else
		{
			return left.index < right.index;
		}
	}
};
typedef set<Node, SetIntComp> MySet;
class SortingWithPermutation
{
public:
	vector<int> getPermutation(vector<int> a)
	{
		MySet m;
		Node node;		
		vector<int> v(a.size());
		int i;
		for ( i = 0; i < a.size(); i ++)
		{
			node.value = a[i];
			node.index = i;
			m.insert(node);
		}
		i = 0;
		for ( MySet::iterator it = m.begin(); it != m.end(); it ++, i ++)
		{			
			v[it->index] = i;
		}
		return v;
	}
};			
			
		

/*

Problem Statement
You work in a company that produces measuring devices. The software for each device is stored in reprogrammable memory. To program a device, you must connect it to a personal computer and transmit data to the device's reprogrammable memory through a serial interface. Your task is to make this process as efficient as possible.
You are given two vector <int>s offset and size. Each corresponding pair of elements in offset and size describes a piece of data that must be transmitted to the device. The i-th piece of data consists of size[i] consecutive bytes that must be written starting at the address in offset[i]. To successfully program a device, you must write every piece of the given data. Memory addresses that are not referenced in this data are not important - so you can write anything to those addresses, or write nothing at all to them.
Data is transmitted from the computer to the device through packets. Each packet can contain a maximum of maxData bytes of consecutive data that will be written to a specified memory address. Return the minimum possible total number of packets required to transmit all of the given data to the device.
Definition
????
Class:
ProgrammingDevice
Method:
minPackets
Parameters:
vector <int>, vector <int>, int
Returns:
int
Method signature:
int minPackets(vector <int> offset, vector <int> size, int maxData)
(be sure your method is public)
????

Notes
-
Assume that the reprogrammable memory of the measuring device is infinitely large.
Constraints
-
offset will contain between 1 and 50 elements, inclusive.
-
offset and size will contain the same number of elements.
-
Each element of offset will be between 0 and 1,000,000,000, inclusive.
-
Each element of size will be between 1 and 1,000,000,000, inclusive.
-
None of the pieces of data described by offset and size will overlap.
-
maxData will be between 1 and 2,000,000,000, inclusive.
Examples
0)

????
{0, 10, 20, 30}
{8, 5, 3, 11}
6
Returns: 6
Send 15 bytes starting from offset 0 in 3 packets. Only 13 of those 15 bytes are meaningful. There are 2 dummy bytes starting from offset 8. Then, send 3 bytes starting from offset 20 in 1 packet. Finally, send 11 bytes starting from offset 30 in 2 packets. A total of 6 packets are sent.
1)

????
{0, 10, 20, 30}
{8, 2, 3, 11}
6
Returns: 5
Send 12 bytes starting from offset 0 in 2 packets. Then, send 3 bytes starting from offset 20 in 1 packet. Finally, send 11 bytes starting from offset 30 in 2 packets. A total of 5 packets are sent.
2)

????
{15, 95}
{1, 20}
100
Returns: 1

3)

????
{77, 7777, 777}
{700, 70000, 7000}
1
Returns: 77700

4)

????
{0,1000000000}
{1000000000,1000000000}
2000000000
Returns: 1

5)

????
{0,1000000000}
{1000000000,1000000000}
1
Returns: 2000000000

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


#include <vector>
#include <map>

using namespace std;

class ProgrammingDevice
{
public:
	int minPackets(vector<int> offset, vector<int> size, int maxData)
	{
		map<int, int> m;
		vector<int> sortedOffset, sortedSize;
		int i, counter = 0, n;
		unsigned int theStart, theSize;
		if (maxData == 1)
		{
			for (i = 0; i < size.size(); i ++)
			{
				counter += size[i];
			}
			return counter;
		}
		
		for (i = 0; i < offset.size(); i ++)
		{
			m[offset[i]] = size[i];
		}
		i = 0;
		for (map<int, int>::const_iterator it = m.begin(); it != m.end(); it ++, i ++)
		{
			sortedOffset.push_back(it->first);
			sortedSize.push_back(it->second);
		}
		theStart = sortedOffset[0];
		theSize = sortedSize[0];
		for (i = 0; i < sortedOffset.size(); i ++)
		{
			if (theStart <= sortedOffset[i])
			{
				theStart = sortedOffset[i];
				theSize = sortedSize[i];
			}
			else
			{
				theSize = sortedSize[i] - (theStart - sortedOffset[i]);
			}
			n = (theSize + maxData - 1)/maxData;
			counter += n;
			theStart += n * maxData;
		}
		return counter;
	}
};
				
			
			
		
			
int main()
{
	vector<int> offset, size;
	ProgrammingDevice p;
	int counter = 0;
	offset.push_back(0);
	offset.push_back(1000000000);
	size.push_back(1000000000);
	size.push_back(1000000000);

	counter = p.minPackets(offset, size, 2000000000);


	return 0;
}

/*

Problem Statement
????
An electronic billboard is supposed to display large letters by using several lightbulbs per letter. Given a message, and how each enlarged letter looks as a 5x5 arrangement of lightbulbs, return the enlarged message.
The enlarged representation of the letters will be in a vector <string> with each element formatted as follows (quotes added for clarity):
"<letter>:*****-*****-*****-*****-*****"
Where <letter> is a single uppercase letter [A-Z], and each * is either the character '#' (representing a lit lightbulb) or a period ('.') (representing an unlit lightbulb). Each group of 5 (delimited by a dash, '-') represents a row in the 5x5 representation of the letter. So, "T:#####-..#..-..#..-..#..-..#.." means that the 5x5 representation of 'T' is:
"#####"
"..#.."
"..#.."
"..#.."
"..#.."
Return the enlarged message as a 5-element vector <string>, with each element representing one row of lightbulbs (where element 0 is the top row). Leave 1 (one) column of periods ('.') between each adjacent pair of letters in the enlarged message.
Definition
????
Class:
Billboard
Method:
enlarge
Parameters:
string, vector <string>
Returns:
vector <string>
Method signature:
vector <string> enlarge(string message, vector <string> letters)
(be sure your method is public)
????

Constraints
-
message will contain between 1 and 10 characters, inclusive.
-
each character of message will be an uppercase letter [A-Z].
-
letters will contain between 1 and 10 elements, inclusive.
-
each element of letters will be exactly 31 characters in length.
-
each element of letters will be formatted as (quotes added for clarity): "<letter>:*****-*****-*****-*****-*****", where <letter> is a single uppercase letter [A-Z] (inclusive) representing the letter being enlarged, and each * is either the character '#' or a period.
-
every letter appearing in message will have an enlarged representation in letters.
-
each letter represented in letters will be unique.
Examples
0)

????
"TOPCODER"
{"T:#####-..#..-..#..-..#..-..#.."
,"O:#####-#...#-#...#-#...#-#####"
,"P:####.-#...#-####.-#....-#...."
,"C:.####-#....-#....-#....-.####"
,"D:####.-#...#-#...#-#...#-####."
,"E:#####-#....-####.-#....-#####"
,"R:####.-#...#-####.-#.#..-#..##"}
Returns: 
{ "#####.#####.####...####.#####.####..#####.####.",
  "..#...#...#.#...#.#.....#...#.#...#.#.....#...#",
  "..#...#...#.####..#.....#...#.#...#.####..####.",
  "..#...#...#.#.....#.....#...#.#...#.#.....#.#..",
  "..#...#####.#......####.#####.####..#####.#..##" }

1)

????
"DOK"
{"D:####.-#...#-#...#-#...#-####."
,"O:#####-#...#-#...#-#...#-#####"
,"K:#...#-#..#.-###..-#..#.-#...#"}
Returns: 
{ "####..#####.#...#",
  "#...#.#...#.#..#.",
  "#...#.#...#.###..",
  "#...#.#...#.#..#.",
  "####..#####.#...#" }

2)

????
"RANDOMNESS"
{"S:##.##-#####-#.#.#-#.#.#-####."
,"N:#####-#####-#####-#####-#####"
,"R:#####-#####-##.##-#####-#####"
,"A:.....-.....-.....-.....-....."
,"D:#.#.#-.#.#.-#.#.#-.#.#.-#.#.#"
,"O:#####-#...#-#.#.#-#...#-#####"
,"E:#....-.#...-..#..-...#.-....#"
,"M:#....-.....-.....-.....-....."
,"X:#...#-.#.#.-..#..-.#.#.-#...#"}
Returns: 
{ "#####.......#####.#.#.#.#####.#.....#####.#.....##.##.##.##",
  "#####.......#####..#.#..#...#.......#####..#....#####.#####",
  "##.##.......#####.#.#.#.#.#.#.......#####...#...#.#.#.#.#.#",
  "#####.......#####..#.#..#...#.......#####....#..#.#.#.#.#.#",
  "#####.......#####.#.#.#.#####.......#####.....#.####..####." }
Note that the letter X is defined but never used.
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.
*/


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

using namespace std;


class Billboard
{
public:
	vector<string> enlarge(string message, vector<string> letters)
	{
		vector<string> result;
		string str[5];
		char* ptr;
		int i, j, index;
		char ch = '.';
		for ( i = 0; i < 5; i ++)
		{
			result.push_back(str[i]);
		}
				
		for (i = 0; i < message.size(); i ++)
		{
			for (j = 0; j < letters.size(); j ++)
			{
				if (message[i] == letters[j][0])
				{
					index = j;
					break;
				}
			}
			for (j = 0; j <  5; j ++)
			{
				ptr =&(letters[index][j * 6 + 2]);
				result[j].append(ptr, 5);
				if (i != message.size() - 1)
				{
					result[j].append(1, ch);
				}
			}
		}
		return result;
	}
};
				
				
			
	
			
	
int main()
{
	Billboard b;
	string str = "DOK";
	vector<string> v, result;
	string s;
	s.assign("D:####.-#...#-#...#-#...#-####.", strlen("D:####.-#...#-#...#-#...#-####."));
	v.push_back(s);

	s.assign("O:#####-#...#-#...#-#...#-#####", strlen("O:#####-#...#-#...#-#...#-#####"));

	v.push_back(s);

	s.assign("K:#...#-#..#.-###..-#..#.-#...#", strlen("K:#...#-#..#.-###..-#..#.-#...#"));

	v.push_back(s);

	result = b.enlarge(str, v);
	for (int i = 0; i < result.size(); i ++)
	{
		printf("%s\n", result[i].c_str());
	}

	return 0;
}

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

Problem Statement
    
We call two numbers friendly if they have the same digits, ignoring order or repetition. For example 122213 and 312 are friendly while 145 and 2544411 are not. A sequence is friendly if it contains at least two numbers, and all possible pairs of numbers within it are friendly. Two contiguous subsequences are different if they have a different start index, end index or both.
If we are given the sequence 112, 12, 21, 354, 534345, 345, 2221 then the friendly contiguous subsequences are: {112, 12}, {112, 12, 21}, {12, 21}, {354, 534345}, {354, 534345, 345} and {534345, 345}. {112, 12, 21, 354} is not a friendly contiguous subsequence because 112 and 354 are not friendly numbers and {112, 12, 21, 2221} is not a friendly contignuous subsequence because the elements of the sequence aren't in consecutive positions in the original sequence.
Given a vector <int> array, you must return number of different friendly contignuous subsequences of array.
Definition
    
Class:
FriendlySequences
Method:
count
Parameters:
vector <int>
Returns:
int
Method signature:
int count(vector <int> array)
(be sure your method is public)
    

Constraints
-
array will have between 0 and 50 elements, inclusive.
-
Each element of array will be between 0 and 2000000000, inclusive.
Examples
0)

    
{112, 12, 21, 354, 534345, 345, 2221}
Returns: 6
The example in the problem.
1)

    
{10, 1100, 10101, 111, 1111, 11111, 11, 1, 111}
Returns: 18

2)

    
{0, 0, 0, 0}
Returns: 6
We have a total of 6 possible different pairs of start and end indices for friendly subsequences.
3)

    
{123456890, 213456890, 198654320} 
Returns: 3

4)

    
{9}
Returns: 0

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

#include <vector>

using namespace std;


class FriendlySequences
{
private:
	int isFriendly(int left, int right)
	{
		char strLeft[11], strRight[11];
		int lenLeft, lenRight, i, j;
		bool bFound;
		sprintf(strLeft, "%d", left);
		sprintf(strRight, "%d", right);
		lenLeft = strlen(strLeft);
		lenRight = strlen(strRight);
		for (i = 0; i < lenLeft; i ++)
		{
			bFound = false;
			for (j = 0; j < lenRight; j ++)
			{
				if (strLeft[i] == strRight[j])
				{
					bFound = true;
					break;
				}
			}
			if (!bFound)
			{
				return false;
			}
		}
		return true;		
	}
	
	int calculate(int n)
	{
		if (n > 0)
		{
			return (n - 1) * n / 2;
		}
		else
		{
			return 0;
		}
	}

public:
	int count(vector <int> array)
	{
		int nStart, nEnd, i, counter = 0;
		nStart = nEnd = 0;
		bool bSame = false;
		for (i = 0; i < array.size(); i ++)
		{
			if (nEnd != i)
			{
				bSame = isFriendly(array[nEnd], array[i]);
			}
			if (!bSame)
			{
				counter += calculate(nEnd - nStart + 1);
				nStart = nEnd = i;
			}
			else
			{
				nEnd ++;
			}
		}
		counter += calculate(nEnd - nStart + 1);
		return counter;
	}
};

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

Problem Statement
    
An essential part of circuit design and general system optimization is critical path analysis. On a chip, the critical path represents the longest path any signal would have to travel during execution. In this problem we will be analyzing chip designs to determine their critical path length. The chips in this problem will not contain any cycles, i.e. there exists no path from one component of a chip back to itself.  Given a vector <string> connects representing the wiring scheme, and a vector <string> costs representing the cost of each connection, your method will return the size of the most costly path between any 2 components on the chip. In other words, you are to find the longest path in a directed, acyclic graph. Element j of connects will list the components of the chip that can be reached directly from the jth component (0-based). Element j of costs will list the costs of each connection mentioned in the jth element of connects. As mentioned above, the chip will not contain any cyclic paths. For example:
connects = {"1 2",
            "2",
            ""}
costs    = {"5 3",
            "7",
            ""}
In this example, component 0 connects to components 1 and 2 with costs 5 and 3 respectively. Component 1 connects to component 2 with a cost of 7. All connections mentioned are directed. This means a connection from component i to component j does not imply a connection from component j to component i. Since we are looking for the longest path between any 2 components, your method would return 12.
Definition
    
Class:
Circuits
Method:
howLong
Parameters:
vector <string>, vector <string>
Returns:
int
Method signature:
int howLong(vector <string> connects, vector <string> costs)
(be sure your method is public)
    

Constraints
-
connects must contain between 2 and 50 elements inclusive
-
connects must contain the same number of elements as costs
-
Each element of connects must contain between 0 and 50 characters inclusive
-
Each element of costs must contain between 0 and 50 characters inclusive
-
Element i of connects must contain the same number of integers as element i of costs
-
Each integer in each element of connects must be between 0 and the size of connects-1 inclusive
-
Each integer in each element of costs must be between 1 and 1000 inclusive
-
Each element of connects may not contain repeated integers
-
Each element of connects must be a single space delimited list of integers, each of which has no extra leading zeros. There will be no leading or trailing whitespace.
-
Each element of costs must be a single space delimited list of integers, each of which has no extra leading zeros. There will be no leading or trailing whitespace.
-
The circuit may not contain any cycles
-
There will be at least 1 connection.
Examples
0)

    
{"1 2",
 "2",
 ""}
{"5 3",
 "7",
 ""}
Returns: 12
From above
1)

    
{"1 2 3 4 5","2 3 4 5","3 4 5","4 5","5",""}
{"2 2 2 2 2","2 2 2 2","2 2 2","2 2","2",""}
Returns: 10
The longest path goes from 0-1-2-3-4-5 for a cost of 10.
2)

    
{"1","2","3","","5","6","7",""}
{"2","2","2","","3","3","3",""}
Returns: 9
The 0-1-2-3 path costs 6 whereas the 4-5-6-7 path costs 9
3)

    
{"","2 3 5","4 5","5 6","7","7 8","8 9","10",
 "10 11 12","11","12","12",""}
{"","3 2 9","2 4","6 9","3","1 2","1 2","5",
 "5 6 9","2","5","3",""}
Returns: 22

4)

    
{"","2 3","3 4 5","4 6","5 6","7","5 7",""}
{"","30 50","19 6 40","12 10","35 23","8","11 20",""}
Returns: 105

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

#include <vector>
#include <string>

using namespace std;

class Circuits
{
private:
	vector<int> string2vector(string& input)
	{
		char buffer[32];
		vector<int> result;
		int i = 0, number;
		const char* ptr = input.c_str();
		if (ptr == NULL || strlen(ptr) == 0)
		{
			return result;
		}
		

		while (true)
		{			
			if (*ptr == ' ' || *ptr == '\0')
			{
				buffer[i] = '\0';
				number = atoi(buffer);
				result.push_back(number);				
				i = 0;
			}
			else
			{
				buffer[i] = *ptr;
				i ++;
			}
			if (*ptr == '\0')
			{
				break;
			}
			ptr ++;
		}
		return result;
	}
				

	// let's use dynamic programming instead of recursion, NO! it is too complicated now...		
		

	int doHowLong(vector<vector<int> > connects, vector<vector<int> > costs, int start)
	{			
		int longest = 0;
		int i, length;
		for (i = 0; i < connects[start].size(); i ++)
		{
			length = costs[start][i] + doHowLong(connects, costs, connects[start][i]);
			if (length > longest)
			{
				longest = length;
			}
		}
		return longest;
	}	
public:
	int howLong(vector <string> connects, vector <string> costs)
	{
		vector<vector<int> > connect, cost;
		vector<int> node;
		int longest = 0, length;
		int i;
		for (i = 0; i < connects.size(); i ++)
		{
			node = string2vector(connects[i]);
			connect.push_back(node);
		}
		for (i = 0; i < costs.size(); i ++)
		{
			node = string2vector(costs[i]);
			cost.push_back(node);
		}
		

		for (i = 0; i < connect.size(); i ++)
		{
			length = doHowLong(connect, cost, i);
			if (length > longest)
			{
				longest = length;
			}
		}
		

		return longest;
	}
};
		

/*
Problem Statement
Your company controls the flow of oil through a network of pipes. The network is composed of N waypoints, each of which has a number 
between 0 and N-1 inclusive. Some of the waypoints are connected by pipes. You will be given vector <string>s caps and costs
describing these pipes. Each element of caps and costs will be formatted as follows (quotes for clarity):
	"x1,y1 x2,y2 x3,y3 ..."
Each x,y pair is called an indicator. Element i of caps will always contain the same number of indicators as element i of costs.
 Furthermore, the jth indicator of element i of caps will correspond to the jth indicator of element i of costs. If element i 
 of caps contains the indicator x,y it means there is a pipe that allows y units of flow from waypoint i to waypoint x. The 
 corresponding pair x,z in element i of costs gives the cost z attributed to using this pipe.  In this network, one waypoint 
 has been designated as the source, and another as the sink. Your business would like to send oil from the source to the sink 
 but it also wants to save money. For this reason, only 1 path will be activated. Your job is to find the path from the source 
 to the sink that maximizes the ratio capacity/cost. For the purposes of this problem, a path will consist of an ordered sequence 
 of distinct waypoints, from the source to the sink, where each consecutive pair of waypoints are connected by a pipe. The pipes
 on the path must allow oil to flow in the direction of the path (source to sink). No flow of oil may enter the source or leave
 the sink. The cost of a path is the sum of all the costs of the pipes on the path. The capacity is the minimum capacity over 
 all the pipes on the path. Note that the pipes are directed, so you can push oil from waypoint i to waypoint j only if there 
 is a pipe allowing such a flow in that direction. You will return the maximum value of capacity/cost accurate to 1e-9 absolute 
 or relative. If there is no path of pipes from source to finish to push oil through, return 0.
Definition


Class:
PipePath
Method:
capCost
Parameters:
vector <string>, vector <string>, int, int
Returns:
double
Method signature:
double capCost(vector <string> caps, vector <string> costs, int source, int sink)
(be sure your method is public)
????

Notes
-
A pipe from waypoint i to waypoint j does not imply there is a pipe from j to i.
-
There can be multiple pipes carrying oil from waypoint i to waypoint j.
Constraints
-
caps will contain between 2 and 50 elements inclusive.
-
caps and costs will contain the same number of elements.
-
Each element of caps and costs will contain between 0 and 50 characters inclusive.
-
Each element of caps and costs will be a single space delimited list of indicators. Each indicator will take the form (quotes for clarity) "x,y". x will have no extra leading zeros, and will be between 0 and N-1 inclusive, where N is the number of elements in caps. y will have no extra leading zeros, and will be between 1 and 20000000 inclusive.
-
Element i of caps will not contain the indicator "i,y".
-
Each element of caps and costs will have no leading or trailing whitespace.
-
Element i of caps will have the same number of indicators as element i of costs.
-
The jth indicator of element i of caps will have the same first value as the jth indicator of element i of costs.
-
source and sink will be between 0 and N-1 inclusive, where N is the number of elements in caps.
-
source and sink will not be equal.
Examples
0)

{"1,10 2,9","","1,100"}
{"1,100 2,50","","1,50"}
0
1
Returns: 0.1
The 2 paths from waypoint 0 to waypoint 1 have a cost of 100. Since one has capacity 9, and the other has capacity 10, we choose the capacity 10 path.
1)

{"1,3 3,5","3,2 2,6","3,2","1,1 2,4 4,6",
 "0,3 2,7"}
{"1,3 3,5","3,2 2,6","3,2","1,1 2,4 4,6",
 "0,3 2,7"}
0
4
Returns: 0.45454545454545453

2)

????
{"1,15 1,20","2,10",""}
{"1,10 1,10","2,15",""}
0
2
Returns: 0.4
There are multiple pipes from waypoint 0 to waypoint 1.
*/

#include <vector>
#include <string>

using namespace std;

class PipePath
{
private:
	vector<vector<pair<int, int> > >capVect;
	vector<vector<pair<int, int> > >costVect;
	int src;
	int dst;
	double doFind(vector<int> path, int minCap,int totalCost, int wayPoint)
	{
		int i;
		int newPoint, newCost, newCap;
		double result = 0, newResult;
		if (wayPoint == dst)
		{
			return (double)minCap/(double)totalCost;
		}
		for (i = 0; i < path.size(); i ++)
		{
			if (wayPoint == path[i])
			{
				return 0.0;
			}
		}
		for (i = 0; i < capVect[wayPoint].size(); i ++)
		{
			newPoint = capVect[wayPoint][i].first;
			newCap = capVect[wayPoint][i].second;
			newCost = costVect[wayPoint][i].second;
			if (i == 0)
			{
				path.push_back(wayPoint);
			}
			else
			{
				path[path.size()-1] = wayPoint;
			}
			if (minCap < newCap)
			{
				newCap = minCap;
			}
			newResult = doFind(path, newCap, totalCost + newCost, newPoint);
			if (newResult > result)
			{
				result = newResult;
			}
		}
		return result;
	}	
		
	vector<pair<int,int> >  string2vector(string& str)
	{
		char buffer[32];
		const char* ptr = str.c_str();
		int number, i;
		
		vector<pair<int, int> > result;
		pair<int, int> node;
		i = 0;
		if (str.size() >  0)
		{
			while (true)
			{
				if (*ptr == ' ' || *ptr == '\0'|| *ptr == ',')
				{
					buffer[i] = '\0';
					number = atoi(buffer);
					i = 0;
					
					if (*ptr == '\0')
					{
						node.second = number;
						result.push_back(node);
						break;
					}
					else
					{
						if (*ptr == ' ')
						{
							node.second = number;
							result.push_back(node);
						}
						else
						{
							if (*ptr == ',')
							{
								node.first = number;
							}
						}
					}
				}
				else
				{
					buffer[i] = *ptr;
					i ++;
				}
				// in any case, we advance
				ptr ++;
			}				
		}			
		return result;	
	}
	
public:
	double capCost(vector <string> caps, vector <string> costs, int source, int sink)
	{
		int i;
		src = source;
		dst = sink;
		vector<int> path;	
		for (i = 0; i < caps.size(); i ++)
		{
			capVect.push_back(string2vector(caps[i]));
			costVect.push_back(string2vector(costs[i]));
		}
		
		return doFind(path, 20000000, 0, source);	
	}
};
	
int main()
{
	vector<string> caps, costs;
	PipePath pipe;
	double result;
	char* capStr[5] = {"1,3 3,5","3,2 2,6","3,2","1,1 2,4 4,6",  "0,3 2,7"};
	char* costStr[5] = {"1,3 3,5","3,2 2,6","3,2","1,1 2,4 4,6", "0,3 2,7"};
	for (int i = 0; i < 5; i ++)
	{
		caps.push_back(capStr[i]);
		costs.push_back(costStr[i]);
	}

	result = pipe.capCost(caps, costs, 0, 4);

	return 0;
}

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

// the problem

Problem Statement
    
You have been given a rows-by-cols chessboard, with a list of squares cut out. The list of cutouts will be given in a vector <string> cutouts. Each element of cutouts is a comma-delimited lists of coords. Each coord has the form (quotes for clarity) "r c". If coord "r c" appears in an element of cutouts, it means that the square at row r column c (0-based) has been removed from the chessboard. This problem will involve placing rooks on a chessboard, so that they cannot attack each other. For a rook to attack a target piece, it must share the same row or column as the target. Your method will return an int that will be the maximum number of rooks that can be placed on the chessboard, such that no pair of rooks can attack each other. Rooks cannot be placed on cut out squares. The cut out squares do not affect where the rooks can attack.
Definition
    
Class:
RookAttack
Method:
howMany
Parameters:
int, int, vector <string>
Returns:
int
Method signature:
int howMany(int rows, int cols, vector <string> cutouts)
(be sure your method is public)
    

Constraints
-
rows will be between 1 and 300 inclusive.
-
cols will be between 1 and 300 inclusive.
-
cutouts will contain between 0 and 50 elements inclusive.
-
Each element of cutouts will contain between 3 and 50 characters inclusive.
-
Each element of cutouts will be a comma delimited list of coords. Each coord will be of the form "r c", where
r and c are integers, with no extra leading zeros,
r is between 0 and rows-1 inclusive,
and c is between 0 and cols-1 inclusive.
-
Each element of cutouts will not contain leading or trailing spaces.
Examples
0)

    
8
8
{}
Returns: 8
In the example cases the .'s represent squares of the chessboard, and the X's represent cut out squares.
........ 
........ 
........ 
........ 
........ 
........ 
........ 
........
1)

    
2
2
{"0 0","0 1","1 1","1 0"}
Returns: 0
XX 
XX  
2)

    
3
3
{"0 0","1 0","1 1","2 0","2 1","2 2"}
Returns: 2
X.. 
XX. 
XXX
3)

    
3
3
{"0 0","1 2","2 2"}
Returns: 3
X.. 
..X 
..X
4)

    
200
200
{}
Returns: 200

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.

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

// this doesn't work!!! as test case 4 runs more than 2 seconds!!!!

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

using namespace std;

class RookAttack
{
private:
	int row;
	int col;
	int* checkBoard;
	int* chessBoard;
	pair<int, int> string2pair(string& str)
	{
		pair<int, int> result;
		const char* ptr = str.c_str();
		sscanf(ptr, "%d %d", &result.first, &result.second);
		return result;
	}
	
	void init(vector<pair<int, int> >& holes)
	{
		int i;
		chessBoard = new int[row*col];
		checkBoard = new int[row*col];
		memset(checkBoard, 0, sizeof(int)*row*col);
		memset(chessBoard, 0, sizeof(int)*row*col);
		for (i = 0;  i < holes.size(); i ++)
		{
			chessBoard[holes[i].first * col + holes[i].second] = -1;
		}	
	}
	void setRook(int r, int c, int level)
	{
		int i, index;
		for (i = 0; i < row; i ++)
		{
			index = i * col + c;
			if (chessBoard[index] == 0)
			{
				chessBoard[index ] = level;
			}
		}
		for (i = 0; i < col; i ++)
		{
			index = r*col + i;
			if (chessBoard[index] == 0)
			{
				chessBoard[index] = level;
			}
		}
	}
	
	void resetRook(int r, int c, int level)
	{
		int i, index;
		for (i = 0; i < row; i ++)
		{
			index = i * col + c;
			if (chessBoard[index] == level)
			{
				chessBoard[index ] = 0;
			}
		}
		for (i = 0; i < col; i ++)
		{
			index = r*col + i;
			if (chessBoard[index] == level)
			{
				chessBoard[index] = 0;
			}
		}
	
	}
	
	int findRook(int level)
	{	
		int result = level;
		int number = 0;
		int r = -1, c = -1;
		int index;
		for (r = 0; r < row; r ++)
		{
			for (c = 0; c < col; c ++)
			{				
				index = r*col + c;
				if (chessBoard[index] == 0 && checkBoard[index] == 0)
				{					
					setRook(r, c, level);
					checkBoard[index] = 1;
					number = findRook(level + 1);
					if (number > result)
					{
						result = number;
					}
					resetRook(r, c, level);
				}
			}		
		}
		return result;		
	}
	
public:
	int howMany(int rows, int cols, vector <string> cutouts)
	{
		vector<pair<int, int> > holes;
		int i;
		for (i = 0; i < cutouts.size(); i ++)
		{
			holes.push_back(string2pair(cutouts[i]));
		}
		row = rows;
		col = cols;
		init(holes);
		return findRook(1) - 1;
	}
};

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

{}

Returns: 0

{2}

Returns: 2

{2,3}

Returns: -1

{1,1,1,1}

Returns: 0

{371,-56,933,519,583,520,938,-398,75,-269,895,-790,982,-941,937,888,-416,-360,714,-594,-783,431,595}

Returns: -12234

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

#include <vector>
#include <algorithm>

using namespace std;

class MedianProcess
{
private:
	int doGetScore(vector<int>& values)
	{
		int length = 0;
		int number;
		length = values.size();
		vector<int>::iterator it;
		if (length == 0)
		{
			return 0;
		}	
		else
		{
			if (length % 2 == 0)
			{
				number = values[length - 1];
				values.pop_back();
				return 	doGetScore(values) - number;
			}
			else
			{
				number = values[length/2];
				it = values.begin();
				for (int i = 0; i < length/2; i ++)
				{
					it ++;
				}
				values.erase(it);
				return doGetScore(values) + number;
			}
		}
	}				
		
public:
	int getScore(vector<int> values)
	{
		sort(values.begin(), values.end());
		return doGetScore(values);
	}
};

Team A   Team B    Difference
7 / 15   8 / 20    Team A played 5 games less than team B, so we assume it will win 2.5 games more.
		   Therefore Team A is (7 + 2.5) - 8 = 1.5 games ahead of team B.
8 / 8    18 / 18   Though both teams have won all their games, team A played 10 games less. 
                   We assume it wins 5 of those 10 games, so it is 5 games behind team B.
20 / 40  10 / 20   Team B played 20 games less, so we assume it will have 10 more wins.
                   Therefore, the gap between the teams is 0. 

{"A 1 1", "A 8 8","D 0 0", "B 7 7", "C 99 99", "BAA 13 13"}

Returns: {"A 0.0", "A 0.0", "B 0.0", "BAA 0.0", "C 0.0", "D 0.0" }

{"B 11 10", "A 10 10", "C 10 11", "D 20 5"}

Returns: {"D 0.0", "B 7.0", "A 7.5", "C 8.0" }

{"MAVS 54 11", "SUNS 50 16", "SPURS 46 20", "JAZZ 43 23"}

Returns: {"MAVS 0.0", "SUNS 4.5", "SPURS 8.5", "JAZZ 11.5" }

{"TEAMA 17 15", "TEAMB 14 11", "TEAMC 3 0",
 "TEAMD 99 94", "LOSER 10 85", "WINNER 76 34"}

Returns: 
{"WINNER 0.0",
 "TEAMD 18.5",
 "TEAMB 19.5",
 "TEAMC 19.5",
 "TEAMA 20.0",
 "LOSER 58.5" }

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

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

using namespace std;

class BasketballStandings
{
private:
struct Score;
struct ScoreComp
{
	bool operator()(const Score& left, const Score& right) const
	{
		float result = 0;
		result = left.comp(right);
		if (result == 0.0)
		{
			return left.name.compare(right.name) < 0;
		}
		else
		{
			return result > 0.0;
		}
	}
};
		
struct Score
{	
	int win;
	int lose;
	string name;
	float comp(const Score& other) const
	{		
		return win - other.win - (float)(win + lose - other.win - other.lose) / 2.0;
	}
};

typedef multiset<Score, ScoreComp> ScoreSet;
	Score string2score(string& str)
	{
		Score result;
		int len;
		len = str.find(' ');
		result.name.assign(&(*str.begin()), len);
		sscanf(str.c_str() + len, " %d %d", &result.win, &result.lose);
		return result;
	}
public:
	vector <string> constructTable(vector <string> teams)
	{
		ScoreSet scoreSet;	
		vector<string> result;
		char buffer[32];
		Score top;
		float gap;
		int i;
		for (i = 0; i < teams.size(); i ++)
		{
			scoreSet.insert(string2score(teams[i]));
		}
		top = *scoreSet.begin();
		for (ScoreSet::iterator it = scoreSet.begin(); it != scoreSet.end(); it ++)
		{
			gap = top.comp(*it);
			sprintf(buffer, "%s %.1f", it->name.c_str(), gap);
			result.push_back(buffer);
		}
		return result;
	}
};
				
			
			
		
			
		
		
		

int main()
{
	BasketballStandings basket;
	char* str[] = {"A 1 1", "A 8 8","D 0 0", "B 7 7", "C 99 99", "BAA 13 13"};
	vector<string> input, output;
	int i;
	for (i = 0; i <sizeof(str)/sizeof(char*); i ++)
	{
		input.push_back(str[i]);
	}

	output = basket.constructTable(input);

	for ( i = 0; i < output.size(); i ++)
	{
		printf("%s\n", output[i].c_str());
	}
	return 0;
}

"AAAAAAA"

Returns: 0.0

"AAB"

Returns: 0.6666666666666666

"AAABBBBB"

Returns: 5.5

""

Returns: 0.0

"ABABABABABABABABABABABABA"

Returns: -23.04

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 <vector>
#include <algorithm>

using namespace std;

class NoMo
{
private:
	int calcMomentum(string game)
	{
		const char* ptr = game.c_str();
		int pos = 0, neg = 0;
		bool bStart = false;
		char prev;
		while (*ptr != '\0')
		{
			if (!bStart)
			{
				bStart = true;						
			}
			else
			{
				if (*ptr == prev)
				{
					pos ++;
				}
				else
				{
					neg ++;
				}
			}
			prev = *ptr;
			ptr ++;
		}	
		return pos - neg;
	}		
		
public:
	double momentum(string game)
	{
		int total = 0, number = 0;
		int cur = 0;
		string value(game);
		vector<int> seq;
		int i;
		cur = calcMomentum(value);
		
		for (i = 0; i < game.size(); i ++)
		{
			seq.push_back(i);
		}
		
		total = cur;
		number = 1;

		while (next_permutation(seq.begin(), seq.end()))
		{
			for (i = 0; i < game.size(); i ++)
			{	
				value[i] = game[seq[i]];
			}				
			total += calcMomentum(value);
			number ++;
		}
				
		return (double)cur - (double)total/(double)number;
	}
};
	

class NoMomentum
{
private:
	int calcMomentum(string game)
	{
		int pos = 0, neg = 0, i;
		for ( i = 1; i < game.size(); i ++)
		{
			if (game[i] == game[ i -1])
			{
				pos ++;
			}
			else
			{
				neg ++;
			}
		}	
		return pos - neg;
	}		
		
public:
	double momentum(string game)
	{
		int total = 0, number = 0;
		int cur = 0;
		int length = 0;
		vector<int> seq;
		int i;
		cur = calcMomentum(game);
		
		for (i = 0; i < game.size(); i ++)
		{
			if (game[i] == 'A')
			{
				length ++;
			}			
		}
		for ( i = 0; i < game.size(); i ++)
		{
			if ( i < length)
			{
				seq.push_back(0);
			}
			else
			{
				seq.push_back(1);
			}
		}
		
		do
		{
			for ( i = 1; i < game.size(); i ++)
			{
				if (seq[i] == seq[ i - 1])
				{
					total ++;
				}
				else
				{
					total --;
				}
			}
			number ++;
		}
		while (next_permutation(seq.begin(), seq.end()));
		double result = (number != 0)?((double)total/(double)number):0;
		return (double)cur - ((number != 0)?((double)total/(double)number):0);
	}
};
	

	
int main()
{
	NoMomentum nomo;
	string game = "ABABABABABABABABABABABABA";
	double result;
	result = nomo.momentum(game);

	printf("result = %f\n", result);

	return 0;
}

"ABCBAD"

Returns: -1

"ABCDABCD"

Returns: 6

"X"

Returns: -1

"ABCDEFGHIJKLMNOPQRSTUVWXYZ"

Returns: -1

"AVERYUNUSUALACCESSPATTERNINDEED"

Returns: 15

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.