f6764c7ea7 2011-12-17        kinaba: #include <iostream>
f6764c7ea7 2011-12-17        kinaba: #include <sstream>
f6764c7ea7 2011-12-17        kinaba: #include <iomanip>
f6764c7ea7 2011-12-17        kinaba: #include <vector>
f6764c7ea7 2011-12-17        kinaba: #include <string>
f6764c7ea7 2011-12-17        kinaba: #include <map>
f6764c7ea7 2011-12-17        kinaba: #include <set>
f6764c7ea7 2011-12-17        kinaba: #include <algorithm>
f6764c7ea7 2011-12-17        kinaba: #include <numeric>
f6764c7ea7 2011-12-17        kinaba: #include <iterator>
f6764c7ea7 2011-12-17        kinaba: #include <functional>
f6764c7ea7 2011-12-17        kinaba: #include <complex>
f6764c7ea7 2011-12-17        kinaba: #include <queue>
f6764c7ea7 2011-12-17        kinaba: #include <stack>
f6764c7ea7 2011-12-17        kinaba: #include <cmath>
f6764c7ea7 2011-12-17        kinaba: #include <cassert>
f6764c7ea7 2011-12-17        kinaba: #include <cstring>
f6764c7ea7 2011-12-17        kinaba: #ifdef __GNUC__
f6764c7ea7 2011-12-17        kinaba: #include <ext/hash_map>
f6764c7ea7 2011-12-17        kinaba: #define unordered_map __gnu_cxx::hash_map
f6764c7ea7 2011-12-17        kinaba: #else
f6764c7ea7 2011-12-17        kinaba: #include <unordered_map>
f6764c7ea7 2011-12-17        kinaba: #endif
f6764c7ea7 2011-12-17        kinaba: using namespace std;
f6764c7ea7 2011-12-17        kinaba: typedef long long LL;
f6764c7ea7 2011-12-17        kinaba: typedef complex<double> CMP;
f6764c7ea7 2011-12-17        kinaba: 
f6764c7ea7 2011-12-17        kinaba: class DucksAlignment { public:
f6764c7ea7 2011-12-17        kinaba: 	int minimumTime(vector <string> grid)
f6764c7ea7 2011-12-17        kinaba: 	{
f6764c7ea7 2011-12-17        kinaba: 		vector<int> xs, ys;
f6764c7ea7 2011-12-17        kinaba: 		for(int y=0; y<grid.size(); ++y)
f6764c7ea7 2011-12-17        kinaba: 		for(int x=0; x<grid[y].size(); ++x)
f6764c7ea7 2011-12-17        kinaba: 			if( grid[y][x] == 'o' )
f6764c7ea7 2011-12-17        kinaba: 			{
f6764c7ea7 2011-12-17        kinaba: 				xs.push_back(x);
f6764c7ea7 2011-12-17        kinaba: 				ys.push_back(y);
f6764c7ea7 2011-12-17        kinaba: 			}
f6764c7ea7 2011-12-17        kinaba: 		sort(xs.begin(), xs.end());
f6764c7ea7 2011-12-17        kinaba: 		sort(ys.begin(), ys.end());
f6764c7ea7 2011-12-17        kinaba: 		return min(single(xs)+line(ys), line(xs)+single(ys));
f6764c7ea7 2011-12-17        kinaba: 	}
f6764c7ea7 2011-12-17        kinaba: 
f6764c7ea7 2011-12-17        kinaba: 	int single(const vector<int>& xs)
f6764c7ea7 2011-12-17        kinaba: 	{
f6764c7ea7 2011-12-17        kinaba: 		int mid = xs[xs.size()/2];
f6764c7ea7 2011-12-17        kinaba: 		int sum = 0;
f6764c7ea7 2011-12-17        kinaba: 		for(int i=0; i<xs.size(); ++i)
f6764c7ea7 2011-12-17        kinaba: 			sum += abs(xs[i] - mid);
f6764c7ea7 2011-12-17        kinaba: 		return sum;
f6764c7ea7 2011-12-17        kinaba: 	}
f6764c7ea7 2011-12-17        kinaba: 
f6764c7ea7 2011-12-17        kinaba: 	int line(const vector<int>& xs)
f6764c7ea7 2011-12-17        kinaba: 	{
f6764c7ea7 2011-12-17        kinaba: 		int best = xs.back() * xs.size();
f6764c7ea7 2011-12-17        kinaba: 		for(int lb=0; lb<=xs.back(); ++lb) {
f6764c7ea7 2011-12-17        kinaba: 			int sum = 0;
f6764c7ea7 2011-12-17        kinaba: 			for(int i=0; i<xs.size(); ++i)
f6764c7ea7 2011-12-17        kinaba: 				sum += abs(xs[i] - (lb+i));
f6764c7ea7 2011-12-17        kinaba: 			best = min(best, sum);
f6764c7ea7 2011-12-17        kinaba: 		}
f6764c7ea7 2011-12-17        kinaba: 		return best;
f6764c7ea7 2011-12-17        kinaba: 	}
f6764c7ea7 2011-12-17        kinaba: };
f6764c7ea7 2011-12-17        kinaba: 
f6764c7ea7 2011-12-17        kinaba: // BEGIN CUT HERE
f6764c7ea7 2011-12-17        kinaba: #include <ctime>
f6764c7ea7 2011-12-17        kinaba: double start_time; string timer()
f6764c7ea7 2011-12-17        kinaba:  { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
f6764c7ea7 2011-12-17        kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
f6764c7ea7 2011-12-17        kinaba:  { os << "{ ";
f6764c7ea7 2011-12-17        kinaba:    for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
f6764c7ea7 2011-12-17        kinaba:    os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
f6764c7ea7 2011-12-17        kinaba: void verify_case(const int& Expected, const int& Received) {
f6764c7ea7 2011-12-17        kinaba:  bool ok = (Expected == Received);
f6764c7ea7 2011-12-17        kinaba:  if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
f6764c7ea7 2011-12-17        kinaba:  cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
f6764c7ea7 2011-12-17        kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
f6764c7ea7 2011-12-17        kinaba: #define END	 verify_case(_, DucksAlignment().minimumTime(grid));}
f6764c7ea7 2011-12-17        kinaba: int main(){
f6764c7ea7 2011-12-17        kinaba: 
f6764c7ea7 2011-12-17        kinaba: CASE(0)
f6764c7ea7 2011-12-17        kinaba: 	string grid_[] = {".o",
f6764c7ea7 2011-12-17        kinaba:  "o."};
f6764c7ea7 2011-12-17        kinaba: 	  vector <string> grid(grid_, grid_+sizeof(grid_)/sizeof(*grid_));
f6764c7ea7 2011-12-17        kinaba: 	int _ = 1;
f6764c7ea7 2011-12-17        kinaba: END
f6764c7ea7 2011-12-17        kinaba: CASE(1)
f6764c7ea7 2011-12-17        kinaba: 	string grid_[] = {".o...",
f6764c7ea7 2011-12-17        kinaba:  "..o..",
f6764c7ea7 2011-12-17        kinaba:  "....o"};
f6764c7ea7 2011-12-17        kinaba: 	  vector <string> grid(grid_, grid_+sizeof(grid_)/sizeof(*grid_));
f6764c7ea7 2011-12-17        kinaba: 	int _ = 3;
f6764c7ea7 2011-12-17        kinaba: END
f6764c7ea7 2011-12-17        kinaba: CASE(2)
f6764c7ea7 2011-12-17        kinaba: 	string grid_[] = {"o..........",
f6764c7ea7 2011-12-17        kinaba:  "..o........",
f6764c7ea7 2011-12-17        kinaba:  ".......o...",
f6764c7ea7 2011-12-17        kinaba:  "...........",
f6764c7ea7 2011-12-17        kinaba:  "...........",
f6764c7ea7 2011-12-17        kinaba:  "...........",
f6764c7ea7 2011-12-17        kinaba:  "........o..",
f6764c7ea7 2011-12-17        kinaba:  "..........."};
f6764c7ea7 2011-12-17        kinaba: 	  vector <string> grid(grid_, grid_+sizeof(grid_)/sizeof(*grid_));
f6764c7ea7 2011-12-17        kinaba: 	int _ = 16;
f6764c7ea7 2011-12-17        kinaba: END
f6764c7ea7 2011-12-17        kinaba: CASE(3)
f6764c7ea7 2011-12-17        kinaba: 	string grid_[] = {".........",
f6764c7ea7 2011-12-17        kinaba:  "....o....",
f6764c7ea7 2011-12-17        kinaba:  "........."};
f6764c7ea7 2011-12-17        kinaba: 	  vector <string> grid(grid_, grid_+sizeof(grid_)/sizeof(*grid_));
f6764c7ea7 2011-12-17        kinaba: 	int _ = 0;
f6764c7ea7 2011-12-17        kinaba: END
f6764c7ea7 2011-12-17        kinaba: CASE(4)
f6764c7ea7 2011-12-17        kinaba: 	string grid_[] = {"...o..........................",
f6764c7ea7 2011-12-17        kinaba:  "............................o.",
f6764c7ea7 2011-12-17        kinaba:  ".o............................",
f6764c7ea7 2011-12-17        kinaba:  "............o.................",
f6764c7ea7 2011-12-17        kinaba:  ".................o............",
f6764c7ea7 2011-12-17        kinaba:  "......................o.......",
f6764c7ea7 2011-12-17        kinaba:  "......o.......................",
f6764c7ea7 2011-12-17        kinaba:  "....o.........................",
f6764c7ea7 2011-12-17        kinaba:  "...............o..............",
f6764c7ea7 2011-12-17        kinaba:  ".......................o......",
f6764c7ea7 2011-12-17        kinaba:  "...........................o..",
f6764c7ea7 2011-12-17        kinaba:  ".......o......................"};
f6764c7ea7 2011-12-17        kinaba: 	  vector <string> grid(grid_, grid_+sizeof(grid_)/sizeof(*grid_));
f6764c7ea7 2011-12-17        kinaba: 	int _ = 99;
f6764c7ea7 2011-12-17        kinaba: END
f6764c7ea7 2011-12-17        kinaba: /*
f6764c7ea7 2011-12-17        kinaba: CASE(5)
f6764c7ea7 2011-12-17        kinaba: 	string grid_[] = ;
f6764c7ea7 2011-12-17        kinaba: 	  vector <string> grid(grid_, grid_+sizeof(grid_)/sizeof(*grid_));
f6764c7ea7 2011-12-17        kinaba: 	int _ = ;
f6764c7ea7 2011-12-17        kinaba: END
f6764c7ea7 2011-12-17        kinaba: CASE(6)
f6764c7ea7 2011-12-17        kinaba: 	string grid_[] = ;
f6764c7ea7 2011-12-17        kinaba: 	  vector <string> grid(grid_, grid_+sizeof(grid_)/sizeof(*grid_));
f6764c7ea7 2011-12-17        kinaba: 	int _ = ;
f6764c7ea7 2011-12-17        kinaba: END
f6764c7ea7 2011-12-17        kinaba: */
f6764c7ea7 2011-12-17        kinaba: }
f6764c7ea7 2011-12-17        kinaba: // END CUT HERE