Artifact Content
Not logged in

Artifact 3917b4343fc07af59d9a4214fa0cd022e3f55056


#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 BedroomFloor { public:
	LL b[6];

	long long numberOfSticks(int x1, int y1, int x2, int y2) 
	{
		b[1] = b[2] = b[3] = b[4] = b[5] = 0;

		devideX_and_count(x1, x2, y1, y2);
		return optimize();
	}

	// utils
	LL FLOOR(LL x) { return x/5*5; }
	LL CEIL (LL x) { return FLOOR(x+4); }

	// counting routines
	void devideX_and_count(LL x1, LL x2, LL y1, LL y2)
	{
		if( FLOOR(x1) == FLOOR(x2) )
			devideY_and_count(x1, x2, y1, y2, 1);
		else
			devideY_and_count(         x1,    CEIL(x1), y1, y2, 1 ),
			devideY_and_count(   CEIL(x1),  CEIL(x1)+5, y1, y2, ((FLOOR(x2)-CEIL(x1))/5+1)/2 ),
			devideY_and_count( CEIL(x1)+5, CEIL(x1)+10, y1, y2, ((FLOOR(x2)-CEIL(x1))/5+0)/2 ),
			devideY_and_count(  FLOOR(x2),          x2, y1, y2, 1 );
	}

	void devideY_and_count(LL x1, LL x2, LL y1, LL y2, LL rep)
	{
		if( FLOOR(y1) == FLOOR(y2) )
			count(x1, x2, y1, y2, rep);
		else
			count(x1, x2,         y1,    CEIL(y1), rep),
			count(x1, x2,   CEIL(y1),  CEIL(y1)+5, rep*(((FLOOR(y2)-CEIL(y1))/5+1)/2) ),
			count(x1, x2, CEIL(y1)+5, CEIL(y1)+10, rep*(((FLOOR(y2)-CEIL(y1))/5+0)/2) ),
			count(x1, x2,  FLOOR(y2),         y2 , rep);
	}

	void count(LL x1, LL x2, LL y1, LL y2, LL rep)
	{
		if( x1/5%2 == y1/5%2 ) // is_horizontal
			b[x2-x1] += rep*(y2-y1);
		else
			b[y2-y1] += rep*(x2-x1);
	}

	// compute minimum number of 1x5 blocks required (by greedily removing larger blocks)
	LL optimize()
	{
		LL total = 0;
		for(int K=6*6*6*6*6; --K>0; )
		{
			int k[] = {-1, K%6, K/6%6, K/6/6%6, K/6/6/6%6, K/6/6/6/6%6};
			if( 1*k[1] + 2*k[2] + 3*k[3] + 4*k[4] + 5*k[5] <= 5 )
			{
				LL n = 1LL<<62;
				for(int i=1; i<=5; ++i)
					if( k[i] )
						n = min(n, b[i]/k[i]);
				for(int i=1; i<=5; ++i)
					b[i] -= n*k[i];
				total += n;
			}
		}
		return total;
	}
};

// 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> ostream& operator<<(ostream& os, const vector<T>& v)
 { os << "{ ";
   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
void verify_case(const long long& Expected, const long long& Received) {
 bool ok = (Expected == Received);
 if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
#define END	 verify_case(_, BedroomFloor().numberOfSticks(x1, y1, x2, y2));}
int main(){

CASE(0)
	int x1 = 0; 
	int y1 = 0; 
	int x2 = 5; 
	int y2 = 5; 
	long long _ = 5LL; 
END
CASE(1)
	int x1 = 0; 
	int y1 = 0; 
	int x2 = 10; 
	int y2 = 2; 
	long long _ = 5LL; 
END
CASE(2)
	int x1 = 2; 
	int y1 = 2; 
	int x2 = 8; 
	int y2 = 8; 
	long long _ = 12LL; 
END
CASE(3)
	int x1 = 8; 
	int y1 = 5; 
	int x2 = 20; 
	int y2 = 16; 
	long long _ = 27LL; 
END
CASE(4)
	int x1 = 0; 
	int y1 = 0; 
	int x2 = 1000000; 
	int y2 = 1000000; 
	long long _ = 200000000000LL; 
END
CASE(5)
	int x1 = 1; 
	int y1 = 4; 
	int x2 = 20; 
	int y2 = 19; 
	long long _ = 58LL; 
END
CASE(5)
	int x1 = 49; 
	int y1 = 51; 
	int x2 = 64; 
	int y2 = 70; 
	long long _ = 58LL; 
END

}
// END CUT HERE