ADDED   SRM/515/1A.cpp
Index: SRM/515/1A.cpp
==================================================================
--- SRM/515/1A.cpp
+++ SRM/515/1A.cpp
@@ -0,0 +1,100 @@
+#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>
+#include <cstring>
+using namespace std;
+typedef long long LL;
+typedef complex<double> CMP;
+
+class RotatedClock { public:
+	string getEarliest(int hourHand, int minuteHand)
+	{
+		for(int h=0; h<12; ++h)
+			for(int m=0; m<60; ++m)
+				for(int offset=0; offset<360; offset+=30) {
+					int hx = (hourHand + offset) % 360;
+					int mx = (minuteHand + offset) % 360;
+					if( match(h, m, hx, mx) ) {
+						char buf[100];
+						sprintf(buf, "%02d:%02d", h, m);
+						return buf;
+					}
+				}
+		return string();
+	}
+
+	bool match(int h, int m, int hx, int mx)
+	{
+		return (h*60+m)*360 == hx*(12*60)
+			&& m*360 == mx*60;
+	}
+};
+
+// 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(_, RotatedClock().getEarliest(hourHand, minuteHand));}
+int main(){
+
+CASE(0)
+	int hourHand = 70; 
+	int minuteHand = 300; 
+	string _ = "08:20"; 
+END
+CASE(1)
+	int hourHand = 90; 
+	int minuteHand = 120; 
+	string _ = "11:00"; 
+END
+CASE(2)
+	int hourHand = 240; 
+	int minuteHand = 36; 
+	string _ = ""; 
+END
+CASE(3)
+	int hourHand = 19; 
+	int minuteHand = 19; 
+	string _ = ""; 
+END
+CASE(4)
+	int hourHand = 1; 
+	int minuteHand = 12; 
+	string _ = "00:02"; 
+END
+/*
+CASE(5)
+	int hourHand = ; 
+	int minuteHand = ; 
+	string _ = ; 
+END
+CASE(6)
+	int hourHand = ; 
+	int minuteHand = ; 
+	string _ = ; 
+END
+*/
+}
+// END CUT HERE

ADDED   SRM/515/1B.cpp
Index: SRM/515/1B.cpp
==================================================================
--- SRM/515/1B.cpp
+++ SRM/515/1B.cpp
@@ -0,0 +1,142 @@
+#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>
+#include <cstring>
+using namespace std;
+typedef long long LL;
+typedef complex<double> CMP;
+
+struct Event
+{
+	int i, T, C, P;
+	double P_total;
+	bool has_next;
+	Event(int i, int T, int C, int P) : i(i), T(T), C(C), P(P) {}
+	bool operator<(const Event& rhs) const { return T < rhs.T; }
+};
+
+class NewItemShop { public:
+	double getMaximum(int swords, vector <string> customers)
+	{
+		vector<Event> ev;
+		for(size_t i=0; i<customers.size(); ++i)
+		{
+			for(size_t k=0; k<customers[i].size(); ++k)
+				if( customers[i][k] == ',' )
+					customers[i][k] = ' ';
+			stringstream ss(customers[i]);
+			for(int T,C,P; ss>>T>>C>>P; )
+				ev.push_back(Event((int)i,T,C,P));
+		}
+		sort(ev.begin(), ev.end());
+		for(int i=0; i<ev.size(); ++i)
+		{
+			ev[i].P_total = 100;
+			ev[i].has_next = false;
+			for(int k=i+1; k<ev.size(); ++k)
+				if( ev[k].i == ev[i].i )
+					ev[i].has_next = true;
+			for(int k=i-1; k>=0; --k)
+				if( ev[k].i == ev[i].i )
+					ev[i].P_total -= ev[k].P;
+		}
+		return rec(0, ev, swords, 0);
+	}
+
+	map<int, double> memo;
+	double rec(int i, const vector<Event>& ev, int swords, int mask)
+	{
+		if( i==ev.size() || swords==0 )
+			return 0;
+		int key = (mask*ev.size() + i) * 25 + swords;
+		if( memo.count(key) )
+			return memo[key];
+
+		const int ID = ev[i].i;
+		const double C = ev[i].C;
+		const double P = ev[i].P / ev[i].P_total;
+		const int newmask = (ev[i].has_next ? mask|(1<<ID) : mask);
+
+		if( (1<<ID) & mask )
+			return memo[key] = rec(i+1, ev, swords, mask);
+		return memo[key] =
+			      P * max(C+rec(i+1, ev, swords-1, newmask), rec(i+1, ev, swords, newmask))
+			+ (1-P) * rec(i+1, ev, swords, mask);
+	}
+};
+
+// 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 double& Expected, const double& Received) {
+ bool ok = (abs(Expected - Received) < 1e-9);
+ 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(_, NewItemShop().getMaximum(swords, customers));}
+int main(){
+
+CASE(0)
+	int swords = 1; 
+	string customers_[] = { "8,1,80 16,100,11", "12,10,100" };
+	  vector <string> customers(customers_, customers_+sizeof(customers_)/sizeof(*customers_)); 
+	double _ = 19.0; 
+END
+CASE(1)
+	int swords = 2; 
+	string customers_[] = { "8,1,80 16,100,11", "12,10,100" };
+	  vector <string> customers(customers_, customers_+sizeof(customers_)/sizeof(*customers_)); 
+	double _ = 21.8; 
+END
+CASE(2)
+	int swords = 1; 
+	string customers_[] = { "0,90,25 2,90,25 4,90,25 6,90,25", "7,100,80" };
+	  vector <string> customers(customers_, customers_+sizeof(customers_)/sizeof(*customers_)); 
+	double _ = 90.0; 
+END
+CASE(3)
+	int swords = 3; 
+	string customers_[] = { "17,31,41 20,59,26 23,53,5", "19,89,79", "16,32,38 22,46,26", "18,43,38 21,32,7" };
+	  vector <string> customers(customers_, customers_+sizeof(customers_)/sizeof(*customers_)); 
+	double _ = 135.5121414; 
+END
+CASE(4)
+	int swords = 5; 
+	string customers_[] = { "1,1,10", "2,2,9", "3,3,8", "4,4,7", "5,5,6", "6,6,5", "7,7,4", "8,8,3", "9,9,2", "10,10,1" };
+	  vector <string> customers(customers_, customers_+sizeof(customers_)/sizeof(*customers_)); 
+	double _ = 2.1999744634845344; 
+END
+/*
+CASE(5)
+	int swords = ; 
+	string customers_[] = ;
+	  vector <string> customers(customers_, customers_+sizeof(customers_)/sizeof(*customers_)); 
+	double _ = ; 
+END
+CASE(6)
+	int swords = ; 
+	string customers_[] = ;
+	  vector <string> customers(customers_, customers_+sizeof(customers_)/sizeof(*customers_)); 
+	double _ = ; 
+END
+*/
+}
+// END CUT HERE

ADDED   SRM/515/1C.cpp
Index: SRM/515/1C.cpp
==================================================================
--- SRM/515/1C.cpp
+++ SRM/515/1C.cpp
@@ -0,0 +1,288 @@
+#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>
+#include <cstring>
+using namespace std;
+typedef long long LL;
+typedef complex<double> CMP;
+
+static const int INF = 0x3fffffff;
+LL gcd(LL x, LL y) { while(x) swap(x,y%=x); return y; }
+static const int dy[] = {-1,+1,0,0};
+static const int dx[] = {0,0,-1,+1};
+
+class MeetInTheMaze { public:
+	int H, W;
+	map<char, int> count;
+
+	void setup_maze(vector<string>& maze)
+	{
+		setup_sentinel(maze);
+
+		H = maze.size();
+		W = maze[0].size();
+
+		for(int y=0; y<H; ++y)
+		for(int x=0; x<W; ++x)
+			count[maze[y][x]] ++;
+	}
+
+	void setup_sentinel(vector<string>& maze)
+	{
+		for(int y=0; y<maze.size(); ++y)
+			maze[y] = '#' + maze[y] + '#';
+		maze.insert( maze.begin(), string(maze[0].size(), '#') );
+		maze.insert( maze.end(),   string(maze[0].size(), '#') );
+	}
+
+	string ratio2str(LL si, LL bo)
+	{
+		if( si >= INF )
+			return "";
+		LL g = gcd(si, bo);
+		stringstream ss;
+		ss << si/g << "/" << bo/g;
+		return ss.str();
+	}
+
+	LL dijkstra(const vector< vector<int> >& FD, const vector< vector<int> >& RD, const vector<string>& maze)
+	{
+		typedef pair<int,int>   vert;
+		typedef LL              cost;
+		typedef pair<cost,vert> cvert;
+
+		vector<bool> V(H*W);
+		priority_queue< cvert, vector<cvert>, greater<cvert> > Q;
+		for(int y=0; y<H; ++y)
+		for(int x=0; x<W; ++x)
+			if( maze[y][x] != '#' )
+				Q.push( cvert(FD[y][x]+RD[y][x], make_pair(y,x)) );
+
+		cost total = 0;
+		while( !Q.empty() )
+		{
+			cvert v = Q.top(); Q.pop();
+			cost c = v.first;
+			int y = v.second.first;
+			int x = v.second.second;
+			if( V[y*W+x] )
+				continue;
+			V[y*W+x] = true;
+
+			if( maze[y][x] == 'L' )
+				total += c;
+
+			for(int k=0; k<4; ++k) {
+				int yy = y+dy[k];
+				int xx = x+dx[k];
+				cvert u(c+1, make_pair(yy,xx));
+				if( maze[yy][xx]!='#' && !V[yy*W+xx] )
+					Q.push(u);
+			}
+		}
+		return total;
+	}
+
+	void bfs(vector< vector<int> >& D, vector<string>& m, int y, int x)
+	{
+		vector< pair<int,int> > Q(1, make_pair(y,x));
+		D[y][x] = 0;
+		for(int s=1; !Q.empty(); ++s)
+		{
+			vector< pair<int,int> > Q2;
+			for(int i=0; i<Q.size(); ++i){
+				y = Q[i].first;
+				x = Q[i].second;
+				for(int k=0; k<4; ++k) {
+					int yy = y+dy[k];
+					int xx = x+dx[k];
+					if( m[yy][xx]!='#' && D[yy][xx]==INF )
+						Q2.push_back(make_pair(yy,xx)), D[yy][xx]=s;
+				}
+			}
+			Q.swap(Q2);
+		}
+	}
+
+	string getExpected(vector <string> maze)
+	{
+		setup_maze(maze);
+
+		LL total = 0;
+		for(int fy=0; fy<H; ++fy)
+		for(int fx=0; fx<W; ++fx)
+		if( maze[fy][fx] == 'F' )
+		{
+			// Fill the 2d-map FD with the distance from (fy,fx) in the maze.
+			vector< vector<int> > FD(H, vector<int>(W, INF));
+			bfs(FD, maze, fy, fx);
+			for(int ry=0; ry<H; ++ry)
+			for(int rx=0; rx<W; ++rx)
+			if( maze[ry][rx] == 'R' )
+			{
+				// Fill the 2d-map RD with the distance from (ry,rx) in the maze.
+				vector< vector<int> > RD(H, vector<int>(W, INF));
+				bfs(RD, maze, ry, rx);
+				// Compute the distances of all the cells from the base "FD+RD"
+				total += dijkstra(FD, RD, maze);
+			}
+		}
+		return ratio2str(total, count['F']*count['R']*count['L']);
+	}
+};
+
+// 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(_, MeetInTheMaze().getExpected(maze));}
+int main(){
+
+CASE(0)
+	string maze_[] = { "#########", 
+  "####F####", 
+  "##L...R##", 
+  "####L####", 
+  "#########" }
+;
+	  vector <string> maze(maze_, maze_+sizeof(maze_)/sizeof(*maze_)); 
+	string _ = "9/2"; 
+END
+CASE(1)
+	string maze_[] = { "LR", 
+  "RF" }
+;
+	  vector <string> maze(maze_, maze_+sizeof(maze_)/sizeof(*maze_)); 
+	string _ = "2/1"; 
+END
+CASE(2)
+	string maze_[] = { "..F.#...", 
+  "L.F.#..L", 
+  "..F.#...", 
+  ".R.#..L.", 
+  "...#....", 
+  "..R#.L.." }
+;
+	  vector <string> maze(maze_, maze_+sizeof(maze_)/sizeof(*maze_)); 
+	string _ = ""; 
+END
+CASE(3)
+	string maze_[] = { ".L..L..L..", 
+  "..........", 
+  "..........", 
+  "..........", 
+  "........R.", 
+  "...R......", 
+  "..........", 
+  "..........", 
+  "..........", 
+  ".......F.." }
+;
+	  vector <string> maze(maze_, maze_+sizeof(maze_)/sizeof(*maze_)); 
+	string _ = "40/3"; 
+END
+CASE(4)
+	string maze_[] = { "#.#....#...#.#", 
+  "#...#..#......", 
+  ".L#...#R#..#F.", 
+  "#...#......#..", 
+  "#......#.....#", 
+  ".R.....F....L.", 
+  "##..#.......#.", 
+  "#........##...", 
+  ".F...##L#..#R#" }
+;
+	  vector <string> maze(maze_, maze_+sizeof(maze_)/sizeof(*maze_)); 
+	string _ = "362/27"; 
+END
+CASE(5)
+	string maze_[] = { "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLFLLLLLLLLLFLLLL", 
+  "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL", 
+  "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL", 
+  "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL", 
+  "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL", 
+  "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL", 
+  "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL", 
+  "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL", 
+  "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLFFLLLLLLLLLLRLLLL", 
+  "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL", 
+  "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL", 
+  "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL", 
+  "LLLLLLLLLLLLLLLLLLLLLLLLLLLLRLLLLLFLLLLLLLLLLLLLLF", 
+  "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL", 
+  "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLF", 
+  "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLFLLL", 
+  "LLLLLLLLLLLRLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL", 
+  "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLRRL", 
+  "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL", 
+  "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL", 
+  "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLRLLLLLLLLLLLLLLLL", 
+  "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLR", 
+  "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL", 
+  "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLRLLL", 
+  "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL", 
+  "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLRLLLLLL", 
+  "LLLLLLLLLLLLLLLLLLLLLLLRLLLLLLLLLLLLLLLLLLLLLLLLLL", 
+  "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL", 
+  "LLLLLLLLLLLLLLLLRLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL", 
+  "LLLLLLLLLFFLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL", 
+  "FLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL", 
+  "LLLLLLLLLLLLLLLLRLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL", 
+  "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL", 
+  "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL", 
+  "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLRLLLLLLLLLLLLLL", 
+  "LLLLLLLLLLLLLLLLLLLLLLFLLLLLLLLLLLLLLLLLLLLLLLLLLL", 
+  "LLLLLLLLLLLLLLLLFLLLLLLLLLRLLLLLLLLLLLLLLLLLLLRLLL", 
+  "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL", 
+  "LLLLLLLFLLLLLLLLLLLLLLLLRLLLLLLLLLRLLLLLLLLLLLLRLL", 
+  "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLRLLLLL", 
+  "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL", 
+  "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL", 
+  "LLLFLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL", 
+  "LLLLLLLLLLLLLLLLLLLLLLLLLFLLLLLLLLLLLLLLLLLLLLLLLL", 
+  "LLLLLLLLLLLLLLLLLLLLFLLLLLLLLLLLLLLLLLLLLLLLLLLLLL", 
+  "FLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL", 
+  "LLLLLLLLLRLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL", 
+  "LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL", 
+  "LLLLLLLLLFLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL", 
+  "LLLLLLLLLLLLLLLLLLLLLLLLLLLFLLLLLLLLLLLLLLLLLLLLLL" }
+;
+	  vector <string> maze(maze_, maze_+sizeof(maze_)/sizeof(*maze_)); 
+	string _ = "210623/4100"; 
+END
+/*
+CASE(6)
+	string maze_[] = ;
+	  vector <string> maze(maze_, maze_+sizeof(maze_)/sizeof(*maze_)); 
+	string _ = ; 
+END
+CASE(7)
+	string maze_[] = ;
+	  vector <string> maze(maze_, maze_+sizeof(maze_)/sizeof(*maze_)); 
+	string _ = ; 
+END
+*/
+}
+// END CUT HERE