ADDED   SRM/576-U/1A.cpp
Index: SRM/576-U/1A.cpp
==================================================================
--- SRM/576-U/1A.cpp
+++ SRM/576-U/1A.cpp
@@ -0,0 +1,158 @@
+#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 ArcadeManao { public:
+	int shortestLadder(vector <string> level, int coinRow, int coinColumn)
+	{
+		for(int L=0; L<=level.size(); ++L)
+			if(can(level, coinRow-1, coinColumn-1, L))
+				return L;
+		return level.size();
+	}
+
+	bool can(vector <string> level, int Cy, int Cx, int L)
+	{
+		int H = level.size();
+		int W = level[0].size();
+		typedef pair<int,int> point;
+		set<point> V;
+		queue<point> Q;
+		Q.push(point(H-1, 0));
+		V.insert(Q.front());
+		while(!Q.empty()) {
+			point p = Q.front();
+			int y=p.first, x=p.second;
+			Q.pop();
+			if(y==Cy && x==Cx)
+				return true;
+			vector<point> cand;
+			cand.push_back(point(y,x-1));
+			cand.push_back(point(y,x+1));
+			for(int dy=-L; dy<=+L; ++dy)
+				cand.push_back(point(y+dy, x));
+
+			for(int i=0; i<cand.size(); ++i) {
+				int yy = cand[i].first;
+				int xx = cand[i].second;
+				point pp(yy,xx);
+				if(0<=yy&&yy<H&&0<=xx&&xx<W&&level[y][x]=='X'&&!V.count(pp)) {
+					Q.push(pp);
+					V.insert(pp);
+				}
+			}
+		}
+		return false;
+	}
+};
+
+// 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(_, ArcadeManao().shortestLadder(level, coinRow, coinColumn));}
+int main(){
+
+CASE(0)
+	string level_[] = {"XXXX....",
+ "...X.XXX",
+ "XXX..X..",
+ "......X.",
+ "XXXXXXXX"};
+	  vector <string> level(level_, level_+sizeof(level_)/sizeof(*level_)); 
+	int coinRow = 2; 
+	int coinColumn = 4; 
+	int _ = 2; 
+END
+CASE(1)
+	string level_[] = {"XXXX",
+ "...X",
+ "XXXX"};
+	  vector <string> level(level_, level_+sizeof(level_)/sizeof(*level_)); 
+	int coinRow = 1; 
+	int coinColumn = 1; 
+	int _ = 1; 
+END
+CASE(2)
+	string level_[] = {"..X..",
+ ".X.X.",
+ "X...X",
+ ".X.X.",
+ "..X..",
+ "XXXXX"};
+	  vector <string> level(level_, level_+sizeof(level_)/sizeof(*level_)); 
+	int coinRow = 1; 
+	int coinColumn = 3; 
+	int _ = 4; 
+END
+CASE(3)
+	string level_[] = {"X"};
+	  vector <string> level(level_, level_+sizeof(level_)/sizeof(*level_)); 
+	int coinRow = 1; 
+	int coinColumn = 1; 
+	int _ = 0; 
+END
+CASE(4)
+	string level_[] = {"XXXXXXXXXX",
+ "...X......",
+ "XXX.......",
+ "X.....XXXX",
+ "..XXXXX..X",
+ ".........X",
+ ".........X",
+ "XXXXXXXXXX"};
+	  vector <string> level(level_, level_+sizeof(level_)/sizeof(*level_)); 
+	int coinRow = 1; 
+	int coinColumn = 1; 
+	int _ = 2; 
+END
+CASE(5)
+	string level_[] = {
+		"XXXXXXXXXXXXXXX",
+		"..............X",
+		"..............X",
+		"..............X",
+		"XXXXXXXXXXXXXXX",
+};
+	  vector <string> level(level_, level_+sizeof(level_)/sizeof(*level_)); 
+	int coinRow = 1; 
+	int coinColumn = 1; 
+	int _ = 1; 
+END
+/*
+CASE(6)
+	string level_[] = ;
+	  vector <string> level(level_, level_+sizeof(level_)/sizeof(*level_)); 
+	int coinRow = ; 
+	int coinColumn = ; 
+	int _ = ; 
+END
+*/
+}
+// END CUT HERE

ADDED   SRM/576-U/1B-U.cpp
Index: SRM/576-U/1B-U.cpp
==================================================================
--- SRM/576-U/1B-U.cpp
+++ SRM/576-U/1B-U.cpp
@@ -0,0 +1,200 @@
+#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;
+
+static const unsigned MODVAL = 1000000009;
+struct mint
+{
+	unsigned val;
+	mint():val(0){}
+	mint(int      x):val(x%MODVAL) {}
+	mint(unsigned x):val(x%MODVAL) {}
+	mint(LL       x):val(x%MODVAL) {}
+};
+mint& operator+=(mint& x, mint y) { return x = x.val+y.val; }
+mint& operator-=(mint& x, mint y) { return x = x.val-y.val+MODVAL; }
+mint& operator*=(mint& x, mint y) { return x = LL(x.val)*y.val; }
+mint operator+(mint x, mint y) { return x+=y; }
+mint operator-(mint x, mint y) { return x-=y; }
+mint operator*(mint x, mint y) { return x*=y; }
+
+template<typename T>
+struct DP4x
+{
+	int N1, N2, N3, N4;
+	vector<T> data;
+	DP4x(int, int N2, int N3, int N4, const T& t = T())
+		: N1(2), N2(N2), N3(N3), N4(N4), data(N1*N2*N3*N4, t) { assert(data.size()*sizeof(T)<(1<<26)); }
+	T& operator()(int i1, int i2, int i3, int i4)
+		{ i1&=1; return data[ (((i1*N2)+i2)*N3+i3)*N4+i4 ]; }
+	void swap(DP4x& rhs)
+		{ data.swap(rhs.data); }
+};
+
+class TheExperiment { public:
+	int countPlacements(vector <string> intensity, int M, int L, int A, int B)
+	{
+		string S = accumulate(intensity.begin(), intensity.end(), string());
+		int N = S.size();
+
+		vector<int> range_L, range_R; // [L,R)
+		{
+			vector<int> PS(N+1, 0);
+			for(int i=0; i<N; ++i)
+				PS[i+1] = PS[i] + (S[i]-'0');
+			for(int i=0; i<N; ++i)
+			{
+				int LL = PS[i]+A;
+				int RR = PS[i]+B+1;
+				range_L.push_back(lower_bound(PS.begin(), PS.end(), LL) - PS.begin());
+				range_R.push_back(lower_bound(PS.begin(), PS.end(), RR) - PS.begin());
+				//cerr<<i<<" ["<<range_L.back()<<"-"<<range_R.back()<<")"<<" "<<LL<<","<<RR<<endl;
+			}
+		}
+
+		DP4x<mint> dp(M+1, N+1, M, 2);
+		dp(0, 0, 0, 0) = 1;
+		for(int i=0; i<M; ++i)
+		{
+			// Clear
+			for(int x=0; x<=N; ++x)
+			for(int rank=0; rank<M; ++rank) {
+			for(int hami=0; hami<2; ++hami) {
+				if(dp(i,x,rank,hami).val)
+				cerr<<i<<" "<<x<<" "<<rank<<" "<<hami<<" : "<< dp(i,x,rank,hami).val<<endl;
+				dp(i+1, x, rank, hami) = 0;
+			}
+
+			// DP
+			for(int x=0; x<N; ++x)
+			for(int rank=0; rank<=i; ++rank)
+			for(int hami=0; hami<2; ++hami)
+			{
+				mint v = dp(i,x,rank,hami);
+				if(v.val != 0)
+					for(int y=range_L[x]; y<range_R[x]; ++y)
+					{
+						if(y-x < L) {
+							if(hami) {
+								for(int r=0; r<=rank; ++r)
+									dp(i+1, y, a) += v;
+							} else {
+							}
+						} else if(y-x == L) {
+							if(hami)
+								dp(i+1, y, i, 0) += v * (rank+1);
+							else
+								dp(i+1, y, i, 0) += v * (rank+1);
+						} else {
+							break;
+						}
+					}
+			}
+		}
+		mint acc = 0;
+		for(int rank=0; rank<M; ++rank)
+			acc += dp(M, N, rank, 0);
+		return acc.val;
+	}
+};
+
+// 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(_, TheExperiment().countPlacements(intensity, M, L, A, B));}
+int main(){
+
+CASE(0)
+	string intensity_[] = {"341156"};
+	  vector <string> intensity(intensity_, intensity_+sizeof(intensity_)/sizeof(*intensity_)); 
+	int M = 3; 
+	int L = 3; 
+	int A = 6; 
+	int B = 10; 
+	int _ = 2; 
+END
+CASE(1)
+	string intensity_[] = {"999112999"};
+	  vector <string> intensity(intensity_, intensity_+sizeof(intensity_)/sizeof(*intensity_)); 
+	int M = 2; 
+	int L = 4; 
+	int A = 21; 
+	int B = 30; 
+	int _ = 2; 
+END
+CASE(2)
+	string intensity_[] = {"111"};
+	  vector <string> intensity(intensity_, intensity_+sizeof(intensity_)/sizeof(*intensity_)); 
+	int M = 2; 
+	int L = 2; 
+	int A = 2; 
+	int B = 3; 
+	int _ = 0; 
+END
+CASE(3)
+	string intensity_[] = {"59059", "110", "1132230231"};
+	  vector <string> intensity(intensity_, intensity_+sizeof(intensity_)/sizeof(*intensity_)); 
+	int M = 1; 
+	int L = 5; 
+	int A = 10; 
+	int B = 20; 
+	int _ = 6; 
+END
+CASE(4)
+	string intensity_[] = {"111111111111111111111111", "111111111111111111111111111", "11111111111111111111111"};
+	  vector <string> intensity(intensity_, intensity_+sizeof(intensity_)/sizeof(*intensity_)); 
+	int M = 12; 
+	int L = 8; 
+	int A = 4; 
+	int B = 2700; 
+	int _ = 418629948; 
+END
+/*
+CASE(5)
+	string intensity_[] = ;
+	  vector <string> intensity(intensity_, intensity_+sizeof(intensity_)/sizeof(*intensity_)); 
+	int M = ; 
+	int L = ; 
+	int A = ; 
+	int B = ; 
+	int _ = ; 
+END
+CASE(6)
+	string intensity_[] = ;
+	  vector <string> intensity(intensity_, intensity_+sizeof(intensity_)/sizeof(*intensity_)); 
+	int M = ; 
+	int L = ; 
+	int A = ; 
+	int B = ; 
+	int _ = ; 
+END
+*/
+}
+// END CUT HERE