ADDED   SRM/563/1A.cpp
Index: SRM/563/1A.cpp
==================================================================
--- SRM/563/1A.cpp
+++ SRM/563/1A.cpp
@@ -0,0 +1,111 @@
+#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 FoxAndHandle { public:
+	string lexSmallestName(string S)
+	{
+		string cur = "";
+		int p = 0;
+		while(cur.size()*2<S.size()) {
+			string next_best;
+			int next_p = -1;
+			for(int x=p; x<S.size(); ++x)
+				if(possible(cur+S[x], x+1, S)) {
+					if(next_p==-1 || next_best>cur+S[x])
+						next_best=cur+S[x], next_p=x+1;
+				}
+			cur = next_best;
+			p = next_p;
+		}
+		return cur;
+	}
+
+	bool possible(const string& used, int x, const string& S)
+	{
+		int freq[26] = {0};
+		int pos[26] = {0};
+		int tot[26] = {0};
+		for(int i=0; i<used.size(); ++i)
+			freq[used[i]-'a']++;
+		for(int i=0; i<S.size(); ++i) {
+			if(x<=i)
+				pos[S[i]-'a']++;
+			tot[S[i]-'a']++;
+		}
+		for(int c=0; c<26; ++c)
+			if((freq[c]+pos[c])*2<tot[c] || freq[c]*2>tot[c])
+				return false;
+		return true;
+	}
+};
+
+// 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 string& Expected, const string& 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(_, FoxAndHandle().lexSmallestName(S));}
+int main(){
+
+CASE(0)
+	string S = "foxfox"; 
+	string _ = "fox"; 
+END
+CASE(1)
+	string S = "ccieliel"; 
+	string _ = "ceil"; 
+END
+CASE(2)
+	string S = "abaabbab"; 
+	string _ = "aabb"; 
+END
+CASE(3)
+	string S = "bbbbaaaa"; 
+	string _ = "bbaa"; 
+END
+CASE(4)
+	string S = "fedcbafedcba"; 
+	string _ = "afedcb"; 
+END
+CASE(5)
+	string S = "nodevillivedon"; 
+	string _ = "deilvon"; 
+END
+/*
+CASE(6)
+	string S = ; 
+	string _ = ; 
+END
+CASE(7)
+	string S = ; 
+	string _ = ; 
+END
+*/
+}
+// END CUT HERE

ADDED   SRM/563/1B.cpp
Index: SRM/563/1B.cpp
==================================================================
--- SRM/563/1B.cpp
+++ SRM/563/1B.cpp
@@ -0,0 +1,159 @@
+#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>
+struct DP2
+{
+	const int N1, N2;
+	vector<T> data;
+	DP2(int N1, int N2, const T& t = T())
+		: N1(N1), N2(N2), data(N1*N2, t) { assert(data.size()*sizeof(T)<(1<<26)); }
+	T& operator()(int i1, int i2)
+		{ return data[ (i1*N2)+i2 ]; }
+	void swap(DP2& rhs)
+		{ data.swap(rhs.data); }
+};
+
+class SpellCards { public:
+	int maxDamage(vector <int> level, vector <int> damage)
+	{
+		static const int IMPOSSIBLE = -99999999;
+
+		int N = level.size();
+		DP2<int> dp(N, N+1, IMPOSSIBLE);
+		for(int w=1; w<=N; ++w)
+		for(int s=0; s<N; ++s) {
+			int L = level[s];
+			int D = damage[s];
+
+			DP2<int> ip(L+1, w, IMPOSSIBLE);
+			ip(1,0) = D;
+			for(int c=1; c<=L; ++c)
+			for(int k=1; k<w; ++k) {
+				int sk = (s+k) % N;
+
+				int v = ip(c-1,k-1);
+				for(int p=1; p<=k; ++p) {
+					int sp = (s+p) % N;
+					v = max(v, ip(c,p-1) + dp(sp, k-p+1));
+				}
+				ip(c,k) = v;
+			}
+
+			dp(s,w) = ip(L, w-1);
+		}
+
+		int theBest = 0;
+		for(int s=0; s<N; ++s)
+		{
+			vector<int> best(N+1);
+			for(int k=0; k<N; ++k) {
+				best[k+1] = best[k];
+				for(int p=0; p<=k; ++p)
+					best[k+1] = max(best[k+1], best[p] + dp((s+p)%N, k-p+1));
+			}
+			theBest = max(theBest, best[N]);
+		}
+		return theBest;
+	}
+};
+
+// 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(_, SpellCards().maxDamage(level, damage));}
+int main(){
+
+CASE(0)
+	int level_[] = {1,1,1};
+	  vector <int> level(level_, level_+sizeof(level_)/sizeof(*level_)); 
+	int damage_[] = {10,20,30};
+	  vector <int> damage(damage_, damage_+sizeof(damage_)/sizeof(*damage_)); 
+	int _ = 60; 
+END
+CASE(1)
+	int level_[] = {3,3,3};
+	  vector <int> level(level_, level_+sizeof(level_)/sizeof(*level_)); 
+	int damage_[] = {10,20,30};
+	  vector <int> damage(damage_, damage_+sizeof(damage_)/sizeof(*damage_)); 
+	int _ = 30; 
+END
+CASE(2)
+	int level_[] = {4,4,4};
+	  vector <int> level(level_, level_+sizeof(level_)/sizeof(*level_)); 
+	int damage_[] = {10,20,30};
+	  vector <int> damage(damage_, damage_+sizeof(damage_)/sizeof(*damage_)); 
+	int _ = 0; 
+END
+CASE(3)
+	int level_[] = {50,1,50,1,50};
+	  vector <int> level(level_, level_+sizeof(level_)/sizeof(*level_)); 
+	int damage_[] = {10,20,30,40,50};
+	  vector <int> damage(damage_, damage_+sizeof(damage_)/sizeof(*damage_)); 
+	int _ = 60; 
+END
+CASE(4)
+	int level_[] = {2,1,1};
+	  vector <int> level(level_, level_+sizeof(level_)/sizeof(*level_)); 
+	int damage_[] = {40,40,10};
+	  vector <int> damage(damage_, damage_+sizeof(damage_)/sizeof(*damage_)); 
+	int _ = 80; 
+END
+CASE(5)
+	int level_[] = {1,2,1,1,3,2,1};
+	  vector <int> level(level_, level_+sizeof(level_)/sizeof(*level_)); 
+	int damage_[] = {10,40,10,10,90,40,10};
+	  vector <int> damage(damage_, damage_+sizeof(damage_)/sizeof(*damage_)); 
+	int _ = 170; 
+END
+CASE(6)
+	int level_[] = {1,2,2,3,1,4,2};
+	  vector <int> level(level_, level_+sizeof(level_)/sizeof(*level_)); 
+	int damage_[] = {113,253,523,941,250,534,454};
+	  vector <int> damage(damage_, damage_+sizeof(damage_)/sizeof(*damage_)); 
+	int _ = 1918; 
+END
+CASE(7)
+	int level_[] = {4,8,50,24,4,32,6,39,3,2,4,4,39,39,10,3,42,36,38,18,6,18,41,15,28,40,45,26,40,30,25,46,18,35,29,25,48,10,18,25,46,33,30,26,36,8,20,35,28,29};
+	  vector <int> level(level_, level_+sizeof(level_)/sizeof(*level_)); 
+	int damage_[] = {8577,2855,8317,7176,295,7028,5317,7099,4642,29,2481,7249,5387,6266,6241,4550,9178,2375,1037,4438,4189,5886,5285,3583,2874,8484,4725,2096,7560,4057,988,5914,3460,1305,6223,2305,6229,2719,2404,6454,278,5242,2948,9607,1302,4263,3366,4925,8381,3692};
+	  vector <int> damage(damage_, damage_+sizeof(damage_)/sizeof(*damage_)); 
+	int _ = -2; 
+END
+CASE(8)
+	int level_[] = {25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25};
+	  vector <int> level(level_, level_+sizeof(level_)/sizeof(*level_)); 
+	int damage_[] = {8577,2855,8317,7176,295,7028,5317,7099,4642,29,2481,7249,5387,6266,6241,4550,9178,2375,1037,4438,4189,5886,5285,3583,2874,8484,4725,2096,7560,4057,988,5914,3460,1305,6223,2305,6229,2719,2404,6454,278,5242,2948,9607,1302,4263,3366,4925,8381,3692};
+	  vector <int> damage(damage_, damage_+sizeof(damage_)/sizeof(*damage_)); 
+	int _ = -2; 
+END
+}
+// END CUT HERE

ADDED   SRM/563/1C.cpp
Index: SRM/563/1C.cpp
==================================================================
--- SRM/563/1C.cpp
+++ SRM/563/1C.cpp
@@ -0,0 +1,346 @@
+#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; }
+mint POW(mint x, LL e) { mint v=1; for(;e;x*=x,e>>=1) if(e&1) v*=x; return v; }
+
+class CoinsGame { public:
+	int ways(vector <string> board)
+	{
+		map<pair<int,int>,int> ID;
+		for(int y=0; y<board.size(); ++y)
+		for(int x=0; x<board[0].size(); ++x)
+		if(board[y][x]=='.') {
+			int id = ID.size() + 1;
+			ID[make_pair(y,x)] = id;
+		}
+
+		vector< vector<int> > G(ID.size()+1);
+		G[0] = vector<int>(4, 0);
+
+		int H = board.size();
+		int W = board[0].size();
+		for(int y=0; y<board.size(); ++y)
+		for(int x=0; x<board[0].size(); ++x)
+		if(board[y][x]=='.')
+		{
+			int dy[]={-1,+1,0,0};
+			int dx[]={0,0,-1,+1};
+			for(int d=0; d<4; ++d)
+			{
+				int yy=y+dy[d], xx=x+dx[d];
+				if(yy<0||H<=yy||xx<0||W<=xx) {
+					// fell
+					G[ID[make_pair(y,x)]].push_back(0); // 0=fall
+				}
+				else if(board[yy][xx]=='#') {
+					// stop at yy-dy[d], xx-dx[d]
+					G[ID[make_pair(y,x)]].push_back(ID[make_pair(y,x)]);
+				}
+				else {
+					G[ID[make_pair(y,x)]].push_back(ID[make_pair(yy,xx)]);
+				}
+			}
+		}
+		return solve(G).val;
+	}
+
+	mint solve(vector< vector<int> >& G)
+	{
+		vector< vector<int> > set_buffer;
+		set<int> active_sets;
+		set<int> active_splitters;
+
+		{
+			set_buffer.push_back( vector<int>(1,0) );
+			vector<int> all;
+			for(int v=1; v<G.size(); ++v)
+				all.push_back(v);
+			set_buffer.push_back(all);
+
+			active_sets.insert(0);
+			active_sets.insert(1);
+			active_splitters.insert(0);
+		}
+
+		while(!active_splitters.empty())
+		{
+			const vector<int>& splv = set_buffer[*active_splitters.begin()];
+			set<int> spl(splv.begin(), splv.end());
+			active_splitters.erase(active_splitters.begin());
+
+			for(int d=0; d<4; ++d)
+			for(set<int>::iterator it=active_sets.begin(); it!=active_sets.end(); )
+			{
+				int ii = *it++;
+				const vector<int>& cur = set_buffer[ii];
+				vector<int> t, f;
+				for(int k=0; k<cur.size(); ++k)
+					(spl.count(G[cur[k]][d]) ? t : f).push_back(cur[k]);
+				if(!t.empty() && !f.empty())
+				{
+					set_buffer.push_back(t);
+					set_buffer.push_back(f);
+					active_sets.insert(set_buffer.size()-2);
+					active_sets.insert(set_buffer.size()-1);
+					if(active_splitters.count(ii)) {
+						active_splitters.insert(set_buffer.size()-2);
+						active_splitters.insert(set_buffer.size()-1);
+					} else {
+						active_splitters.insert(t.size()<f.size() ? set_buffer.size()-2 : set_buffer.size()-1);
+					}
+					active_splitters.erase(ii);
+					active_sets.erase(ii);
+				}
+			}
+		}
+
+		vector<int> es;
+		for(set<int>::iterator it=active_sets.begin(); it!=active_sets.end(); ++it)
+			if(*it)
+				es.push_back(set_buffer[*it].size());
+/*
+		for(bool changed=true; changed;) 
+		{
+			changed=false;
+			for(int i=0; i<eqs.size(); ++i) if(!eqs[i].second && !dead[i]){
+				set<int> spl(eqs[i].first.begin(), eqs[i].first.end());
+				eqs[i].second = true;
+				for(int k=0; k<eqs.size(); ++k)
+				for(int d=0; d<4; ++d) if(!dead[k]) {
+					vector<int> t, f;
+					for(vector<int>::iterator it=eqs[k].first.begin(); it!=eqs[k].first.end(); ++it)
+						(spl.count(G[*it][d]) ? t : f).push_back(*it);
+					if(!t.empty() && !f.empty()) {
+						if(eqs[k].second) {
+							eqs.push_back(make_pair(t,t.size()>f.size()));
+							eqs.push_back(make_pair(f,t.size()<=f.size()));
+							dead.push_back(false);
+							dead.push_back(false);
+							changed = true;
+						} else {
+							eqs.push_back(make_pair(t,false));
+							eqs.push_back(make_pair(f,false));
+							dead.push_back(false);
+							dead.push_back(false);
+							changed = true;
+						}
+						dead[k] = true;
+					}
+				}
+			}
+		}
+
+		vector<int> es;
+		for(int i=1; i<eqs.size(); ++i) if(!dead[i]) 
+			es.push_back(eqs[i].first.size());
+*/
+		int sum = accumulate(es.begin(), es.end(), 0);
+		mint x = POW(2, sum);
+		for(int i=0; i<es.size(); ++i)
+			x -= POW(2, es[i])-1;
+		return x-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(_, CoinsGame().ways(board));}
+int main(){
+
+CASE(0)
+	string board_[] = {".."};
+	  vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); 
+	int _ = 1; 
+END
+CASE(1)
+	string board_[] = {"##.#",
+ ".###",
+ "###.",
+ "#.##"};
+	  vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); 
+	int _ = 11; 
+END
+CASE(2)
+	string board_[] = {"####",
+ "#..#",
+ "#..#",
+ "####"};
+	  vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); 
+	int _ = 0; 
+END
+CASE(3)
+	string board_[] = {"#.#.#"};
+	  vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); 
+	int _ = 0; 
+END
+CASE(4)
+	string board_[] = {"........",
+ "........",
+ "........",
+ "........",
+ "........",
+ "........",
+ "........",
+ "........"};
+	  vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); 
+	int _ = 688856388; 
+END
+CASE(5)
+	string board_[] = {"........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................", "........................................"};
+	  vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); 
+	int _ = 150087966; 
+END
+CASE(5)
+	string board_[] = {"........................................",
+ "........................................", 
+ "........................................",
+ "........................................",
+ "........................................",
+ "........................................",
+ "........................................",
+ "........................................",
+ "........................................",
+ "........................................",
+ "........................................",
+ "........................................", 
+ "........................................",
+ "........................................",
+ "........................................",
+ "........................................",
+ "........................................",
+ "........................................",
+ "........................................",
+ "........................................",};
+	  vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); 
+	int _ = 150087966; 
+END
+CASE(5)
+	string board_[] = {"........................................",
+ "........................................", 
+ "........................................",
+ "........................................",
+ "........................................",
+ "........................................",
+ "........................................",
+ "........................................",
+ "........................................",
+ "........................................",
+ "........................................",
+ "........................................", 
+ "........................................",
+ "........................................",
+ "........................................",
+ "........................................",
+ "........................................",
+ "........................................",
+ "........................................",
+ "........................................",
+"........................................",
+ "........................................", 
+ "........................................",
+ "........................................",
+ "........................................",
+ "........................................",
+ "........................................",
+ "........................................",
+ "........................................",
+ "........................................",
+ "........................................",
+ "........................................", 
+ "........................................",
+ "........................................",
+ "........................................",
+ "........................................",
+ "........................................",
+ "........................................",
+ "........................................",
+ "........................................",
+"........................................",
+ "........................................", 
+ "........................................",
+ "........................................",
+ "........................................",
+ "........................................",
+ "........................................",
+ "........................................",
+ "........................................",
+ "........................................",
+ "........................................",
+ "........................................", 
+ "........................................",
+ "........................................",
+ "........................................",
+ "........................................",
+ "........................................",
+ "........................................",
+ "........................................",
+ "........................................",
+"........................................",
+ "........................................", 
+ "........................................",
+ "........................................",
+ "........................................",
+ "........................................",
+ "........................................",
+ "........................................",
+ "........................................",
+ "........................................",
+ "........................................",
+ "........................................", 
+ "........................................",
+ "........................................",
+ "........................................",
+ "........................................",
+ "........................................",
+ "........................................",
+ "........................................",
+ "........................................",};
+	  vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); 
+	int _ = 150087966; 
+END
+}
+// END CUT HERE