Artifact Content
Not logged in

Artifact 284412eb4506862853b5f7b5e43f3de76d90d56a


#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 TileCutting {
public:
	int cuts(vector <string> layout) 
	{
		int san=0, ni=0, ic=0;
		for(int y=0; y<layout.size(); y+=2)
			for(int x=0; x<layout[0].size(); x+=2)
			{
				string s = layout[y].substr(x,2) + layout[y+1].substr(x,2);
				if( s==".xxx" || s=="x.xx" || s=="xx.x" || s=="xxx." )
					ic++;
				else if( s=="..xx" || s=="x.x." || s=="xx.." || s==".x.x" )
					ni++;
				else if( s=="x..x" || s==".xx." )
					ic+=2;
				else if( s=="x..." || s==".x.." || s=="..x." || s=="...x" )
					san++;
			}
		int mincut=0x7fffffff;
		for(int nk=0; nk<=san; ++nk)
			if(nk+nk/3>=san)
				mincut = min(mincut, calc(san,ni,ic,nk));
		return mincut;
	}

	int calc(int san, int ni, int ic, int nk) {
		// create nk pieces of L-shaped block
		// reuse nk pieces of single-block to form the rest of neede L-blocks
		int cut   = nk*2;
		int piece = nk-(san-nk)*3;  // single-block piecese left

		// form single-blocks
		int pi = min(ic, piece);
		ic    -= pi;
		piece -= pi;

		// if still left, use single-blocks to form I-shaped blocks
		if( piece )
		{
			ni    -= piece/2;
			piece -= piece/2*2;
		}

		// create I-shaped blocks
		int xpiece = 0;
		if(ni) {
			cut  +=  (ni+1)/2*2;
			xpiece = ni%2 ? 1 : 0;
		}

		// create single-blocks
		pi = min(ic, piece);
		ic    -= pi;
		piece -= pi;
		if( ic ) {
			if( xpiece ) ic-=2, cut+=1;
			if(ic>0)
				cut += ic/4*4 + ic%4 + (ic%4==0 ? 0 : 1);
		}
		return cut;
	}
};

// 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> 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(); }
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;}

template<int N> struct Case_ { Case_(){start_time=clock();} };
char Test_(...);
int Test_(Case_<0>) {
	string layout_[] = { "..",
  ".." };
	  vector <string> layout(layout_, layout_+sizeof(layout_)/sizeof(*layout_)); 
	int RetVal = 0; 
	return verify_case(RetVal, TileCutting().cuts(layout)); }
int Test_(Case_<1>) {
	string layout_[] = { "x.",
  ".." };
	  vector <string> layout(layout_, layout_+sizeof(layout_)/sizeof(*layout_)); 
	int RetVal = 2; 
	return verify_case(RetVal, TileCutting().cuts(layout)); }
int Test_(Case_<2>) {
	string layout_[] = { ".x",
  "xx" };
	  vector <string> layout(layout_, layout_+sizeof(layout_)/sizeof(*layout_)); 
	int RetVal = 2; 
	return verify_case(RetVal, TileCutting().cuts(layout)); }
int Test_(Case_<3>) {
	string layout_[] = { "xxxx..xxxx",
  "x..x..xx..",
  "x..xxxxx..",
  "xxxxxxxxxx" };
	  vector <string> layout(layout_, layout_+sizeof(layout_)/sizeof(*layout_)); 
	int RetVal = 6; 
	return verify_case(RetVal, TileCutting().cuts(layout)); }
int Test_(Case_<4>) {
	string layout_[] = { "xxxxxx",
  "x....x" };
	  vector <string> layout(layout_, layout_+sizeof(layout_)/sizeof(*layout_)); 
	int RetVal = 3; 
	return verify_case(RetVal, TileCutting().cuts(layout)); }
int Test_(Case_<5>) {
	string layout_[] = { "x..x....",
  "x..xx...",
  "..xx....",
  "...x....",
  "......xx",
  "......xx" };
	  vector <string> layout(layout_, layout_+sizeof(layout_)/sizeof(*layout_)); 
	int RetVal = 4; 
	return verify_case(RetVal, TileCutting().cuts(layout)); }
int Test_(Case_<6>) {
	string layout_[] = { "x..xx.x..x.xx..x.xx.",
  "..x..x..x.x..xx...x.",
  ".xx...x...x...x..x..",
  ".xx...x.x.x...x..xx.",
  ".x..x...x.....x...x.",
  ".x.x.x..x..x..x..x.x",
  "...x.x.x.x.x.x.x...x",
  ".x..x..x...x..x...x.",
  "...x.x.x..x.x.x.....",
  "...x.x.x..x.x.xxx.x.",
  "xx.xx.xx.x.x.x.x..x.",
  ".x..xxx...x.xx...x.x",
  "xx..x.x...x.x.x.x..x",
  ".xx..x.xx.xxxxx...xx",
  "x....x.x...x...x.x..",
  ".x.xx.x..x.x.xxx.x..",
  "...xx.xxx.....xx.xxx",
  ".xx..x..xx.x...x.xx.",
  "x.x...x.x.xx.x..x.xx",
  ".....xx.x.......xx.x",
  "x...x.xx.x..x....x..",
  ".x..xxx.....x.x.x.xx" }
;
	  vector <string> layout(layout_, layout_+sizeof(layout_)/sizeof(*layout_)); 
	int RetVal = 121; 
	return verify_case(RetVal, TileCutting().cuts(layout)); }
int Test_(Case_<7>) {
	string layout_[] = { "..................................................",
  "..................................................",
  "..................................................",
  "..................................................",
  "..................................................",
  "..................................................",
  "..................................................",
  "..................................................",
  "..................................................",
  "..................................................",
  "..................................................",
  "..................................................",
  "..................................................",
  "..................................................",
  "..................................................",
  "..................................................",
  "..................................................",
  "..................................................",
  "..................................................",
  "..................................................",
  "..................................................",
  "..................................................",
  "..................................................",
  "..................................................",
  "..................................................",
  "..................................................",
  "..................................................",
  "..................................................",
  "..................................................",
  "..................................................",
  "..................................................",
  "..................................................",
  "..................................................",
  "..................................................",
  "..................................................",
  "..................................................",
  "..................................................",
  "..................................................",
  "..................................................",
  "..................................................",
  "..................................................",
  "..................................................",
  "..................................................",
  "..................................................",
  "..................................................",
  "..................................................",
  "..................................................",
  "..................................................",
  "..................................................",
  ".................................................." }
;
	  vector <string> layout(layout_, layout_+sizeof(layout_)/sizeof(*layout_)); 
	int RetVal = 0; 
	return verify_case(RetVal, TileCutting().cuts(layout)); }
int Test_(Case_<8>) {
	string layout_[] = 
{"x..x...x...x..x....x",
 ".x..x.xxx....xx..x..",
 "..x...x..x...xxx....",
 "x....x.....xx..xx...",
 "..x.x...x..x........",
 ".x...xx.xx...xxx...x",
 "x..x.x......xx.x....",
 "...xxx.....x.x..xx.."}
;
	  vector <string> layout(layout_, layout_+sizeof(layout_)/sizeof(*layout_)); 
	int RetVal = 44; 
	return verify_case(RetVal, TileCutting().cuts(layout)); }

template<int N> void Run_() { cerr << "Test Case #" << N << "..." << flush; Test_(Case_<N>()); Run_<sizeof(Test_(Case_<N+1>()))==1 ? -1 : N+1>(); }
template<>      void Run_<-1>() {}
int main() { Run_<0>(); }
// END CUT HERE