#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