#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <functional>
#include <complex>
#include <queue>
#include <stack>
#include <cmath>
#include <cassert>
#include <cstring>
using namespace std;
typedef long long LL;
typedef complex<double> CMP;
class CssRules { public:
int getMinimalCssRuleCount(vector <string> xthml)
{
tree virtual_root;
{
num_node = 0;
string xs = accumulate(xthml.begin(), xthml.end(), string(""));
const char* p = xs.c_str();
virtual_root.children = parse_tags(p);
}
vector<int> memo(num_node*8*8*8, -1);
return rec(virtual_root.children, 7*64+7*8+7, memo);
}
struct tree
{
int id;
int tag;
int color;
vector<tree*> children;
~tree() { for(int i=0; i<children.size(); ++i) delete children[i]; }
};
// solver -------------------------------------------------------------
int rec(vector<tree*>& ts, int tag_to_color, vector<int>& memo)
{
int sum = 0;
for(int i=0; i<ts.size(); ++i)
sum += rec(ts[i], tag_to_color, memo);
return sum;
}
int rec(tree* t, int tag_to_color, vector<int>& memo)
{
const int key = t->id * 8*8*8 + tag_to_color;
if( memo[key] >= 0 )
return memo[key];
int me = ((tag_to_color>>(3*t->tag))&7) != t->color;
int best = 0x3fffffff;
for(int ttc=0; ttc<8*8*8; ++ttc)
{
int cost = 0;
cost += ((tag_to_color>>0)&7) != ((ttc>>0)&7);
cost += ((tag_to_color>>3)&7) != ((ttc>>3)&7);
cost += ((tag_to_color>>6)&7) != ((ttc>>6)&7);
best = min(best, cost + srec(t->children, ttc, memo));
}
return memo[key] = me + best;
}
// parser ------------------------------------------------------
int num_node;
vector<tree*> parse_tags( const char*& p )
{
vector<tree*> res;
while(*p && p[1]!='/')
res.push_back(parse_tag(p));
return res;
}
tree* parse_tag( const char*& p )
{
static map<string, int> color_map;
if( color_map.empty() )
{
color_map["black"] = 0;
color_map["blue"] = 1;
color_map["gray"] = 2;
color_map["green"] = 3;
color_map["red"] = 4;
color_map["white"] = 5;
color_map["yellow"] = 6;
}
static map<string, int> tag_map;
if( tag_map.empty() )
{
tag_map["b"] = 0;
tag_map["u"] = 1;
tag_map["i"] = 2;
}
// <TAG id='ID' style='color:COLOR'>tagContent</TAG>
p++; // <
string tag; while(*p!=' ') tag+=*p++; // TAG
while(*p==' ') ++p; // _sp_
p += 4; // id='
string id; while(*p!='\'') id+=*p++; // ID
++p; // '
while(*p==' ') ++p; // _sp_
p += 13; // style='color:
string cl; while(*p!='\'') cl+=*p++; // COLOR
p += 2; // '>
vector<tree*> ch = parse_tags(p); // tagContent
p += 4; // </TAG>
tree* t = new tree;
t->id = num_node++;
t->tag = tag_map[tag];
t->color = color_map[cl];
t->children = ch;
return t;
}
};
// BEGIN CUT HERE
#include <ctime>
double start_time; string timer()
{ ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
{ os << "{ ";
for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
void verify_case(const int& Expected, const int& Received) {
bool ok = (Expected == Received);
if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl;
cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
#define END verify_case(_, CssRules().getMinimalCssRuleCount(xthml));}
int main(){
CASE(6)
string xthml_[] = {"<i id='b' style='color:white'><u id='f' styl", "e='color:red'></u><u id='e' style='color:red", "'></u><u id='d' style='color:gray'></u><i id", "='c' style='color:white'></i></i><i id='a' s", "tyle='color:red'></i>"};
vector <string> xthml(xthml_, xthml_+sizeof(xthml_)/sizeof(*xthml_));
int _ = 5;
END
CASE(0)
string xthml_[] = {"<b id='x' style='color:red'></b>"};
vector <string> xthml(xthml_, xthml_+sizeof(xthml_)/sizeof(*xthml_));
int _ = 1;
END
CASE(1)
string xthml_[] = {"<b id='x' style='color:red'>","<b id='y' style='color:red'>",
"<b id='z' style='color:red'>","</b></b></b>"}
;
vector <string> xthml(xthml_, xthml_+sizeof(xthml_)/sizeof(*xthml_));
int _ = 2;
END
CASE(2)
string xthml_[] = {"<b id='x' style='color:red'>",
"<b id='y' style='color:red'>",
"<b id='w' style='color:red'>",
"</b>",
"</b>",
"<u id='z' style='color:red'>",
"</u>",
"</b>"};
vector <string> xthml(xthml_, xthml_+sizeof(xthml_)/sizeof(*xthml_));
int _ = 3;
END
CASE(3)
string xthml_[] = {"<b id='x' style='color:red'>",
"<i id='y' style='color:black'>",
"<u id='w' style='color:white'>",
"</u>",
"</i>",
"<u id='z' style='color:yellow'>",
"</u>",
"</b>"};
vector <string> xthml(xthml_, xthml_+sizeof(xthml_)/sizeof(*xthml_));
int _ = 4;
END
CASE(4)
string xthml_[] = {"<b id='x' style='col", "or:red'></b>", "<b id=", "'xx' style='color", ":red'></b>"};
vector <string> xthml(xthml_, xthml_+sizeof(xthml_)/sizeof(*xthml_));
int _ = 2;
END
CASE(5)
string xthml_[] = {
"<b id='aa' style='color:red'><b id='ab' style='col",
"or:red'><b id='ac' style='color:red'><b id='ad' st",
"yle='color:red'><b id='ae' style='color:red'><b id",
"='af' style='color:red'><b id='ag' style='color:re",
"d'><b id='ah' style='color:red'><b id='ai' style='",
"color:red'><b id='aj' style='color:red'><b id='ak'",
" style='color:red'><b id='al' style='color:red'><b",
" id='am' style='color:red'><b id='an' style='color",
":red'><b id='ao' style='color:red'><b id='ap' styl",
"e='color:red'><b id='aq' style='color:red'><b id='",
"ar' style='color:red'><b id='as' style='color:red'",
"><b id='at' style='color:red'><b id='au' style='co",
"lor:red'><b id='av' style='color:red'><b id='aw' s",
"tyle='color:red'><b id='ax' style='color:red'><b i",
"d='ay' style='color:red'><b id='az' style='color:r",
"ed'><b id='ba' style='color:red'><b id='bb' style=",
"'color:red'><b id='bc' style='color:red'><b id='bd",
"' style='color:red'><b id='be' style='color:red'><",
"b id='bf' style='color:red'><b id='bg' style='colo",
"r:red'><b id='bh' style='color:red'><b id='bi' sty",
"le='color:red'><b id='bj' style='color:red'><b id=",
"'bk' style='color:red'><b id='bl' style='color:red",
"'><b id='bm' style='color:red'><b id='bn' style='c",
"olor:red'><b id='bo' style='color:red'><b id='bp' ",
"style='color:red'><b id='bq' style='color:red'><b ",
"id='br' style='color:red'><b id='bs' style='color:",
"red'><b id='bt' style='color:red'><b id='bu' style",
"='color:red'><b id='bv' style='color:red'><b id='b",
"w' style='color:red'><b id='bx' style='color:red'>",
"<b id='by' style='color:red'><b id='bz' style='col",
"or:red'><b id='ca' style='color:red'><b id='cb' st",
"yle='color:red'><b id='cc' style='color:red'><b id",
"='cd' style='color:red'><b id='ce' style='color:re",
"d'><b id='cf' style='color:red'><b id='cg' style='",
"color:red'><b id='ch' style='color:red'><b id='ci'",
" style='color:red'><b id='cj' style='color:red'><b",
" id='ck' style='color:red'><b id='cl' style='color",
":red'><b id='cm' style='color:red'><b id='cn' styl",
"e='color:red'><b id='co' style='color:red'><b id='",
"cp' style='color:red'><b id='cq' style='color:red'",
"><b id='cr' style='color:red'><b id='cs' style='co",
"lor:red'><b id='ct' style='color:red'><b id='cu' s",
"tyle='color:red'><b id='cv' style='color:red'><b i",
"d='cw' style='color:red'></b></b></b></b></b></b><",
"/b></b></b></b></b></b></b></b></b></b></b></b></b",
"></b></b></b></b></b></b></b></b></b></b></b></b><",
"/b></b></b></b></b></b></b></b></b></b></b></b></b",
"></b></b></b></b></b></b></b></b></b></b></b></b><",
"/b></b></b></b></b></b></b></b></b></b></b></b></b",
"></b></b></b></b></b></b>"
};
vector <string> xthml(xthml_, xthml_+sizeof(xthml_)/sizeof(*xthml_));
int _ = -1;
END
}
// END CUT HERE