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