46d6ab9496 2011-12-07 kinaba: #include <iostream> 46d6ab9496 2011-12-07 kinaba: #include <sstream> 46d6ab9496 2011-12-07 kinaba: #include <iomanip> 46d6ab9496 2011-12-07 kinaba: #include <vector> 46d6ab9496 2011-12-07 kinaba: #include <string> 46d6ab9496 2011-12-07 kinaba: #include <map> 46d6ab9496 2011-12-07 kinaba: #include <set> 46d6ab9496 2011-12-07 kinaba: #include <algorithm> 46d6ab9496 2011-12-07 kinaba: #include <numeric> 46d6ab9496 2011-12-07 kinaba: #include <iterator> 46d6ab9496 2011-12-07 kinaba: #include <functional> 46d6ab9496 2011-12-07 kinaba: #include <complex> 46d6ab9496 2011-12-07 kinaba: #include <queue> 46d6ab9496 2011-12-07 kinaba: #include <stack> 46d6ab9496 2011-12-07 kinaba: #include <cmath> 46d6ab9496 2011-12-07 kinaba: #include <cassert> 46d6ab9496 2011-12-07 kinaba: #include <cstring> 46d6ab9496 2011-12-07 kinaba: #ifdef __GNUC__ 46d6ab9496 2011-12-07 kinaba: #include <ext/hash_map> 46d6ab9496 2011-12-07 kinaba: #define unordered_map __gnu_cxx::hash_map 46d6ab9496 2011-12-07 kinaba: #else 46d6ab9496 2011-12-07 kinaba: #include <unordered_map> 46d6ab9496 2011-12-07 kinaba: #endif 46d6ab9496 2011-12-07 kinaba: using namespace std; 46d6ab9496 2011-12-07 kinaba: typedef long long LL; 46d6ab9496 2011-12-07 kinaba: typedef complex<double> CMP; 46d6ab9496 2011-12-07 kinaba: 46d6ab9496 2011-12-07 kinaba: class DropCoins { public: 46d6ab9496 2011-12-07 kinaba: int getMinimum(vector <string> board, int K) 46d6ab9496 2011-12-07 kinaba: { 46d6ab9496 2011-12-07 kinaba: static const int INF = 0x3fffffff; 46d6ab9496 2011-12-07 kinaba: int best = INF; 46d6ab9496 2011-12-07 kinaba: int H = board.size(); 46d6ab9496 2011-12-07 kinaba: int W = board[0].size(); 46d6ab9496 2011-12-07 kinaba: vector< vector<int> > sum(H, vector<int>(W+1)); 46d6ab9496 2011-12-07 kinaba: for(int y=0; y<H; ++y) 46d6ab9496 2011-12-07 kinaba: for(int x=0; x<W; ++x) 46d6ab9496 2011-12-07 kinaba: sum[y][x+1] = sum[y][x] + (board[y][x]=='o' ? 1 : 0); 46d6ab9496 2011-12-07 kinaba: 46d6ab9496 2011-12-07 kinaba: for(int x=0; x<W; ++x) 46d6ab9496 2011-12-07 kinaba: for(int X=x; X<=W; ++X) 46d6ab9496 2011-12-07 kinaba: for(int y=0; y<H; ++y) 46d6ab9496 2011-12-07 kinaba: for(int Y=y; Y<=H; ++Y) 46d6ab9496 2011-12-07 kinaba: { 46d6ab9496 2011-12-07 kinaba: // count 46d6ab9496 2011-12-07 kinaba: int cnt = 0; 46d6ab9496 2011-12-07 kinaba: for(int i=y; i<Y; ++i) 46d6ab9496 2011-12-07 kinaba: cnt += sum[i][X]-sum[i][x]; 46d6ab9496 2011-12-07 kinaba: if( cnt == K ) 46d6ab9496 2011-12-07 kinaba: { 46d6ab9496 2011-12-07 kinaba: int L = x; 46d6ab9496 2011-12-07 kinaba: int R = W-X; 46d6ab9496 2011-12-07 kinaba: int T = y; 46d6ab9496 2011-12-07 kinaba: int B = H-Y; 46d6ab9496 2011-12-07 kinaba: int move = L+R+min(L,R)+T+B+min(T,B); 46d6ab9496 2011-12-07 kinaba: best = min(best, move); 46d6ab9496 2011-12-07 kinaba: } 46d6ab9496 2011-12-07 kinaba: } 46d6ab9496 2011-12-07 kinaba: return best==INF ? -1 : best; 46d6ab9496 2011-12-07 kinaba: } 46d6ab9496 2011-12-07 kinaba: }; 46d6ab9496 2011-12-07 kinaba: 46d6ab9496 2011-12-07 kinaba: // BEGIN CUT HERE 46d6ab9496 2011-12-07 kinaba: #include <ctime> 46d6ab9496 2011-12-07 kinaba: double start_time; string timer() 46d6ab9496 2011-12-07 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 46d6ab9496 2011-12-07 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 46d6ab9496 2011-12-07 kinaba: { os << "{ "; 46d6ab9496 2011-12-07 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 46d6ab9496 2011-12-07 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 46d6ab9496 2011-12-07 kinaba: void verify_case(const int& Expected, const int& Received) { 46d6ab9496 2011-12-07 kinaba: bool ok = (Expected == Received); 46d6ab9496 2011-12-07 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 46d6ab9496 2011-12-07 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 46d6ab9496 2011-12-07 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 46d6ab9496 2011-12-07 kinaba: #define END verify_case(_, DropCoins().getMinimum(board, K));} 46d6ab9496 2011-12-07 kinaba: int main(){ 46d6ab9496 2011-12-07 kinaba: 46d6ab9496 2011-12-07 kinaba: CASE(0) 46d6ab9496 2011-12-07 kinaba: string board_[] = {".o.." 46d6ab9496 2011-12-07 kinaba: ,"oooo" 46d6ab9496 2011-12-07 kinaba: ,"..o."} 46d6ab9496 2011-12-07 kinaba: ; 46d6ab9496 2011-12-07 kinaba: vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); 46d6ab9496 2011-12-07 kinaba: int K = 3; 46d6ab9496 2011-12-07 kinaba: int _ = 2; 46d6ab9496 2011-12-07 kinaba: END 46d6ab9496 2011-12-07 kinaba: CASE(1) 46d6ab9496 2011-12-07 kinaba: string board_[] = {".....o" 46d6ab9496 2011-12-07 kinaba: ,"......" 46d6ab9496 2011-12-07 kinaba: ,"oooooo" 46d6ab9496 2011-12-07 kinaba: ,"oooooo" 46d6ab9496 2011-12-07 kinaba: ,"......" 46d6ab9496 2011-12-07 kinaba: ,"o....."} 46d6ab9496 2011-12-07 kinaba: ; 46d6ab9496 2011-12-07 kinaba: vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); 46d6ab9496 2011-12-07 kinaba: int K = 12; 46d6ab9496 2011-12-07 kinaba: int _ = 3; 46d6ab9496 2011-12-07 kinaba: END 46d6ab9496 2011-12-07 kinaba: CASE(2) 46d6ab9496 2011-12-07 kinaba: string board_[] = {"...." 46d6ab9496 2011-12-07 kinaba: ,".oo." 46d6ab9496 2011-12-07 kinaba: ,".oo." 46d6ab9496 2011-12-07 kinaba: ,"...."} 46d6ab9496 2011-12-07 kinaba: ; 46d6ab9496 2011-12-07 kinaba: vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); 46d6ab9496 2011-12-07 kinaba: int K = 3; 46d6ab9496 2011-12-07 kinaba: int _ = -1; 46d6ab9496 2011-12-07 kinaba: END 46d6ab9496 2011-12-07 kinaba: CASE(3) 46d6ab9496 2011-12-07 kinaba: string board_[] = {"......." 46d6ab9496 2011-12-07 kinaba: ,"..ooo.." 46d6ab9496 2011-12-07 kinaba: ,"ooooooo" 46d6ab9496 2011-12-07 kinaba: ,".oo.oo." 46d6ab9496 2011-12-07 kinaba: ,"oo...oo"} 46d6ab9496 2011-12-07 kinaba: ; 46d6ab9496 2011-12-07 kinaba: vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); 46d6ab9496 2011-12-07 kinaba: int K = 12; 46d6ab9496 2011-12-07 kinaba: int _ = 4; 46d6ab9496 2011-12-07 kinaba: END 46d6ab9496 2011-12-07 kinaba: CASE(4) 46d6ab9496 2011-12-07 kinaba: string board_[] = {"................." 46d6ab9496 2011-12-07 kinaba: ,".ooooooo...oooo.." 46d6ab9496 2011-12-07 kinaba: ,".ooooooo..oooooo." 46d6ab9496 2011-12-07 kinaba: ,".oo.......oo..oo." 46d6ab9496 2011-12-07 kinaba: ,".oo.......oo..oo." 46d6ab9496 2011-12-07 kinaba: ,".ooooo.....oooo.." 46d6ab9496 2011-12-07 kinaba: ,".ooooooo...oooo.." 46d6ab9496 2011-12-07 kinaba: ,".....ooo..oo..oo." 46d6ab9496 2011-12-07 kinaba: ,"......oo..oo..oo." 46d6ab9496 2011-12-07 kinaba: ,".ooooooo..oooooo." 46d6ab9496 2011-12-07 kinaba: ,".oooooo....oooo.." 46d6ab9496 2011-12-07 kinaba: ,"................."} 46d6ab9496 2011-12-07 kinaba: ; 46d6ab9496 2011-12-07 kinaba: vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); 46d6ab9496 2011-12-07 kinaba: int K = 58; 46d6ab9496 2011-12-07 kinaba: int _ = 6; 46d6ab9496 2011-12-07 kinaba: END 46d6ab9496 2011-12-07 kinaba: CASE(5) 46d6ab9496 2011-12-07 kinaba: string board_[] = {"oooooooooooooooooooooooooooooo", 46d6ab9496 2011-12-07 kinaba: "oooooooooooooooooooooooooooooo", 46d6ab9496 2011-12-07 kinaba: "oooooooooooooooooooooooooooooo", 46d6ab9496 2011-12-07 kinaba: "oooooooooooooooooooooooooooooo", 46d6ab9496 2011-12-07 kinaba: "oooooooooooooooooooooooooooooo", 46d6ab9496 2011-12-07 kinaba: "oooooooooooooooooooooooooooooo", 46d6ab9496 2011-12-07 kinaba: "oooooooooooooooooooooooooooooo", 46d6ab9496 2011-12-07 kinaba: "oooooooooooooooooooooooooooooo", 46d6ab9496 2011-12-07 kinaba: "oooooooooooooooooooooooooooooo", 46d6ab9496 2011-12-07 kinaba: "oooooooooooooooooooooooooooooo", 46d6ab9496 2011-12-07 kinaba: "oooooooooooooooooooooooooooooo", 46d6ab9496 2011-12-07 kinaba: "oooooooooooooooooooooooooooooo", 46d6ab9496 2011-12-07 kinaba: "oooooooooooooooooooooooooooooo", 46d6ab9496 2011-12-07 kinaba: "oooooooooooooooooooooooooooooo", 46d6ab9496 2011-12-07 kinaba: "oooooooooooooooooooooooooooooo", 46d6ab9496 2011-12-07 kinaba: "oooooooooooooooooooooooooooooo", 46d6ab9496 2011-12-07 kinaba: "oooooooooooooooooooooooooooooo", 46d6ab9496 2011-12-07 kinaba: "oooooooooooooooooooooooooooooo", 46d6ab9496 2011-12-07 kinaba: "oooooooooooooooooooooooooooooo", 46d6ab9496 2011-12-07 kinaba: "oooooooooooooooooooooooooooooo", 46d6ab9496 2011-12-07 kinaba: "oooooooooooooooooooooooooooooo", 46d6ab9496 2011-12-07 kinaba: "oooooooooooooooooooooooooooooo", 46d6ab9496 2011-12-07 kinaba: "oooooooooooooooooooooooooooooo", 46d6ab9496 2011-12-07 kinaba: "oooooooooooooooooooooooooooooo", 46d6ab9496 2011-12-07 kinaba: "oooooooooooooooooooooooooooooo", 46d6ab9496 2011-12-07 kinaba: "oooooooooooooooooooooooooooooo", 46d6ab9496 2011-12-07 kinaba: "oooooooooooooooooooooooooooooo", 46d6ab9496 2011-12-07 kinaba: "oooooooooooooooooooooooooooooo", 46d6ab9496 2011-12-07 kinaba: "oooooooooooooooooooooooooooooo", 46d6ab9496 2011-12-07 kinaba: "oooooooooooooooooooooooooooooo", 46d6ab9496 2011-12-07 kinaba: }; 46d6ab9496 2011-12-07 kinaba: vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); 46d6ab9496 2011-12-07 kinaba: int K = 1; 46d6ab9496 2011-12-07 kinaba: int _ = 58; 46d6ab9496 2011-12-07 kinaba: END 46d6ab9496 2011-12-07 kinaba: /* 46d6ab9496 2011-12-07 kinaba: CASE(6) 46d6ab9496 2011-12-07 kinaba: string board_[] = ; 46d6ab9496 2011-12-07 kinaba: vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); 46d6ab9496 2011-12-07 kinaba: int K = ; 46d6ab9496 2011-12-07 kinaba: int _ = ; 46d6ab9496 2011-12-07 kinaba: END 46d6ab9496 2011-12-07 kinaba: */ 46d6ab9496 2011-12-07 kinaba: } 46d6ab9496 2011-12-07 kinaba: // END CUT HERE