ADDED SRM/608-U/1A.cpp Index: SRM/608-U/1A.cpp ================================================================== --- SRM/608-U/1A.cpp +++ SRM/608-U/1A.cpp @@ -0,0 +1,133 @@ +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +using namespace std; +typedef long long LL; +typedef complex CMP; + +class MysticAndCandies { public: + int minBoxes(int C, int X, vector low, vector high) + { + sort(low.begin(), low.end()); + int t1 = 0, c1 = 0; + while(t1 < X) { + t1 += low.back(); + c1 += 1; + low.pop_back(); + } + + sort(high.begin(), high.end()); + int t2 = accumulate(high.begin(), high.end(), 0), c2 = 0; + while(t2 > C-X) { + t2 -= high.back(); + c2 += 1; + high.pop_back(); + } + + return min(c1, c2); + } +}; + +// BEGIN CUT HERE +#include +double start_time; string timer() + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } +template ostream& operator<<(ostream& os, const vector& v) + { os << "{ "; + for(typename vector::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(_, MysticAndCandies().minBoxes(C, X, low, high));} +int main(){ + +CASE(0) + int C = 15; + int X = 12; + int low_[] = {1, 2, 3, 4, 5}; + vector low(low_, low_+sizeof(low_)/sizeof(*low_)); + int high_[] = {1, 2, 3, 4, 5}; + vector high(high_, high_+sizeof(high_)/sizeof(*high_)); + int _ = 3; +END +CASE(1) + int C = 60; + int X = 8; + int low_[] = {5, 2, 3}; + vector low(low_, low_+sizeof(low_)/sizeof(*low_)); + int high_[] = {49, 48, 47}; + vector high(high_, high_+sizeof(high_)/sizeof(*high_)); + int _ = 2; +END +CASE(2) + int C = 58; + int X = 30; + int low_[] = {3, 9, 12, 6, 15}; + vector low(low_, low_+sizeof(low_)/sizeof(*low_)); + int high_[] = {8, 12, 20, 8, 15}; + vector high(high_, high_+sizeof(high_)/sizeof(*high_)); + int _ = 2; +END +CASE(3) + int C = 207581165; + int X = 172146543; + int low_[] = {4725448, 2753824, 6019698, 4199708, 4070001, 3589497, 5358499, 3637585, 5393667, 2837466, +2747807, 2918199, 3638042, 5199002, 3072044, 3858909, 3762101, 3657754, 3218704, 3888861, +3195689, 4768935, 3137633, 4124272, 4125056, 6087486, 3632970, 3620489, 2748765, 5917493, +3958996, 3335021, 3517186, 5543440, 2951006, 3403270, 3299481, 3093204, 4092331}; + vector low(low_, low_+sizeof(low_)/sizeof(*low_)); + int high_[] = {5702812, 6805664, 6823687, 5337687, 4286533, 4999849, 6567411, 4563235, 6618139, 6260135, +6249469, 3821449, 5963157, 6385012, 4255959, 5786920, 6112817, 4103918, 6371537, 4231698, +3409172, 6806782, 5623563, 4511221, 6407338, 6491490, 5209517, 6076093, 6530132, 6111464, +5833839, 6253088, 5595160, 6236805, 5772388, 5285713, 5617002, 4650978, 5234740}; + vector high(high_, high_+sizeof(high_)/sizeof(*high_)); + int _ = 31; +END +CASE(4) + int C = 43873566; + int X = 32789748; + int low_[] = {2053198, 2175819, 4260803, 1542497, 1418952, 5000015, 1381849, 2462882, 6466891, 1827580, 6943641, 5775477}; + vector low(low_, low_+sizeof(low_)/sizeof(*low_)); + int high_[] = {2827461, 3726335, 5410505, 4781355, 4925909, 5621160, 7325774, 5025476, 7876037, 8072075, 6979462, 6647628}; + vector high(high_, high_+sizeof(high_)/sizeof(*high_)); + int _ = 7; +END +/* +CASE(5) + int C = ; + int X = ; + int low_[] = ; + vector low(low_, low_+sizeof(low_)/sizeof(*low_)); + int high_[] = ; + vector high(high_, high_+sizeof(high_)/sizeof(*high_)); + int _ = ; +END +CASE(6) + int C = ; + int X = ; + int low_[] = ; + vector low(low_, low_+sizeof(low_)/sizeof(*low_)); + int high_[] = ; + vector high(high_, high_+sizeof(high_)/sizeof(*high_)); + int _ = ; +END +*/ +} +// END CUT HERE ADDED SRM/608-U/1B.cpp Index: SRM/608-U/1B.cpp ================================================================== --- SRM/608-U/1B.cpp +++ SRM/608-U/1B.cpp @@ -0,0 +1,332 @@ +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +using namespace std; +typedef long long LL; +typedef complex CMP; + +template +class SCC +{ + vector< vector > G; + +public: + void addVert( Vert s ) + { + if( s >= G.size() ) G.resize(s+1); + } + + void addEdge( Vert s, Vert t ) + { + if( max(s,t) >= G.size() ) G.resize(max(s,t)+1); + G[s].push_back(t); + } + + void scc() + { + int N = G.size(); + dfs_no.assign(N, 0); + dfs_lo.assign(N, 0); + pending = stack(); + scc_id.assign(N, -1); + scc_list.clear(); + scc_children.clear(); + for(int v=0; v scc_id; // which scc does the vert belong to? + vector< vector > scc_list; // list of nodes in the scc + vector< vector > scc_children; // forest relationship of sccs + +private: + int no; + vector dfs_no; // 1-origin dfs-visit ID + vector dfs_lo; // the least ID in the vert's scc + stack pending; // current unclassigied verts + + void dfs(int v) + { + // visit v if not yet + if( dfs_no[v] ) + return; + dfs_no[v] = dfs_lo[v] = ++no; + pending.push(v); + + // visit children + for(int i=0; i scc; + for(;;) { + int w = pending.top(); pending.pop(); + scc.push_back(w); + scc_id[w] = scc_list.size(); + if( w == v ) break; + } + scc_list.push_back(scc); + + set children; + for(int j=0; j(children.begin(), children.end()) ); + } + } +}; + +class BigO { public: + int minK(vector graph) + { + int N = graph.size(); + SCC scc; + for(int i=0; i loop(K); + for(int i=0; i=2) + return -1; // branched loop + } + + loop[i] = true; + } + + function rec; + vector memo(K, -1); + rec = [&](int s) { + if(memo[s] != -1) + return memo[s]; + int best = 0; + for(int t: scc.scc_children[s]) + best = max(best, rec(t)); + return memo[s] = best + loop[s]; + }; + + int best = 0; + for(int i=0; i +double start_time; string timer() + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } +template ostream& operator<<(ostream& os, const vector& v) + { os << "{ "; + for(typename vector::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(_, BigO().minK(graph));} +int main(){ + +CASE(0) + string graph_[] = {"NYY", + "YNY", + "YYN"}; + vector graph(graph_, graph_+sizeof(graph_)/sizeof(*graph_)); + int _ = -1; +END +CASE(1) + string graph_[] = {"NYNNN", + "NNYNN", + "NNNYN", + "NNNNY", + "NNNNN"}; + vector graph(graph_, graph_+sizeof(graph_)/sizeof(*graph_)); + int _ = 0; +END +CASE(2) + string graph_[] = {"NYNNN", + "YNNNN", + "NNNYN", + "NNNNY", + "NNYNN"}; + vector graph(graph_, graph_+sizeof(graph_)/sizeof(*graph_)); + int _ = 0; +END +CASE(3) + string graph_[] = {"NYYYNYYYNNYYYYYYNYNN", + "NNNNYNYYNNYYYNYYNYYN", + "NYNNYYYNNNYYYYNYNYNN", + "NYYNNYYYYNNNYYNNYNYY", + "NYNYNNNNNNYYYYYNYYYN", + "YNNNNNNYNNYNNYYYYYYY", + "NNYYNNNNNYNYNYNNYNYY", + "NNYNYYNNNNYNYNYYYYNN", + "NYYNYYNNNYNNYYYNYNYN", + "YYNNYNNYYNYNNNNNYNNN", + "YYNYYNNYYYNYYNYNYYYY", + "YYNNYYNYNYNNNNYNNNNY", + "NNYYNYYYNNNNNYYYYYNY", + "YNNNYNNNNYNNNNNYNNNY", + "YYYYNYYNNYNNNNNYNNNN", + "NYYYYNYNYYNNYNNNYNNY", + "YYYYYNNNYYYYNYYYNNYN", + "NNYNNYNYNYNNNNNNYNYN", + "YYNYYNNNNNYNNYNYNNNY", + "YYYYNYNYYNNYNYNYNNNN"}; + vector graph(graph_, graph_+sizeof(graph_)/sizeof(*graph_)); + int _ = -1; +END +CASE(4) + string graph_[] = {"NYNYYYNYYYNYYNYYNYYNYYNYNNYYYYNNNYYNNNYNYYNYNNNYNY", + "NNNNNNNNNNNNNNNNYNNNYNNNNNYNYNYNNNNNNYNNNNNNNNNNNN", + "NYNYYYYNYNYYNNYYYYYYYYYYNYYYNYYYYYYNNYYYYYYYNNYYYY", + "NYNNYYNNNNNNNNNNNYNNNYNYNNYNYNYYNYYNNYYYNNNNNNNYYY", + "NNNNNNNNNNNNYNNYYNNNYNNNNYNNYNNYNNYNNYNYNNNNNNNYYN", + "NNNNNNNNNNNNNNNNYNNNYNNNNNNNNNYNNNNNNYNNNNNNNNNNNN", + "YYNYNNNYNYYYYNYYYYYYYYYYNYYYYYYYNYYNNYNYYYYYNNYNYY", + "NYNYYNNNYYNNYNNYYYNNYYNYNYYNYYYNNNYNNYYYNNNNNNNYYY", + "NYNYYYNYNYNNNNNYYYNNNNNNNYYNYYYYNYYNNYYYNNNNNNNYYY", + "NYNNNYNNNNNNNNNYYNNNYNNNNNYNYNYNNYYNNYNYNNNYNNNNYN", + "NYNYYYNNYYNYYNYNYYNYYYNYNYYNYYYYNYNNNNYYYYNYNNNYNY", + "NYNNYYNNNYNNYNNYYYNNYYNNNYYNYYNNNYYNNNNYNNNYNNNYYY", + "NNNNNNNNNNNNNNNYYNNNYNNNNNNNYNNYNYNNNYYNNNNNNNNYNN", + "YYYYNYYYYYYYYNYYYYNYYYYYYYYYYYNYYNYYYNYYYYYNNYYNYN", + "NYNYYNNYYYNYYNNYYYNYNYNYNYYNYYYYNYYNNYYYYYNYNNNNNY", + "NYNNNNNNNNNNNNNNYNNNYNNNNNYNYNYYNYNNNNNNNNNNNNNNNN", + "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNN", + "NYNNNYNNNNNNNNNYYNNNNNNNNNNNYNYYNYYNNYNNNNNNNNNYYN", + "NYNYYYNNYYNYNNYYYYNYYYNYNYYYYNNYNNYNNYNYYYYNNNYYYY", + "NNNYYYNNNYNYYNNYYYNNYYNNNYYNYYYYNYYNNNYYNYNYNNNYYY", + "NNNNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNN", + "NYNNNYNNNNNNNNNYNNNNNNNNNYYNYYYYNYYNNYNNNNNNNNNYYN", + "YYNYYYNNYYNYYNYNYYNYNYNYNYYYYYYYNYNNNYYYYYNYNNYYYY", + "NYNYYYNNNNNNYNNNYYNNYYNNNYYNYYYYNYYNNYYYNNNNNNNYNY", + "YNNNYYYYYYYYYNYYYYYYYYYNNYYNYNYNYNNYYYYYYYNYNNYYYY", + "NYNNNYNNNNNNNNNYYNNNYNNNNNYNYNYYNYYNNNNYNNNNNNNYNN", + "NNNNNNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNN", + "NYNYYYNYYYNYNNNNYYNYYNNYNYYNYYYYNYYNNNNNYYNYNNYYNN", + "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNN", + "NYNNNYNNNNNNNNNYYNNNYNNNNNNNNNYYNYYNNNNYNNNNNNNYYY", + "NNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", + "NNNNNNNNNNNNNNNNYNNNYNNNNNYNNNYNNNNNNNNNNNNNNNNNNN", + "NYNYYNNYYYNNNNNYYYNYYYNNNYYYYYYYNYYNNYYYYNNYNNNNYY", + "NNNNNNNNNNNNNNNYYNNNYNNNNNYNYNYYNNNNNYNNNNNNNNNNNN", + "NYNNNNNNNNNNNNNNYNNNYNNNNNYNNNYYNNNNNNNNNNNNNNNYNN", + "NYNYYYYYNYYYYNYYYYYYNYYYNNNYYYYYNYYNYNYYYYYYNYYYNY", + "YYNYYYNYYYNNNNNYNYYYYNYNNNYYYYYYNYYNNYYNYNNYNNYNNY", + "NNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", + "NYNNNYNNNNNNNNNYYNNNNYNNNNYNYNNYNNNNNYNYNNNNNNNYNN", + "NYNNNYNNNNNNNNNYYNNNNNNNNYYNYNYNNYYNNNNNNNNNNNNYNN", + "NYNYYYNYYYNYNNNNNYNNYYNYNNYNNYYYNYYNNYYYNNNNNNNYYY", + "NYNYYNNNNYNYYNNYYYNYYYNNNYYNYYYNNYYNNYYYNNNYNNNNYY", + "NYNYNYNYYYNYYNYYNYNYNYYYNNYYYYYYNNNNNYYYNYNYNNYNYY", + "NYNNNYNNNYNNNNNYYYNNYNNNNNYNYNNNNYYNNYNYNNNNNNNYYN", + "YYYNNYNYYYNYNNYYYYYNYYNYNYYYYYNYYNYNYYYYYNNYNNYNYN", + "YYNNYYYYYYYNYNYYNYYYYYYYYYYNYYYNYYYNNYYYYNYYNNYYYY", + "NYNNYYNYYYNNYNNYYYNYNYNYNYYNNYYNNYNNNYYYNYNYNNNNYY", + "NNNNNNNNNNNNNNNNYNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNN", + "NNNNNNNNNNNNNNNNNNNNYNNNNNYNYNYNNNNNNYNNNNNNNNNYNN", + "NYNNYYNNNNNNNNNYYNNNNNNNNYYNYNNYNYYNNYNYNNNNNNNYNN"}; + vector graph(graph_, graph_+sizeof(graph_)/sizeof(*graph_)); + int _ = 7; +END +CASE(5) + string graph_[] = { + "YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY", + "YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY", + "YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY", + "YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY", + "YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY", + "YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY", + "YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY", + "YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY", + "YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY", + "YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY", + "YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY", + "YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY", + "YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY", + "YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY", + "YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY", + "YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY", + "YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY", + "YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY", + "YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY", + "YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY", + "YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY", + "YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY", + "YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY", + "YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY", + "YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY", + "YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY", + "YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY", + "YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY", + "YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY", + "YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY", + "YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY", + "YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY", + "YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY", + "YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY", + "YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY", + "YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY", + "YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY", + "YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY", + "YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY", + "YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY", + "YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY", + "YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY", + "YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY", + "YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY", + "YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY", + "YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY", + "YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY", + "YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY", + "YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY", + "YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY", +}; + vector graph(graph_, graph_+sizeof(graph_)/sizeof(*graph_)); + int _ = -1; +END +/* +CASE(6) + string graph_[] = ; + vector graph(graph_, graph_+sizeof(graph_)/sizeof(*graph_)); + int _ = ; +END +*/ + +} +// END CUT HERE