ADDED SRM/551-U/1A.cpp
Index: SRM/551-U/1A.cpp
==================================================================
--- SRM/551-U/1A.cpp
+++ SRM/551-U/1A.cpp
@@ -0,0 +1,110 @@
+#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>
+using namespace std;
+typedef long long LL;
+typedef long double LD;
+typedef complex<LD> CMP;
+
+class ColorfulChocolates { public:
+ int maximumSpread(string chocolates, int maxSwaps)
+ {
+ int N = chocolates.size();
+ chocolates += '$';
+ int best = 0;
+ for(int s=0; s<N; ++s)
+ for(int e=s+1; e<=N; ++e)
+ for(char c='A'; c<='Z'; ++c)
+ if( can(chocolates, c, s, e, maxSwaps) )
+ best = max(best, count(chocolates.begin()+s, chocolates.begin()+e, c));
+ return best;
+ }
+
+ bool can(const string& choco, char c, int s, int e, int k)
+ {
+ vector<int> z;
+ for(;;) {
+ int i = choco.find(c, s);
+ if(i>=e || i==string::npos)
+ i = e;
+
+ z.push_back(i-s);
+ if( i == e )
+ break;
+ s = i+1;
+ }
+ int needSwap = 0;
+ for(int i=0; i<z.size(); ++i)
+ needSwap += z[i] * min<int>(i, z.size()-1-i);
+ return needSwap <= k;
+ }
+};
+
+// 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(_, ColorfulChocolates().maximumSpread(chocolates, maxSwaps));}
+int main(){
+
+CASE(0)
+ string chocolates = "ABCDCBC";
+ int maxSwaps = 1;
+ int _ = 2;
+END
+CASE(1)
+ string chocolates = "ABCDCBC";
+ int maxSwaps = 2;
+ int _ = 3;
+END
+CASE(2)
+ string chocolates = "ABBABABBA";
+ int maxSwaps = 3;
+ int _ = 4;
+END
+CASE(3)
+ string chocolates = "ABBABABBA";
+ int maxSwaps = 4;
+ int _ = 5;
+END
+CASE(4)
+ string chocolates = "QASOKZNHWNFODOQNHGQKGLIHTPJUVGKLHFZTGPDCEKSJYIWFOO";
+ int maxSwaps = 77;
+ int _ = 5;
+END
+CASE(5)
+ string chocolates = "ABCDEBC";
+ int maxSwaps = 1;
+ int _ = 1;
+END
+/*
+CASE(6)
+ string chocolates = ;
+ int maxSwaps = ;
+ int _ = ;
+END
+*/
+}
+// END CUT HERE
ADDED SRM/551-U/1B.cpp
Index: SRM/551-U/1B.cpp
==================================================================
--- SRM/551-U/1B.cpp
+++ SRM/551-U/1B.cpp
@@ -0,0 +1,276 @@
+#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>
+using namespace std;
+typedef long long LL;
+typedef long double LD;
+typedef complex<LD> CMP;
+
+template<typename T>
+class IdGen
+{
+ map<T, int> v2id_;
+ vector<T> id2v_;
+public:
+ int v2id(const T& v) {
+ if( !v2id_.count(v) ) { v2id_[v] = size(); id2v_.push_back(v); }
+ return v2id_[v];
+ }
+ const T& id2v(int i) const { return id2v_[i]; }
+ int size() const { return id2v_.size(); }
+};
+
+template<typename Vert, typename Cost>
+class Dijkstra
+{
+ IdGen<Vert> idgen;
+
+ typedef pair<Cost,int> Edge;
+ typedef vector<Edge> Edges;
+ typedef vector<Edges> Graph;
+ Graph G;
+
+public:
+ void addEdge( Vert s_, Vert t_, Cost c )
+ {
+ int s = idgen.v2id(s_), t = idgen.v2id(t_);
+ if( max(s,t) >= G.size() ) G.resize(max(s,t)+1);
+ G[s].push_back(Edge(c, t));
+ }
+
+ Cost calc( Vert s_, Vert t_ )
+ {
+ int s = idgen.v2id(s_), t = idgen.v2id(t_);
+ if( max(s,t) >= G.size() ) G.resize(max(s,t)+1);
+
+ priority_queue< Edge, vector<Edge>, greater<Edge> > Q;
+ Q.push( Edge(0,s) );
+ vector<bool> visited(G.size());
+ while( !Q.empty() )
+ {
+ int v = Q.top().second;
+ Cost c = Q.top().first;
+ Q.pop();
+ if( visited[v] )
+ continue;
+ visited[v] = true;
+
+ if( v == t )
+ return c;
+
+ for(int i=0; i<G[v].size(); ++i)
+ if( !visited[G[v][i].second] )
+ Q.push( make_pair(G[v][i].first+c, G[v][i].second) );
+ }
+ return -1;
+ }
+};
+
+class ColorfulWolves { public:
+ int getmin(vector <string> colormap)
+ {
+ const int N = colormap.size();
+ Dijkstra<int, int> G;
+ for(int i=0; i<N; ++i)
+ for(int k=0,d=0; k<N; ++k)
+ if( colormap[i][k] == 'Y' )
+ G.addEdge(i, k, d++);
+ return G.calc(0, N-1);
+ }
+};
+
+// 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(_, ColorfulWolves().getmin(colormap));}
+int main(){
+
+CASE(0)
+ string colormap_[] = {"NYN","YNY","NNN"};
+ vector <string> colormap(colormap_, colormap_+sizeof(colormap_)/sizeof(*colormap_));
+ int _ = 1;
+END
+CASE(1)
+ string colormap_[] = {"NNNNNNNY","NNNNYYYY","YNNNNYYN","NNNNNYYY","YYYNNNNN","YNYNYNYN","NYNYNYNY","YYYYYYYN"};
+ vector <string> colormap(colormap_, colormap_+sizeof(colormap_)/sizeof(*colormap_));
+ int _ = 0;
+END
+CASE(2)
+ string colormap_[] = {"NYYYYN","YNYYYN","YYNYYN","YYYNYN","YYYYNN","YYYYYN"};
+ vector <string> colormap(colormap_, colormap_+sizeof(colormap_)/sizeof(*colormap_));
+ int _ = -1;
+END
+CASE(3)
+ string colormap_[] = {
+"NYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY",
+"YNYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY",
+"YYNYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY",
+"YYYNYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY",
+"YYYYNYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY",
+"YYYYYNYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY",
+"YYYYYYNYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY",
+"YYYYYYYNYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY",
+"YYYYYYYYNYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY",
+"YYYYYYYYYNYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY",
+"YYYYYYYYYYNYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY",
+"YYYYYYYYYYYNYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY",
+"YYYYYYYYYYYYNYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY",
+"YYYYYYYYYYYYYNYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY",
+"YYYYYYYYYYYYYYNYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY",
+"YYYYYYYYYYYYYYYNYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY",
+"YYYYYYYYYYYYYYYYNYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY",
+"YYYYYYYYYYYYYYYYYNYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY",
+"YYYYYYYYYYYYYYYYYYNYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY",
+"YYYYYYYYYYYYYYYYYYYNYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY",
+"YYYYYYYYYYYYYYYYYYYYNYYYYYYYYYYYYYYYYYYYYYYYYYYYYY",
+"YYYYYYYYYYYYYYYYYYYYYNYYYYYYYYYYYYYYYYYYYYYYYYYYYY",
+"YYYYYYYYYYYYYYYYYYYYYYNYYYYYYYYYYYYYYYYYYYYYYYYYYY",
+"YYYYYYYYYYYYYYYYYYYYYYYNYYYYYYYYYYYYYYYYYYYYYYYYYY",
+"YYYYYYYYYYYYYYYYYYYYYYYYNYYYYYYYYYYYYYYYYYYYYYYYYY",
+"YYYYYYYYYYYYYYYYYYYYYYYYYNYYYYYYYYYYYYYYYYYYYYYYYY",
+"YYYYYYYYYYYYYYYYYYYYYYYYYYNYYYYYYYYYYYYYYYYYYYYYYY",
+"YYYYYYYYYYYYYYYYYYYYYYYYYYYNYYYYYYYYYYYYYYYYYYYYYY",
+"YYYYYYYYYYYYYYYYYYYYYYYYYYYYNYYYYYYYYYYYYYYYYYYYYY",
+"YYYYYYYYYYYYYYYYYYYYYYYYYYYYYNYYYYYYYYYYYYYYYYYYYY",
+"YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYNYYYYYYYYYYYYYYYYYYY",
+"YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYNYYYYYYYYYYYYYYYYYY",
+"YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYNYYYYYYYYYYYYYYYYY",
+"YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYNYYYYYYYYYYYYYYYY",
+"YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYNYYYYYYYYYYYYYYY",
+"YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYNYYYYYYYYYYYYYY",
+"YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYNYYYYYYYYYYYYY",
+"YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYNYYYYYYYYYYYY",
+"YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYNYYYYYYYYYYY",
+"YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYNYYYYYYYYYY",
+"YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYNYYYYYYYYY",
+"YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYNYYYYYYYY",
+"YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYNYYYYYYY",
+"YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYNYYYYYY",
+"YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYNYYYYY",
+"YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYNYYYY",
+"YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYNYYY",
+"YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYNYY",
+"YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYNY",
+"YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYN"
+};
+ vector <string> colormap(colormap_, colormap_+sizeof(colormap_)/sizeof(*colormap_));
+ int _ = 48;
+END
+CASE(4)
+ string colormap_[] = {
+"NYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY",
+"YNYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY",
+"YYNYYYYYYYYYNNNNNYYYYYYNNNNNYYYYYNNYYYNNYYYYYYYYYY",
+"YYYNYYYYYYYNYYYYYYYYYYYNYYYYNYYYYNYNYNYNYYYYYYYYYY",
+"YNNNNYYYYYYNYYYYYYYYYYYNYYYYNYYYYNYNYNYNYYYYYYYYYY",
+"YYYYYNYYYYYYNNNNNYYYYYYNNNNNYYYYYNYYNYYNYYYYYYYYYY",
+"YYYYNNNNNYYYYYYYYNYYYYYNYYYNYYYYYNYYNYYNYYYYYYYYYY",
+"YYYYYYYNYYYYYYYYYNYYYYYNYYYYNYYYYNYYYYYNYYYYYYYYYY",
+"YYYYYYYYNYYYNNNNNYYYYYYNYYYYNYYYYNYYYYYNYYYYYYNYYY",
+"YYNNNYYYYNYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYNYYYY",
+"YYYYYYYYYYNYYNNNNNNNNYYYYYYYYNNNNNNYYYYYYYYYNNYYYY",
+"YYYYYYYYYYYNYYYYYYYYYYNNNNNNYNYYYYYYYYYYYYYYYNYYYY",
+"YYYNNNNNYYYYNYYYYYYYYYYYYYYYYYYYYNNNNNYYYYYNNYYYYY",
+"YYYYYYYYYYYYYNYYYYYNNNNYYYYYYNNNNNYYYYYNNNNYYYYYYY",
+"YYYYNNNNYYYYYYNYYYYYYYYYYYYYYYYYYYNNNNNYYYYYYYYYYY",
+"YYYYYYYYYYYYYYYNYYNNNNNNNNNYYYYYYYYYYYYYYYYYYYYYYY",
+"YYNNNNNNYYYYYYYYNYYYYYYYYYYYNNNNYYYYYYYYYYNNNNNYYY",
+"YYNYYYYYNNNYYYYYYNYYYYYYNNNNNNNNNYYYYYYYYYYYYYYYYY",
+"YYYYNYYYYYYYNNNYYYNYYYYYYYYYYYYYNNNNNNYYYYYYYYYYYY",
+"YYYYYYNYYYNNNNYYYYYNYYYYYYYYYYYYYYYYYNNNNNYYYYYYYY",
+"NNNNNYYYYYYYNYYYYYYYNYYYYYYYYYYYNNNNNNNNYYYYYYYYYY",
+"YYYYYYYYYYYYYNNNNYYYYNYYYNNNNYYYYYYYYYYYYNNNNNNYYY",
+"YYYYNNNYYYYNNNNYYYYYYYNYYYYYYYYYYYYYNNNNNNYYYYYYYY",
+"YYYYYYYYYYYYYYYYYYYYYYYNYYYNNNYYYYNNNNYYYYYYYYYYYY",
+"YYYYYYYYYNNNNNYYYYYYYYYYNYYYYYNNNNYYYYYYYYYYYYYYYY",
+"YYYNNNNYYYYYYYYYYYYYYYYYYNYYYYYNNNNYYYYYNNNNNYYYYY",
+"YYYYYYYYYYYNNNNNYYYYYYYYYYNYYYYYYYYYYNNNNNYYYYYYYY",
+"YYYNNNNNNYYYYYYNNNNNYYYYYYYNYYYYYYYYYYYYYYYYYYYYYY",
+"YYYYYNNNNNYYYYYYNNNNNYYYYYYYNYYYYYYYNNNNNNYYYYYYYY",
+"YYNNNNNYYYYYYYYYYYYYYYYYYYNNNNNNYYYYYYYYYYYYYNNNYY",
+"YYYYNNNNNYYYYYYYYYNNNNNNNNNYYYNYYYYYYNNNNNYYYYYYYY",
+"YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYNYYYNNNNNNYYYYYYYYY",
+"YYYYYYYYYYYYYNNNNNNYYYYYYNNNNNNYNYYYYYYYYYNNNYYYYN",
+"YYYYYNNNNNNNNYYYYYYNNNNNYYYYYYYYYNYYYYYYYYNNNNNYYY",
+"YYYYYYYYYYYYYYYYYYYYYYYYNNNNYYYYYYNYYYYYYYYYYYYYYY",
+"YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYNNNNNNNYYYYYYYNNNNNY",
+"YYYNNNNNNNNYYYNNNNNNNNYYYYNYYYYYYYYYNYYYYYYYYYYYYY",
+"YYYNYYYYYYYYYYNYYYYYYYYYNNNYYYYYYYYYYNYYYYYYYYYYYY",
+"YYYNYYYYYYYYYYNYYYYYYYYYYYNYYYYYYNNNNNNYYYNNNNNYYY",
+"YYYNYYYYYYYYYYNYYYYYYYYYYYNYYYYYYYYYYYYNYYYYYYYYYY",
+"YYYNYNNNNYYYYYNYNNNNYYYYYYNYYYYYYYYYNNNNNNYYYYYYYY",
+"YYYNNYYYYNYYYYNNYYYYNYYYYYNYYYYYYYYYYYYYYNYYYYYYYY",
+"YYYNYYYYYYNYYYNYYYYYYNYYYYNYYYYYYYYYYYYYYYNYYNNNNY",
+"YYYYYYYYYYNYYYYYYYYYYNYYYYNYYYYYNNNNNNYYYYYNYYYYYY",
+"YYYYYYYYYYNYYYYYYYYYYNYYYYNYYYYYYYYYYYNNNNNNNYYYYY",
+"YYYNYYYYYNYYYYNYYYYYNYYYYYNYYYNNNNNNNNNNNNYYYNYYYY",
+"YYYYNNNNNYYYYYYNNNNNYYYYNNNNNYYYNNNNNNYYYNNNNYNYYY",
+"YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYNYY",
+"YYYYNNNNYYYYNNNNNNNNNNNNYYYYYNNNNNNNNNYYYYYYYYYYNY",
+"YYYYYYNYYYYYYYYYYYYYYNYYYYYYYYYYYYYYYYYYYYYNYYYYYN"
+};
+ vector <string> colormap(colormap_, colormap_+sizeof(colormap_)/sizeof(*colormap_));
+ int _ = 35;
+END
+CASE(5)
+string colormap_[] = {"NN","NN"};
+ vector <string> colormap(colormap_, colormap_+sizeof(colormap_)/sizeof(*colormap_));
+ int _ = -1;
+END
+CASE(6)
+string colormap_[] = {"NY","YN"};
+ vector <string> colormap(colormap_, colormap_+sizeof(colormap_)/sizeof(*colormap_));
+ int _ = 0;
+END
+CASE(6)
+string colormap_[] = {
+ "NNNNNNNNNNYNNNNNNNYN",
+ "NNNNNNNNNNNNNNNNNNNN",
+ "NNNNNNNNNNNNNNNNNNNN",
+ "NNNNNNNNNNNNNNNNNNNN",
+ "NNNNNNNNNNNNNNNNNNNN",
+ "NNNNNNNNNNNNNNNNNNNN",
+ "NNNNNNNNNNNNNNNNNNNN",
+ "NNNNNNNNNNNNNNNNNNNN",
+ "NNNNNNNNNNNNNNNNNNNN",
+ "NNNNNNNNNNNNNNNNNNNN",
+ "YYYYYYYYYYNYNNNNNNNN",
+ "YYYYYYYYYYNNYNNNNNNN",
+ "YYYYYYYYYYNNNYNNNNNN",
+ "YYYYYYYYYYNNNNYNNNNN",
+ "YYYYYYYYYYNNNNNYNNNN",
+ "YYYYYYYYYYNNNNNNYNNN",
+ "YYYYYYYYYYNNNNNNNYNY",
+ "YYYYYYYYYYNNNNNNYNYN",
+ "YYYYYYYYYYNNNNNNYNYN",
+ "NNNNNNNNNNNNNNNNNNNN",
+};
+ vector <string> colormap(colormap_, colormap_+sizeof(colormap_)/sizeof(*colormap_));
+ int _ = 0;
+END
+
+}
+// END CUT HERE