7e18a763ef 2013-01-29        kinaba: #include <iostream>
7e18a763ef 2013-01-29        kinaba: #include <sstream>
7e18a763ef 2013-01-29        kinaba: #include <iomanip>
7e18a763ef 2013-01-29        kinaba: #include <vector>
7e18a763ef 2013-01-29        kinaba: #include <string>
7e18a763ef 2013-01-29        kinaba: #include <map>
7e18a763ef 2013-01-29        kinaba: #include <set>
7e18a763ef 2013-01-29        kinaba: #include <algorithm>
7e18a763ef 2013-01-29        kinaba: #include <numeric>
7e18a763ef 2013-01-29        kinaba: #include <iterator>
7e18a763ef 2013-01-29        kinaba: #include <functional>
7e18a763ef 2013-01-29        kinaba: #include <complex>
7e18a763ef 2013-01-29        kinaba: #include <queue>
7e18a763ef 2013-01-29        kinaba: #include <stack>
7e18a763ef 2013-01-29        kinaba: #include <cmath>
7e18a763ef 2013-01-29        kinaba: #include <cassert>
7e18a763ef 2013-01-29        kinaba: using namespace std;
7e18a763ef 2013-01-29        kinaba: typedef long long LL;
7e18a763ef 2013-01-29        kinaba: typedef long double LD;
7e18a763ef 2013-01-29        kinaba: typedef complex<LD> CMP;
7e18a763ef 2013-01-29        kinaba: 
7e18a763ef 2013-01-29        kinaba: static const unsigned MODVAL = 1000000009;
7e18a763ef 2013-01-29        kinaba: 
7e18a763ef 2013-01-29        kinaba: class Mountains { public:
7e18a763ef 2013-01-29        kinaba: 	int countPlacements(vector <int> heights, vector <string> visibility)
7e18a763ef 2013-01-29        kinaba: 	{
7e18a763ef 2013-01-29        kinaba: 		int W = visibility[0].size();
7e18a763ef 2013-01-29        kinaba: 		int N = visibility.size();
7e18a763ef 2013-01-29        kinaba: 		memo.resize(N);
7e18a763ef 2013-01-29        kinaba: 
7e18a763ef 2013-01-29        kinaba: 		vector<int> view(W, 0);
7e18a763ef 2013-01-29        kinaba: 		return rec(W, view, heights.size()-1, heights, visibility);
7e18a763ef 2013-01-29        kinaba: 	}
7e18a763ef 2013-01-29        kinaba: 
7e18a763ef 2013-01-29        kinaba: 	vector< map<vector<int>,int> > memo;
7e18a763ef 2013-01-29        kinaba: 	int rec(int W, const vector<int>& view, int i, vector<int>& H, const vector<string>& V)
7e18a763ef 2013-01-29        kinaba: 	{
7e18a763ef 2013-01-29        kinaba: 		if(i < 0)
7e18a763ef 2013-01-29        kinaba: 			return 1;
7e18a763ef 2013-01-29        kinaba: 
7e18a763ef 2013-01-29        kinaba: 		if(memo[i].count(view))
7e18a763ef 2013-01-29        kinaba: 			return memo[i][view];
7e18a763ef 2013-01-29        kinaba: 
7e18a763ef 2013-01-29        kinaba: 		int mustL=0, mustR=W-1;
7e18a763ef 2013-01-29        kinaba: 		int mustNotL=W, mustNotR=-1;
7e18a763ef 2013-01-29        kinaba: 		for(int x=0; x<W; ++x)
7e18a763ef 2013-01-29        kinaba: 		{
7e18a763ef 2013-01-29        kinaba: 			int LLL = x - (H[i]-view[x]-1);
7e18a763ef 2013-01-29        kinaba: 			int RRR = x + (H[i]-view[x]-1);
7e18a763ef 2013-01-29        kinaba: 			if(V[i][x] == 'X') {
7e18a763ef 2013-01-29        kinaba: 				if( H[i] <= view[x] )
7e18a763ef 2013-01-29        kinaba: 					return 0;
7e18a763ef 2013-01-29        kinaba: 				mustL = max(mustL, LLL);
7e18a763ef 2013-01-29        kinaba: 				mustR = min(mustR, RRR);
7e18a763ef 2013-01-29        kinaba: 			} else {
7e18a763ef 2013-01-29        kinaba: //				if( H[i] > view[x] ) {
7e18a763ef 2013-01-29        kinaba: //					mustNotL = min(mustNotL, LLL);
7e18a763ef 2013-01-29        kinaba: //					mustNotR = max(mustNotR, RRR);
7e18a763ef 2013-01-29        kinaba: //				}
7e18a763ef 2013-01-29        kinaba: 			}
7e18a763ef 2013-01-29        kinaba: 		}
7e18a763ef 2013-01-29        kinaba: 
7e18a763ef 2013-01-29        kinaba: 		LL result = 0;
7e18a763ef 2013-01-29        kinaba: 		for(int c=mustL; c<=mustR; ++c) if(c<mustNotL || mustNotR<c)
7e18a763ef 2013-01-29        kinaba: 		{
7e18a763ef 2013-01-29        kinaba: 			bool good = true;
7e18a763ef 2013-01-29        kinaba: 			for(int x=0; x<W && good; ++x) {
7e18a763ef 2013-01-29        kinaba: 				int my_h = H[i] - abs(x-c);
7e18a763ef 2013-01-29        kinaba: 				if((V[i][x]=='X') != (view[x] < my_h))
7e18a763ef 2013-01-29        kinaba: 					good = false;
7e18a763ef 2013-01-29        kinaba: 			}
7e18a763ef 2013-01-29        kinaba: 
7e18a763ef 2013-01-29        kinaba: 			if( good ) {
7e18a763ef 2013-01-29        kinaba: 				vector<int> view2(W);
7e18a763ef 2013-01-29        kinaba: 				for(int x=0; x<W; ++x) {
7e18a763ef 2013-01-29        kinaba: 					int my_h = H[i] - abs(x-c);
7e18a763ef 2013-01-29        kinaba: 					view2[x] = max(my_h, view[x]);
7e18a763ef 2013-01-29        kinaba: 				}
7e18a763ef 2013-01-29        kinaba: 				result += rec(W, view2, i-1, H, V);
7e18a763ef 2013-01-29        kinaba: 			}
7e18a763ef 2013-01-29        kinaba: 		}
7e18a763ef 2013-01-29        kinaba: 		return memo[i][view] = int(result % MODVAL);
7e18a763ef 2013-01-29        kinaba: 	}
7e18a763ef 2013-01-29        kinaba: };
7e18a763ef 2013-01-29        kinaba: 
7e18a763ef 2013-01-29        kinaba: // BEGIN CUT HERE
7e18a763ef 2013-01-29        kinaba: #include <ctime>
7e18a763ef 2013-01-29        kinaba: double start_time; string timer()
7e18a763ef 2013-01-29        kinaba:  { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
7e18a763ef 2013-01-29        kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
7e18a763ef 2013-01-29        kinaba:  { os << "{ ";
7e18a763ef 2013-01-29        kinaba:    for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
7e18a763ef 2013-01-29        kinaba:    os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
7e18a763ef 2013-01-29        kinaba: void verify_case(const int& Expected, const int& Received) {
7e18a763ef 2013-01-29        kinaba:  bool ok = (Expected == Received);
7e18a763ef 2013-01-29        kinaba:  if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
7e18a763ef 2013-01-29        kinaba:  cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
7e18a763ef 2013-01-29        kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
7e18a763ef 2013-01-29        kinaba: #define END	 verify_case(_, Mountains().countPlacements(heights, visibility));}
7e18a763ef 2013-01-29        kinaba: int main(){
7e18a763ef 2013-01-29        kinaba: 
7e18a763ef 2013-01-29        kinaba: CASE(0)
7e18a763ef 2013-01-29        kinaba: 	int heights_[] = {2, 3, 2};
7e18a763ef 2013-01-29        kinaba: 	  vector <int> heights(heights_, heights_+sizeof(heights_)/sizeof(*heights_));
7e18a763ef 2013-01-29        kinaba: 	string visibility_[] = {"------",
7e18a763ef 2013-01-29        kinaba:  "XXXX--",
7e18a763ef 2013-01-29        kinaba:  "---XXX"};
7e18a763ef 2013-01-29        kinaba: 	  vector <string> visibility(visibility_, visibility_+sizeof(visibility_)/sizeof(*visibility_));
7e18a763ef 2013-01-29        kinaba: 	int _ = 4;
7e18a763ef 2013-01-29        kinaba: END
7e18a763ef 2013-01-29        kinaba: CASE(1)
7e18a763ef 2013-01-29        kinaba: 	int heights_[] = {4, 3, 4};
7e18a763ef 2013-01-29        kinaba: 	  vector <int> heights(heights_, heights_+sizeof(heights_)/sizeof(*heights_));
7e18a763ef 2013-01-29        kinaba: 	string visibility_[] = {"XXXXX--------",
7e18a763ef 2013-01-29        kinaba:  "----------XXX",
7e18a763ef 2013-01-29        kinaba:  "----XXXXXXX--"};
7e18a763ef 2013-01-29        kinaba: 	  vector <string> visibility(visibility_, visibility_+sizeof(visibility_)/sizeof(*visibility_));
7e18a763ef 2013-01-29        kinaba: 	int _ = 4;
7e18a763ef 2013-01-29        kinaba: END
7e18a763ef 2013-01-29        kinaba: CASE(2)
7e18a763ef 2013-01-29        kinaba: 	int heights_[] = {13, 2, 3, 2};
7e18a763ef 2013-01-29        kinaba: 	  vector <int> heights(heights_, heights_+sizeof(heights_)/sizeof(*heights_));
7e18a763ef 2013-01-29        kinaba: 	string visibility_[] = {"XXXXXXXXX",
7e18a763ef 2013-01-29        kinaba:  "-XXX-----",
7e18a763ef 2013-01-29        kinaba:  "----XXXXX",
7e18a763ef 2013-01-29        kinaba:  "-----XXX-"};
7e18a763ef 2013-01-29        kinaba: 	  vector <string> visibility(visibility_, visibility_+sizeof(visibility_)/sizeof(*visibility_));
7e18a763ef 2013-01-29        kinaba: 	int _ = 9;
7e18a763ef 2013-01-29        kinaba: END
7e18a763ef 2013-01-29        kinaba: CASE(3)
7e18a763ef 2013-01-29        kinaba: 	int heights_[] = {8, 2, 9, 3, 10};
7e18a763ef 2013-01-29        kinaba: 	  vector <int> heights(heights_, heights_+sizeof(heights_)/sizeof(*heights_));
7e18a763ef 2013-01-29        kinaba: 	string visibility_[] = {"X------",
7e18a763ef 2013-01-29        kinaba:  "-------",
7e18a763ef 2013-01-29        kinaba:  "------X",
7e18a763ef 2013-01-29        kinaba:  "-------",
7e18a763ef 2013-01-29        kinaba:  "XXXXXXX"};
7e18a763ef 2013-01-29        kinaba: 	  vector <string> visibility(visibility_, visibility_+sizeof(visibility_)/sizeof(*visibility_));
7e18a763ef 2013-01-29        kinaba: 	int _ = 98;
7e18a763ef 2013-01-29        kinaba: END
7e18a763ef 2013-01-29        kinaba: CASE(4)
7e18a763ef 2013-01-29        kinaba: 	int heights_[] = {20, 20, 20, 20, 20, 20, 45, 50, 49, 50};
7e18a763ef 2013-01-29        kinaba: 	  vector <int> heights(heights_, heights_+sizeof(heights_)/sizeof(*heights_));
7e18a763ef 2013-01-29        kinaba: 	string visibility_[] = {"-------------------",
7e18a763ef 2013-01-29        kinaba:  "-------------------",
7e18a763ef 2013-01-29        kinaba:  "-------------------",
7e18a763ef 2013-01-29        kinaba:  "-------------------",
7e18a763ef 2013-01-29        kinaba:  "-------------------",
7e18a763ef 2013-01-29        kinaba:  "-------------------",
7e18a763ef 2013-01-29        kinaba:  "-------------------",
7e18a763ef 2013-01-29        kinaba:  "------------XXXXXXX",
7e18a763ef 2013-01-29        kinaba:  "XXXXXXX------------",
7e18a763ef 2013-01-29        kinaba:  "XXXXXXXXXXXXXXXXXXX"}
7e18a763ef 2013-01-29        kinaba: ;
7e18a763ef 2013-01-29        kinaba: 	  vector <string> visibility(visibility_, visibility_+sizeof(visibility_)/sizeof(*visibility_));
7e18a763ef 2013-01-29        kinaba: 	int _ = 973726691;
7e18a763ef 2013-01-29        kinaba: END
7e18a763ef 2013-01-29        kinaba: CASE(5)
7e18a763ef 2013-01-29        kinaba: 	int heights_[] = {20, 20, 20, 20, 20, 20, 45, 50, 49, 50};
7e18a763ef 2013-01-29        kinaba: 	  vector <int> heights(heights_, heights_+sizeof(heights_)/sizeof(*heights_));
7e18a763ef 2013-01-29        kinaba: 	string visibility_[] = {"-------------------------------------------------",
7e18a763ef 2013-01-29        kinaba:  "-------------------------------------------------",
7e18a763ef 2013-01-29        kinaba:  "-------------------------------------------------",
7e18a763ef 2013-01-29        kinaba:  "-------------------------------------------------",
7e18a763ef 2013-01-29        kinaba:  "-------------------------------------------------",
7e18a763ef 2013-01-29        kinaba:  "-------------------------------------------------",
7e18a763ef 2013-01-29        kinaba:  "-------------------------------------------------",
7e18a763ef 2013-01-29        kinaba:  "------------XXXXXXX------------------------------",
7e18a763ef 2013-01-29        kinaba:  "XXXXXXX------------------------------------------",
7e18a763ef 2013-01-29        kinaba:  "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX"}
7e18a763ef 2013-01-29        kinaba: ;
7e18a763ef 2013-01-29        kinaba: 	  vector <string> visibility(visibility_, visibility_+sizeof(visibility_)/sizeof(*visibility_));
7e18a763ef 2013-01-29        kinaba: 	int _ = -1;
7e18a763ef 2013-01-29        kinaba: END
7e18a763ef 2013-01-29        kinaba: }
7e18a763ef 2013-01-29        kinaba: // END CUT HERE