DengklekMakingChains.cpp

#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cassert>
#include <climits>
#include <cstring>
using namespace std;

typedef long long  int64;
typedef vector<int> vi;
typedef string ST;
typedef stringstream SS;
typedef vector< vector <int> > vvi;
typedef pair<int,int> ii;
typedef vector <string> vs;

#define Pf	printf
#define	Sf	scanf

#define	ep	1e-9
#define PI M_PI
#define E M_E

#define	CL(a, b)	memset(a, b, sizeof(a))
#define	mp	make_pair

#define	pb	push_back

#define	all(c)	(c).begin(), (c).end()
#define	tr(i, c)	for(typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)

#define	present(x, c)	((c).find(x) != (c).end())		//map & set//
#define	cpresent(x, c)	(find(all(c),x) != (c).end())	//vector & list//

#define forn(i, n)	for(int i = 0, loop_ends_here = (int)n; i < loop_ends_here; i++)
#define forab(i, a, b)	for(int i = a, loop_ends_here = (int) b; i <= loop_ends_here; i++)
#define rep(i, a, b)	for(int i = a, loop_ends_here = (int)b; i>=loop_ends_here; i--)

class DengklekMakingChains
{
	int num(char ch) {
		if(ch == '.')
			return -1;
		return ch - '0';
	}
	bool isAll(ST &st) {
		return (st[0] != '.' && st[1] != '.' && st[2] != '.') ? true :false;
	}
	int countLeft(ST &st) {
		int ret = 0;
		for(int i = 0; i < 3 && st[i] != '.' ; i++)
			ret += num(st[i]);
		return ret;
	}
	int countRight(ST &st) {
		int ret = 0;
		for(int i = 2; i >= 0 && st[i] != '.' ; i--)
			ret += num(st[i]);
		return ret;
	}
public:
	int maxBeauty(vector <string> ch)
	{
	/*
		if(ch.size() == 1) {
			if(ch[0] == "...")
				return 0;
			if (ch[0][1] == '.' )
				return max(num(ch[0][0]), num(ch[0][2]));
			int ret = 0;
			forn(i, 3)
				ret += num(ch[0][i]);
			return ret;
		}
		bool flag = true;
		forn(i, ch.size())
			if(ch[i] != "...")
				flag = false;
		if(flag)
			return 0;
	*/
		int ret = 0;

		forn(i, ch.size())
			if(isAll(ch[i]))
				ret += countLeft(ch[i]);

//		cout << "#1\n";
		int left = 0, right = 0, idx = -1;

		forn(i, ch.size())	if(! isAll(ch[i])) {
			int t = countLeft(ch[i]);
			if(t > left) {
				left = t;
				idx = i;
			}
			else if(t == left && idx != -1) {
				if( countRight(ch[i]) < countRight(ch[idx]) )
					idx = i;
			}
		}

//		cout << "#2\n";
		forn(i, ch.size())	if(i != idx && ! isAll(ch[i])) {
			int t = countRight(ch[i]);
			if(t > right) {
				right = t;
//				idx = i;
			}
		}
//		cout << "#3\n";
		int ret1 = left + right;

		left = 0, right = 0, idx = -1;

		forn(i, ch.size())	if(! isAll(ch[i])) {
			int t = countRight(ch[i]);
			if(t > right) {
				right = t;
				idx = i;
			}
			else if(t == right && idx != -1) {
				if( countLeft(ch[i]) < countLeft(ch[idx]) )
					idx = i;
			}
		}

		forn(i, ch.size())	if(i != idx && ! isAll(ch[i])) {
			int t = countLeft(ch[i]);
			if(t > left) {
				left = t;
//				idx = i;
			}
		}

		int ret2 = left + right;

		ret += max(ret1, ret2);

		ret1 = 0;
		forn(i, ch.size())
			if(ch[i][0] == '.' && ch[i][2] == '.' && ch[i][1] != '.')
				ret1 = max(ret1, num(ch[i][1]));

		ret = max(ret, ret1);
		return ret;
/*
		int ret = 0;

		forn(i, ch.size())
			if(isAll(ch[i]))
				forn(j, 3)
					ret += num(ch[i][j]);

		
		int left1 = 0, right1 = 0, t = 0, idx, ret1, ret2;

		forn(i, ch.size())	 if(!isAll(ch[i])) {
			t = 0;
			for(int j = 0; j < 3 && ch[i][j] != '.'; j++)
				t += num(ch[i][j]);
			if(t > left) {
				left = t;
				idx = i;
			}
			if(t == left) {
				int t1 = 0, t2;
				for(int j = 2; ch[i][j] != '.'; j--)
					t1 += num(ch[i][j]);
				if()
			}
			left = max(left, t);
			Pf("ch = %s : left = %d\n", ch[i].c_str(), left);
		}

		forn(i, ch.size())	 if(!isAll(ch[i])) {
			t = 0;
			for(int j = 2; j >= 0 && ch[i][j] != '.'; j--)
				t += num(ch[i][j]);
			right = max(right, t);
			Pf("ch = %s : right = %d\n", ch[i].c_str(), right);
		}

		Pf("ret = %d, left = %d, right = %d\n", ret, left, right);
		
		return ret + left + right;
*/
	}
};

// BEGIN KAWIGIEDIT TESTING
// Generated by KawigiEdit 2.1.8 (beta) modified by pivanof
#include <iostream>
#include <string>
#include <vector>
using namespace std;
bool KawigiEdit_RunTest(int testNum, vector <string> p0, bool hasAnswer, int p1) {
	cout << "Test " << testNum << ": [" << "{";
	for (int i = 0; int(p0.size()) > i; ++i) {
		if (i > 0) {
			cout << ",";
		}
		cout << "\"" << p0[i] << "\"";
	}
	cout << "}";
	cout << "]" << endl;
	DengklekMakingChains *obj;
	int answer;
	obj = new DengklekMakingChains();
	clock_t startTime = clock();
	answer = obj->maxBeauty(p0);
	clock_t endTime = clock();
	delete obj;
	bool res;
	res = true;
	cout << "Time: " << double(endTime - startTime) / CLOCKS_PER_SEC << " seconds" << endl;
	if (hasAnswer) {
		cout << "Desired answer:" << endl;
		cout << "\t" << p1 << endl;
	}
	cout << "Your answer:" << endl;
	cout << "\t" << answer << endl;
	if (hasAnswer) {
		res = answer == p1;
	}
	if (!res) {
		cout << "DOESN'T MATCH!!!!" << endl;
	} else if (double(endTime - startTime) / CLOCKS_PER_SEC >= 2) {
		cout << "FAIL the timeout" << endl;
		res = false;
	} else if (hasAnswer) {
		cout << "Match :-)" << endl;
	} else {
		cout << "OK, but is it right?" << endl;
	}
	cout << "" << endl;
	return res;
}
int main() {
	bool all_right;
	all_right = true;
	
	vector <string> p0;
	int p1;
	
	{
	// ----- test 0 -----
	string t0[] = {".15","7..","402","..3"};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	p1 = 19;
	all_right = KawigiEdit_RunTest(0, p0, true, p1) && all_right;
	// ------------------
	}
	
	{
	// ----- test 1 -----
	string t0[] = {"..1","7..","567","24.","8..","234"};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	p1 = 36;
	all_right = KawigiEdit_RunTest(1, p0, true, p1) && all_right;
	// ------------------
	}
	
	{
	// ----- test 2 -----
	string t0[] = {"...","..."};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	p1 = 0;
	all_right = KawigiEdit_RunTest(2, p0, true, p1) && all_right;
	// ------------------
	}
	
	{
	// ----- test 3 -----
	string t0[] = {"16.","9.8",".24","52.","3.1","532","4.4","111"};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	p1 = 28;
	all_right = KawigiEdit_RunTest(3, p0, true, p1) && all_right;
	// ------------------
	}
	
	{
	// ----- test 4 -----
	string t0[] = {"..1","3..","2..",".7."};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	p1 = 7;
	all_right = KawigiEdit_RunTest(4, p0, true, p1) && all_right;
	// ------------------
	}
	
	{
	// ----- test 5 -----
	string t0[] = {"412","..7",".58","7.8","32.","6..","351","3.9","985","...",".46"};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	p1 = 58;
	all_right = KawigiEdit_RunTest(5, p0, true, p1) && all_right;
	// ------------------
	}
	
	{
	// ----- test 6 -----
	string t0[] = {"3.4","000","2.4"};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	p1 = 7;
	all_right = KawigiEdit_RunTest(6, p0, true, p1) && all_right;
	// ------------------
	}
	
	{
	// ----- test 7 -----
	string t0[] = {"3.4","000","2.4"};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	p1 = 7;
	all_right = KawigiEdit_RunTest(7, p0, true, p1) && all_right;
	// ------------------
	}
	
	{
	// ----- test 8 -----
	string t0[] = {"000","3.3"};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	p1 = 3;
	all_right = KawigiEdit_RunTest(8, p0, true, p1) && all_right;
	// ------------------
	}
	
	{
	// ----- test 9 -----
	string t0[] = {"...","..."};
			p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
	p1 = 0;
	all_right = KawigiEdit_RunTest(9, p0, true, p1) && all_right;
	// ------------------
	}
	
	if (all_right) {
		cout << "You're a stud (at least on the example cases)!" << endl;
	} else {
		cout << "Some of the test cases had errors." << endl;
	}
	return 0;
}
// PROBLEM STATEMENT
// Mr. Dengklek lives in the Kingdom of Ducks, where humans and ducks live together in peace and harmony. 
// 
// 
// 
// Mr. Dengklek works as a chain maker. Today, he would like to make a beautiful chain as a decoration for one of his lovely ducks. He will produce the chain from leftovers he found in his workshop. Each of the leftovers is a chain piece consisting of exactly 3 links. Each link is either clean or rusty. Different clean links may have different degrees of beauty.
// 
// 
// 
// You are given a vector <string> chains describing the leftovers. Each element of chains is a 3-character string describing one of the chain pieces. A rusty link is represented by a period ('.'), whereas a clean link is represented by a digit ('0'-'9'). The value of the digit in the clean link is the beauty of the link. For example, chains = {".15", "7..", "532", "..3"} means that Mr. Dengklek has 4 chain pieces, and only one of these ("532") has no rusty links.
// 
// 
// 
// All links have the same shape, which allows Mr. Dengklek to concatenate any two chain pieces. However, the link shape is not symmetric, therefore he may not reverse the chain pieces. E.g., in the above example he is able to produce the chain "532.15" or the chain ".15..37..", but he cannot produce "5323..".
// 
// 
// 
// To produce the chain, Mr. Dengklek will follow these steps:
// 
// Concatenate all chain pieces in any order.
// Pick a contiguous sequence of links that contains no rusty links. Remove and discard all the remaining links.
// 
// The beauty of the new chain is the total beauty of all the links picked in the second step. Of course, Mr. Dengklek would like to create the most beautiful chain possible.
// 
// 
// 
// Return the largest possible beauty a chain can have according to the above rules.
// 
// DEFINITION
// Class:DengklekMakingChains
// Method:maxBeauty
// Parameters:vector <string>
// Returns:int
// Method signature:int maxBeauty(vector <string> chains)
// 
// 
// NOTES
// -Mr. Dengklek is not allowed to remove and discard individual links before concatenating the chain pieces.
// -If all links in the input are rusty, Mr. Dengklek is forced to select an empty sequence of links. The beauty of an empty sequence is 0.
// 
// 
// CONSTRAINTS
// -chains will contain between 1 and 50 elements, inclusive.
// -Each element of chains will contain exactly 3 characters.
// -Each character in each element of chains will be either a '.' or one of '0'-'9'.
// 
// 
// EXAMPLES
// 
// 0)
// {".15", "7..", "402", "..3"}
// 
// Returns: 19
// 
// One possible solution:
// 
// 
// In the first step, concatenate the chain pieces in the order "..3", ".15", "402", "7.." to obtain the chain "..3.154027..".
// In the second step, pick the subsequence "154027".
// 
// The beauty of the chain in this solution is 1+5+4+0+2+7 = 19.
// 
// 1)
// {"..1", "7..", "567", "24.", "8..", "234"}
// 
// Returns: 36
// 
// One possible solution is to concatenate the chain pieces in this order:
// 
// "..1", "234", "567", "8..", "24.", "7.." -> "..12345678..24.7..",
// 
// and then to pick the subsequence "12345678". Its beauty is 1+2+3+4+5+6+7+8 = 36.
// 
// 2)
// {"...", "..."}
// 
// Returns: 0
// 
// Mr. Dengklek cannot pick any links.
// 
// 3)
// {"16.", "9.8", ".24", "52.", "3.1", "532", "4.4", "111"}
// 
// Returns: 28
// 
// 
// 
// 4)
// {"..1", "3..", "2..", ".7."}
// 
// Returns: 7
// 
// 
// 
// 5)
// {"412", "..7", ".58", "7.8", "32.", "6..", "351", "3.9", "985", "...", ".46"}
// 
// Returns: 58
// 
// 
// 
// END KAWIGIEDIT TESTING




//Powered by KawigiEdit 2.1.8 (beta) modified by pivanof!