/* cmd /V:ON
    SetEnv.Cmd /Vista /x64 /Release
    cl "$F" /EHsc /O2 /Oi /Ot /Ox /favor:AMD64 /GS- /GR- /GL /Z7
*/
/*
	   0123456789ABC|D
	 0 □□□□□□□□□□□□□ □
	 1 □□□□□□□□□□□□□ □
	 2 □□□□□□□□□□□□□ □
	 3 □□□□□□□□□□□□□ □
	 4 □□□□□□■□□□□□□ □
	 5 □□□□□□■□□□□□□ □
	 6 □□□□□□□□□□□□□ □
	 7 □□□□□□□□□□□□□ □
	 8 □□□□□□□□□□□□□ □
	 9 □□□□□□□□□□□□□ □
	10 □□□□□□□□□□□□□ □
	11 □□□□□□□□□□□□□ □
	--
	12 □□□□□□□□□□□□□ □

	横 size*2-3 +1 (extra 1 line is for EndRecurrence)
	縦 size*2-4 +1 (extra 1 line is for EndRecurrence)
	S (size-2, size-4) 0-origin
*/
#include <vector>
#include <utility> // pair
#include <algorithm> // sort, unique
#include <iostream> // cout, endl
#include <iomanip> // setprecision

const int Size = 15;
const int BoardWidth = Size*2-2;
const int BoardHeight = Size*2-3;
static char g_board[BoardWidth*BoardHeight];

static std::vector<std::vector<std::pair<char,char> > > g_contact_points;
static std::vector<char> g_protein(Size, 0);
static long g_sum_of_cp = 0;

inline int Index(int x, int y)
{
	return x + y*BoardWidth;
}

inline bool CanMove(int x, int y)
{
	return g_board[Index(x,y)] == 0;
}

inline bool Reached(int x, int y)
{
	return g_board[Index(x,y)] != 0;
}

void EndRecurrence()
{
	std::vector<std::pair<char,char>> cpts;
	cpts.reserve(22);

	for(int x = 0; x != BoardWidth-1; ++x)
	for(int y = 0; y != BoardHeight-1; ++y) {
		if (! Reached(x,y)) {
			continue;
		}
		char i = g_board[Index(x,y)]-1;
		if (Reached(x+1,y)) {
			char j = g_board[Index(x+1,y)]-1;
			cpts.push_back(std::make_pair(i<j?i:j, i<j?j:i));
		}
		if (Reached(x,y+1)) {
			char j = g_board[Index(x,y+1)]-1;
			cpts.push_back(std::make_pair(i<j?i:j, i<j?j:i));
		}
	}

	struct {
		bool operator()(std::pair<char,char> l, std::pair<char,char> r) {
			return (int(l.first)<<8)+l.second <= (int(r.first)<<8)+r.second;
		}
	} sorter;
	std::sort(cpts.begin(), cpts.end(), sorter);

	g_contact_points.push_back(cpts);
}

void RecursiveMove(int x0, int y0, int x, int y, int limit)
{
	g_board[Index(x,y)] = g_board[Index(x0,y0)]+1;
	limit -= 1;
	if (limit == 0) {
		EndRecurrence();
	} else if (0 < limit) {
		if (CanMove(x+1,y)) { RecursiveMove(x,y, x+1,y, limit); };
		if (CanMove(x-1,y)) { RecursiveMove(x,y, x-1,y, limit); };
		if (CanMove(x,y+1)) { RecursiveMove(x,y, x,y+1, limit); };
		if (CanMove(x,y-1)) { RecursiveMove(x,y, x,y-1, limit); };
	}
	g_board[Index(x,y)] = 0;
}

void EndFlip()
{
	int contact_point = 0;

	for (std::vector<std::vector<std::pair<char,char> > >::iterator it = g_contact_points.begin(); it != g_contact_points.end(); ++it) {
		int acceptable_mishit = it->size() - contact_point - 1;
		if (acceptable_mishit < 0) {
			break;
		}
		for (unsigned i = 0; i != it->size(); ++i) {
			if (! g_protein[(*it)[i].first] || ! g_protein[(*it)[i].second]) {
				acceptable_mishit -= 1;
				if (acceptable_mishit < 0) {
					break;
				}
			}
		}
		if (0 <= acceptable_mishit) {
			contact_point += acceptable_mishit + 1;
		}
	}

	g_sum_of_cp += contact_point;
}

void Flip(int i)
{
	if (i == Size-1) {
		EndFlip();
		g_protein[i] = 1;
		EndFlip();
		g_protein[i] = 0;
	} else if (i < Size-1) {
		Flip(i+1);
		g_protein[i] = 1;
		Flip(i+1);
		g_protein[i] = 0;
	}
}

int main()
{
	g_board[Index(Size-2, Size-4)] = 1; // start
	RecursiveMove(Size-2, Size-4, Size-2, Size-3, Size-1);
	std::cout << "folding pattern: " << g_contact_points.size() << std::endl;

	std::sort(g_contact_points.begin(), g_contact_points.end());
	g_contact_points.resize(std::distance(g_contact_points.begin(), std::unique(g_contact_points.begin(), g_contact_points.end())));
	struct {
		bool operator()(const std::vector<std::pair<char,char> >& cpts) {
			struct superset_of {
				const std::vector<std::pair<char,char> >& cpts;
				superset_of(const std::vector<std::pair<char,char> >& cpts) : cpts(cpts) {}
				bool operator()(const std::vector<std::pair<char,char> >& _) {
					return cpts.size() < _.size() && std::includes(_.begin(), _.end(), cpts.begin(), cpts.end());
				}
			};
			return std::any_of(g_contact_points.begin(), g_contact_points.end(), superset_of(cpts));
		}
	} remover;
	g_contact_points.resize(std::distance(g_contact_points.begin(), std::remove_if(g_contact_points.begin(), g_contact_points.end(), remover)));
	struct {
		bool operator()(const std::vector<std::pair<char,char> >& l, const std::vector<std::pair<char,char> >& r) {
			return l.size() > r.size();
		}
	} sorter;
	std::sort(g_contact_points.begin(), g_contact_points.end(), sorter);
	std::cout << "folding pattern: " << g_contact_points.size() << std::endl;

	Flip(0);
	std::cout << g_sum_of_cp << std::endl;
	std::cout << std::setprecision(120) << (1.0*g_sum_of_cp/(1<<Size)) << std::endl;
}