ADDED SRM/558-U/1A.cpp
Index: SRM/558-U/1A.cpp
==================================================================
--- SRM/558-U/1A.cpp
+++ SRM/558-U/1A.cpp
@@ -0,0 +1,115 @@
+#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 Stamp { public:
+ int getMinimumCost(string desiredColor, int stampCost, int pushCost)
+ {
+ const int N = desiredColor.size();
+
+ int best = 0x7fffffff;
+ for(int L=1; L<=N; ++L) {
+ vector<int> dp(N+1, 999);
+ dp[0] = 0;
+ for(int e=1; e<=N; ++e) {
+ set<char> colors;
+ for(int s=e-1; s>=0; --s) {
+ if(desiredColor[s] != '*')
+ colors.insert(desiredColor[s]);
+ if(colors.size()<=1 && e-s>=L) {
+ int nPush = (e-s+L-1)/L;
+ dp[e] = min(dp[e], dp[s]+nPush);
+ }
+ }
+ }
+ best = min(best, L*stampCost + dp[N]*pushCost);
+ }
+ return best;
+ }
+};
+
+// 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(_, Stamp().getMinimumCost(desiredColor, stampCost, pushCost));}
+int main(){
+
+CASE(0)
+ string desiredColor = "RRGGBB";
+ int stampCost = 1;
+ int pushCost = 1;
+ int _ = 5;
+END
+CASE(1)
+ string desiredColor = "R**GB*";
+ int stampCost = 1;
+ int pushCost = 1;
+ int _ = 5;
+END
+CASE(2)
+ string desiredColor = "BRRB";
+ int stampCost = 2;
+ int pushCost = 7;
+ int _ = 30;
+END
+CASE(3)
+ string desiredColor = "R*RR*GG";
+ int stampCost = 10;
+ int pushCost = 58;
+ int _ = 204;
+END
+CASE(4)
+ string desiredColor = "*B**B**B*BB*G*BBB**B**B*";
+ int stampCost = 5;
+ int pushCost = 2;
+ int _ = 33;
+END
+CASE(5)
+ string desiredColor = "*R*RG*G*GR*RGG*G*GGR***RR*GG";
+ int stampCost = 7;
+ int pushCost = 1;
+ int _ = 30;
+END
+/*
+CASE(6)
+ string desiredColor = ;
+ int stampCost = ;
+ int pushCost = ;
+ int _ = ;
+END
+CASE(7)
+ string desiredColor = ;
+ int stampCost = ;
+ int pushCost = ;
+ int _ = ;
+END
+*/
+}
+// END CUT HERE
ADDED SRM/558-U/1B.cpp
Index: SRM/558-U/1B.cpp
==================================================================
--- SRM/558-U/1B.cpp
+++ SRM/558-U/1B.cpp
@@ -0,0 +1,157 @@
+#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 Ear { public:
+ long long getCount(vector <string> redX, vector <string> blueX, vector <string> blueY)
+ {
+ vector<int> rx, bx, by;
+ {
+ stringstream sin(accumulate(redX.begin(), redX.end(), string("")));
+ for(int x; sin>>x; ) rx.push_back(x);
+ }
+ {
+ stringstream sin(accumulate(blueX.begin(), blueX.end(), string("")));
+ for(int x; sin>>x; ) bx.push_back(x);
+ }
+ {
+ stringstream sin(accumulate(blueY.begin(), blueY.end(), string("")));
+ for(int y; sin>>y; ) by.push_back(y);
+ }
+ int B = bx.size();
+
+ LL total = 0;
+ for(int p=0; p<B; ++p)
+ for(int q=0; q<B; ++q)
+ if(by[p] > by[q])
+ {
+ int px=bx[p], py=by[p], qx=bx[q], qy=by[q];
+ LL a=0, b=0, c=0, d=0;
+ for(int i=0; i<rx.size(); ++i)
+ {
+ int x = rx[i];
+ double z = px + (qx-px)*py/double(py-qy);
+ if(x<min<double>(z,px))
+ ++a;
+ if(min<double>(z,px)<=x && x<qx)
+ ++b;
+ if(qx<x && x<=max<double>(z,px))
+ ++c;
+ if(max<double>(z,px)<x)
+ ++d;
+ }
+ total += (a*(a-1)/2+a*b) * (d*(d-1)/2+d*c);
+ }
+ return total;
+ }
+};
+
+// 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 long long& Expected, const long long& 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(_, Ear().getCount(redX, blueX, blueY));}
+int main(){
+
+CASE(0)
+ string redX_[] = {"3 2 8 7"};
+ vector <string> redX(redX_, redX_+sizeof(redX_)/sizeof(*redX_));
+ string blueX_[] = {"5 4"};
+ vector <string> blueX(blueX_, blueX_+sizeof(blueX_)/sizeof(*blueX_));
+ string blueY_[] = {"2 4"};
+ vector <string> blueY(blueY_, blueY_+sizeof(blueY_)/sizeof(*blueY_));
+ long long _ = 1LL;
+END
+CASE(1)
+ string redX_[] = {"3 2 8 7"};
+ vector <string> redX(redX_, redX_+sizeof(redX_)/sizeof(*redX_));
+ string blueX_[] = {"2 8"};
+ vector <string> blueX(blueX_, blueX_+sizeof(blueX_)/sizeof(*blueX_));
+ string blueY_[] = {"3 4"};
+ vector <string> blueY(blueY_, blueY_+sizeof(blueY_)/sizeof(*blueY_));
+ long long _ = 0LL;
+END
+CASE(2)
+ string redX_[] = {"1 2 6 9"};
+ vector <string> redX(redX_, redX_+sizeof(redX_)/sizeof(*redX_));
+ string blueX_[] = {"3 6 8 5"};
+ vector <string> blueX(blueX_, blueX_+sizeof(blueX_)/sizeof(*blueX_));
+ string blueY_[] = {"1 5 4 3"};
+ vector <string> blueY(blueY_, blueY_+sizeof(blueY_)/sizeof(*blueY_));
+ long long _ = 4LL;
+END
+CASE(3)
+ string redX_[] = {"10000"};
+ vector <string> redX(redX_, redX_+sizeof(redX_)/sizeof(*redX_));
+ string blueX_[] = {"10000 9999"};
+ vector <string> blueX(blueX_, blueX_+sizeof(blueX_)/sizeof(*blueX_));
+ string blueY_[] = {"10000 9999"};
+ vector <string> blueY(blueY_, blueY_+sizeof(blueY_)/sizeof(*blueY_));
+ long long _ = 0LL;
+END
+CASE(4)
+ string redX_[] = {"100 2", "00", " 39", "9", " 800 900 9", "99"};
+ vector <string> redX(redX_, redX_+sizeof(redX_)/sizeof(*redX_));
+ string blueX_[] = {"15", "0 250 ", "349"};
+ vector <string> blueX(blueX_, blueX_+sizeof(blueX_)/sizeof(*blueX_));
+ string blueY_[] = {"2 3 1"};
+ vector <string> blueY(blueY_, blueY_+sizeof(blueY_)/sizeof(*blueY_));
+ long long _ = 12LL;
+END
+CASE(5)
+ string redX_[] = {"1", " ", "2", " ", "3", " ", "4 5 6", " 7 8 9"};
+ vector <string> redX(redX_, redX_+sizeof(redX_)/sizeof(*redX_));
+ string blueX_[] = {"4", " ", "5", " ", "6", " 7 ", "8"};
+ vector <string> blueX(blueX_, blueX_+sizeof(blueX_)/sizeof(*blueX_));
+ string blueY_[] = {"1", " 2 ", "3 4", " 5"};
+ vector <string> blueY(blueY_, blueY_+sizeof(blueY_)/sizeof(*blueY_));
+ long long _ = 204LL;
+END
+/*
+CASE(6)
+ string redX_[] = ;
+ vector <string> redX(redX_, redX_+sizeof(redX_)/sizeof(*redX_));
+ string blueX_[] = ;
+ vector <string> blueX(blueX_, blueX_+sizeof(blueX_)/sizeof(*blueX_));
+ string blueY_[] = ;
+ vector <string> blueY(blueY_, blueY_+sizeof(blueY_)/sizeof(*blueY_));
+ long long _ = LL;
+END
+CASE(7)
+ string redX_[] = ;
+ vector <string> redX(redX_, redX_+sizeof(redX_)/sizeof(*redX_));
+ string blueX_[] = ;
+ vector <string> blueX(blueX_, blueX_+sizeof(blueX_)/sizeof(*blueX_));
+ string blueY_[] = ;
+ vector <string> blueY(blueY_, blueY_+sizeof(blueY_)/sizeof(*blueY_));
+ long long _ = LL;
+END
+ */
+}
+// END CUT HERE