4fd800b3a8 2011-02-23 kinaba: #include <iostream> 4fd800b3a8 2011-02-23 kinaba: #include <sstream> 4fd800b3a8 2011-02-23 kinaba: #include <iomanip> 4fd800b3a8 2011-02-23 kinaba: #include <vector> 4fd800b3a8 2011-02-23 kinaba: #include <string> 4fd800b3a8 2011-02-23 kinaba: #include <map> 4fd800b3a8 2011-02-23 kinaba: #include <set> 4fd800b3a8 2011-02-23 kinaba: #include <algorithm> 4fd800b3a8 2011-02-23 kinaba: #include <numeric> 4fd800b3a8 2011-02-23 kinaba: #include <iterator> 4fd800b3a8 2011-02-23 kinaba: #include <functional> 4fd800b3a8 2011-02-23 kinaba: #include <complex> 4fd800b3a8 2011-02-23 kinaba: #include <queue> 4fd800b3a8 2011-02-23 kinaba: #include <stack> 4fd800b3a8 2011-02-23 kinaba: #include <cmath> 4fd800b3a8 2011-02-23 kinaba: #include <cassert> 4fd800b3a8 2011-02-23 kinaba: #include <cstring> 4fd800b3a8 2011-02-23 kinaba: using namespace std; 4fd800b3a8 2011-02-23 kinaba: typedef long long LL; 4fd800b3a8 2011-02-23 kinaba: typedef complex<double> CMP; 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: class TileCutting { 4fd800b3a8 2011-02-23 kinaba: public: 4fd800b3a8 2011-02-23 kinaba: int cuts(vector <string> layout) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: int san=0, ni=0, ic=0; 4fd800b3a8 2011-02-23 kinaba: for(int y=0; y<layout.size(); y+=2) 4fd800b3a8 2011-02-23 kinaba: for(int x=0; x<layout[0].size(); x+=2) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: string s = layout[y].substr(x,2) + layout[y+1].substr(x,2); 4fd800b3a8 2011-02-23 kinaba: if( s==".xxx" || s=="x.xx" || s=="xx.x" || s=="xxx." ) 4fd800b3a8 2011-02-23 kinaba: ic++; 4fd800b3a8 2011-02-23 kinaba: else if( s=="..xx" || s=="x.x." || s=="xx.." || s==".x.x" ) 4fd800b3a8 2011-02-23 kinaba: ni++; 4fd800b3a8 2011-02-23 kinaba: else if( s=="x..x" || s==".xx." ) 4fd800b3a8 2011-02-23 kinaba: ic+=2; 4fd800b3a8 2011-02-23 kinaba: else if( s=="x..." || s==".x.." || s=="..x." || s=="...x" ) 4fd800b3a8 2011-02-23 kinaba: san++; 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: int mincut=0x7fffffff; 4fd800b3a8 2011-02-23 kinaba: for(int nk=0; nk<=san; ++nk) 4fd800b3a8 2011-02-23 kinaba: if(nk+nk/3>=san) 4fd800b3a8 2011-02-23 kinaba: mincut = min(mincut, calc(san,ni,ic,nk)); 4fd800b3a8 2011-02-23 kinaba: return mincut; 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: int calc(int san, int ni, int ic, int nk) { 4fd800b3a8 2011-02-23 kinaba: // create nk pieces of L-shaped block 4fd800b3a8 2011-02-23 kinaba: // reuse nk pieces of single-block to form the rest of neede L-blocks 4fd800b3a8 2011-02-23 kinaba: int cut = nk*2; 4fd800b3a8 2011-02-23 kinaba: int piece = nk-(san-nk)*3; // single-block piecese left 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: // form single-blocks 4fd800b3a8 2011-02-23 kinaba: int pi = min(ic, piece); 4fd800b3a8 2011-02-23 kinaba: ic -= pi; 4fd800b3a8 2011-02-23 kinaba: piece -= pi; 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: // if still left, use single-blocks to form I-shaped blocks 4fd800b3a8 2011-02-23 kinaba: if( piece ) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: ni -= piece/2; 4fd800b3a8 2011-02-23 kinaba: piece -= piece/2*2; 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: // create I-shaped blocks 4fd800b3a8 2011-02-23 kinaba: int xpiece = 0; 4fd800b3a8 2011-02-23 kinaba: if(ni) { 4fd800b3a8 2011-02-23 kinaba: cut += (ni+1)/2*2; 4fd800b3a8 2011-02-23 kinaba: xpiece = ni%2 ? 1 : 0; 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: // create single-blocks 4fd800b3a8 2011-02-23 kinaba: pi = min(ic, piece); 4fd800b3a8 2011-02-23 kinaba: ic -= pi; 4fd800b3a8 2011-02-23 kinaba: piece -= pi; 4fd800b3a8 2011-02-23 kinaba: if( ic ) { 4fd800b3a8 2011-02-23 kinaba: if( xpiece ) ic-=2, cut+=1; 4fd800b3a8 2011-02-23 kinaba: if(ic>0) 4fd800b3a8 2011-02-23 kinaba: cut += ic/4*4 + ic%4 + (ic%4==0 ? 0 : 1); 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: return cut; 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: }; 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: // BEGIN CUT HERE 4fd800b3a8 2011-02-23 kinaba: #include <ctime> 4fd800b3a8 2011-02-23 kinaba: double start_time;string timer() { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); } 4fd800b3a8 2011-02-23 kinaba: int verify_case(const int &Expected, const int &Received) { if (Expected == Received) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; cerr << "\tExpected: \"" << Expected << '\"' << endl; cerr << "\tReceived: \"" << Received << '\"' << endl; } return 0;} 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: template<int N> struct Case_ { Case_(){start_time=clock();} }; 4fd800b3a8 2011-02-23 kinaba: char Test_(...); 4fd800b3a8 2011-02-23 kinaba: int Test_(Case_<0>) { 4fd800b3a8 2011-02-23 kinaba: string layout_[] = { "..", 4fd800b3a8 2011-02-23 kinaba: ".." }; 4fd800b3a8 2011-02-23 kinaba: vector <string> layout(layout_, layout_+sizeof(layout_)/sizeof(*layout_)); 4fd800b3a8 2011-02-23 kinaba: int RetVal = 0; 4fd800b3a8 2011-02-23 kinaba: return verify_case(RetVal, TileCutting().cuts(layout)); } 4fd800b3a8 2011-02-23 kinaba: int Test_(Case_<1>) { 4fd800b3a8 2011-02-23 kinaba: string layout_[] = { "x.", 4fd800b3a8 2011-02-23 kinaba: ".." }; 4fd800b3a8 2011-02-23 kinaba: vector <string> layout(layout_, layout_+sizeof(layout_)/sizeof(*layout_)); 4fd800b3a8 2011-02-23 kinaba: int RetVal = 2; 4fd800b3a8 2011-02-23 kinaba: return verify_case(RetVal, TileCutting().cuts(layout)); } 4fd800b3a8 2011-02-23 kinaba: int Test_(Case_<2>) { 4fd800b3a8 2011-02-23 kinaba: string layout_[] = { ".x", 4fd800b3a8 2011-02-23 kinaba: "xx" }; 4fd800b3a8 2011-02-23 kinaba: vector <string> layout(layout_, layout_+sizeof(layout_)/sizeof(*layout_)); 4fd800b3a8 2011-02-23 kinaba: int RetVal = 2; 4fd800b3a8 2011-02-23 kinaba: return verify_case(RetVal, TileCutting().cuts(layout)); } 4fd800b3a8 2011-02-23 kinaba: int Test_(Case_<3>) { 4fd800b3a8 2011-02-23 kinaba: string layout_[] = { "xxxx..xxxx", 4fd800b3a8 2011-02-23 kinaba: "x..x..xx..", 4fd800b3a8 2011-02-23 kinaba: "x..xxxxx..", 4fd800b3a8 2011-02-23 kinaba: "xxxxxxxxxx" }; 4fd800b3a8 2011-02-23 kinaba: vector <string> layout(layout_, layout_+sizeof(layout_)/sizeof(*layout_)); 4fd800b3a8 2011-02-23 kinaba: int RetVal = 6; 4fd800b3a8 2011-02-23 kinaba: return verify_case(RetVal, TileCutting().cuts(layout)); } 4fd800b3a8 2011-02-23 kinaba: int Test_(Case_<4>) { 4fd800b3a8 2011-02-23 kinaba: string layout_[] = { "xxxxxx", 4fd800b3a8 2011-02-23 kinaba: "x....x" }; 4fd800b3a8 2011-02-23 kinaba: vector <string> layout(layout_, layout_+sizeof(layout_)/sizeof(*layout_)); 4fd800b3a8 2011-02-23 kinaba: int RetVal = 3; 4fd800b3a8 2011-02-23 kinaba: return verify_case(RetVal, TileCutting().cuts(layout)); } 4fd800b3a8 2011-02-23 kinaba: int Test_(Case_<5>) { 4fd800b3a8 2011-02-23 kinaba: string layout_[] = { "x..x....", 4fd800b3a8 2011-02-23 kinaba: "x..xx...", 4fd800b3a8 2011-02-23 kinaba: "..xx....", 4fd800b3a8 2011-02-23 kinaba: "...x....", 4fd800b3a8 2011-02-23 kinaba: "......xx", 4fd800b3a8 2011-02-23 kinaba: "......xx" }; 4fd800b3a8 2011-02-23 kinaba: vector <string> layout(layout_, layout_+sizeof(layout_)/sizeof(*layout_)); 4fd800b3a8 2011-02-23 kinaba: int RetVal = 4; 4fd800b3a8 2011-02-23 kinaba: return verify_case(RetVal, TileCutting().cuts(layout)); } 4fd800b3a8 2011-02-23 kinaba: int Test_(Case_<6>) { 4fd800b3a8 2011-02-23 kinaba: string layout_[] = { "x..xx.x..x.xx..x.xx.", 4fd800b3a8 2011-02-23 kinaba: "..x..x..x.x..xx...x.", 4fd800b3a8 2011-02-23 kinaba: ".xx...x...x...x..x..", 4fd800b3a8 2011-02-23 kinaba: ".xx...x.x.x...x..xx.", 4fd800b3a8 2011-02-23 kinaba: ".x..x...x.....x...x.", 4fd800b3a8 2011-02-23 kinaba: ".x.x.x..x..x..x..x.x", 4fd800b3a8 2011-02-23 kinaba: "...x.x.x.x.x.x.x...x", 4fd800b3a8 2011-02-23 kinaba: ".x..x..x...x..x...x.", 4fd800b3a8 2011-02-23 kinaba: "...x.x.x..x.x.x.....", 4fd800b3a8 2011-02-23 kinaba: "...x.x.x..x.x.xxx.x.", 4fd800b3a8 2011-02-23 kinaba: "xx.xx.xx.x.x.x.x..x.", 4fd800b3a8 2011-02-23 kinaba: ".x..xxx...x.xx...x.x", 4fd800b3a8 2011-02-23 kinaba: "xx..x.x...x.x.x.x..x", 4fd800b3a8 2011-02-23 kinaba: ".xx..x.xx.xxxxx...xx", 4fd800b3a8 2011-02-23 kinaba: "x....x.x...x...x.x..", 4fd800b3a8 2011-02-23 kinaba: ".x.xx.x..x.x.xxx.x..", 4fd800b3a8 2011-02-23 kinaba: "...xx.xxx.....xx.xxx", 4fd800b3a8 2011-02-23 kinaba: ".xx..x..xx.x...x.xx.", 4fd800b3a8 2011-02-23 kinaba: "x.x...x.x.xx.x..x.xx", 4fd800b3a8 2011-02-23 kinaba: ".....xx.x.......xx.x", 4fd800b3a8 2011-02-23 kinaba: "x...x.xx.x..x....x..", 4fd800b3a8 2011-02-23 kinaba: ".x..xxx.....x.x.x.xx" } 4fd800b3a8 2011-02-23 kinaba: ; 4fd800b3a8 2011-02-23 kinaba: vector <string> layout(layout_, layout_+sizeof(layout_)/sizeof(*layout_)); 4fd800b3a8 2011-02-23 kinaba: int RetVal = 121; 4fd800b3a8 2011-02-23 kinaba: return verify_case(RetVal, TileCutting().cuts(layout)); } 4fd800b3a8 2011-02-23 kinaba: int Test_(Case_<7>) { 4fd800b3a8 2011-02-23 kinaba: string layout_[] = { "..................................................", 4fd800b3a8 2011-02-23 kinaba: "..................................................", 4fd800b3a8 2011-02-23 kinaba: "..................................................", 4fd800b3a8 2011-02-23 kinaba: "..................................................", 4fd800b3a8 2011-02-23 kinaba: "..................................................", 4fd800b3a8 2011-02-23 kinaba: "..................................................", 4fd800b3a8 2011-02-23 kinaba: "..................................................", 4fd800b3a8 2011-02-23 kinaba: "..................................................", 4fd800b3a8 2011-02-23 kinaba: "..................................................", 4fd800b3a8 2011-02-23 kinaba: "..................................................", 4fd800b3a8 2011-02-23 kinaba: "..................................................", 4fd800b3a8 2011-02-23 kinaba: "..................................................", 4fd800b3a8 2011-02-23 kinaba: "..................................................", 4fd800b3a8 2011-02-23 kinaba: "..................................................", 4fd800b3a8 2011-02-23 kinaba: "..................................................", 4fd800b3a8 2011-02-23 kinaba: "..................................................", 4fd800b3a8 2011-02-23 kinaba: "..................................................", 4fd800b3a8 2011-02-23 kinaba: "..................................................", 4fd800b3a8 2011-02-23 kinaba: "..................................................", 4fd800b3a8 2011-02-23 kinaba: "..................................................", 4fd800b3a8 2011-02-23 kinaba: "..................................................", 4fd800b3a8 2011-02-23 kinaba: "..................................................", 4fd800b3a8 2011-02-23 kinaba: "..................................................", 4fd800b3a8 2011-02-23 kinaba: "..................................................", 4fd800b3a8 2011-02-23 kinaba: "..................................................", 4fd800b3a8 2011-02-23 kinaba: "..................................................", 4fd800b3a8 2011-02-23 kinaba: "..................................................", 4fd800b3a8 2011-02-23 kinaba: "..................................................", 4fd800b3a8 2011-02-23 kinaba: "..................................................", 4fd800b3a8 2011-02-23 kinaba: "..................................................", 4fd800b3a8 2011-02-23 kinaba: "..................................................", 4fd800b3a8 2011-02-23 kinaba: "..................................................", 4fd800b3a8 2011-02-23 kinaba: "..................................................", 4fd800b3a8 2011-02-23 kinaba: "..................................................", 4fd800b3a8 2011-02-23 kinaba: "..................................................", 4fd800b3a8 2011-02-23 kinaba: "..................................................", 4fd800b3a8 2011-02-23 kinaba: "..................................................", 4fd800b3a8 2011-02-23 kinaba: "..................................................", 4fd800b3a8 2011-02-23 kinaba: "..................................................", 4fd800b3a8 2011-02-23 kinaba: "..................................................", 4fd800b3a8 2011-02-23 kinaba: "..................................................", 4fd800b3a8 2011-02-23 kinaba: "..................................................", 4fd800b3a8 2011-02-23 kinaba: "..................................................", 4fd800b3a8 2011-02-23 kinaba: "..................................................", 4fd800b3a8 2011-02-23 kinaba: "..................................................", 4fd800b3a8 2011-02-23 kinaba: "..................................................", 4fd800b3a8 2011-02-23 kinaba: "..................................................", 4fd800b3a8 2011-02-23 kinaba: "..................................................", 4fd800b3a8 2011-02-23 kinaba: "..................................................", 4fd800b3a8 2011-02-23 kinaba: ".................................................." } 4fd800b3a8 2011-02-23 kinaba: ; 4fd800b3a8 2011-02-23 kinaba: vector <string> layout(layout_, layout_+sizeof(layout_)/sizeof(*layout_)); 4fd800b3a8 2011-02-23 kinaba: int RetVal = 0; 4fd800b3a8 2011-02-23 kinaba: return verify_case(RetVal, TileCutting().cuts(layout)); } 4fd800b3a8 2011-02-23 kinaba: int Test_(Case_<8>) { 4fd800b3a8 2011-02-23 kinaba: string layout_[] = 4fd800b3a8 2011-02-23 kinaba: {"x..x...x...x..x....x", 4fd800b3a8 2011-02-23 kinaba: ".x..x.xxx....xx..x..", 4fd800b3a8 2011-02-23 kinaba: "..x...x..x...xxx....", 4fd800b3a8 2011-02-23 kinaba: "x....x.....xx..xx...", 4fd800b3a8 2011-02-23 kinaba: "..x.x...x..x........", 4fd800b3a8 2011-02-23 kinaba: ".x...xx.xx...xxx...x", 4fd800b3a8 2011-02-23 kinaba: "x..x.x......xx.x....", 4fd800b3a8 2011-02-23 kinaba: "...xxx.....x.x..xx.."} 4fd800b3a8 2011-02-23 kinaba: ; 4fd800b3a8 2011-02-23 kinaba: vector <string> layout(layout_, layout_+sizeof(layout_)/sizeof(*layout_)); 4fd800b3a8 2011-02-23 kinaba: int RetVal = 44; 4fd800b3a8 2011-02-23 kinaba: return verify_case(RetVal, TileCutting().cuts(layout)); } 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: template<int N> void Run_() { cerr << "Test Case #" << N << "..." << flush; Test_(Case_<N>()); Run_<sizeof(Test_(Case_<N+1>()))==1 ? -1 : N+1>(); } 4fd800b3a8 2011-02-23 kinaba: template<> void Run_<-1>() {} 4fd800b3a8 2011-02-23 kinaba: int main() { Run_<0>(); } 4fd800b3a8 2011-02-23 kinaba: // END CUT HERE 4fd800b3a8 2011-02-23 kinaba: