记录编号	328593	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2015]斗地主	最终得分	100
用户昵称	Smile	是否通过	通过
代码语言	C++	运行时间	0.040 s
提交时间	2016-10-24 14:19:50	内存使用	0.31 MiB

#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;

const int maxn=18;
const int INF=0x3f3f3f3f;

int a[maxn], ans=INF;
int T, n;

void Find_SZ(vector<int>& G, int& L, int& R) {
	L=0, R=0;
	int i=3;
	while((i+5-1)<=14) {
		int j=i;
		while(a[j]) j++;
		if(j-i-1>R-L) L=i, R=j-1;
		if(j>i) i=j;
		else i++;
	}
	if(R-L+1>=5) { 
		G.push_back(L);
	}
}

void Find_IV(vector<int>& G) {
	int select=0;
	for(int i=3; i<=16; i++) {
		if(a[i]>=4) {
			select=i; break;
		}
	}
	if(!select) return;
	
	G.push_back(select); G.push_back(select);
	G.push_back(select); G.push_back(select);
	
	int s1=0, s2=0;
	for(int i=3; i<=16; i++) {
		if(a[i]==1) {
			if(!s1) s1=i;
			else {
				s2=i; break;
			}
		}
	}
	if(s1 && s2) {
		G.push_back(s1); G.push_back(s2);
		return;
	}
	
	int h1=0, h2=0;
	for(int i=3; i<=16; i++) {
		if(a[i]==2) {
			if(!h1) h1=i;
			else {
				h2=i; break;
			}
		}
	}
	if(h1 && h2) {
		G.push_back(h1); G.push_back(h1);
		G.push_back(h2); G.push_back(h2);
		return;
	}
	
	if(h1) {
		G.push_back(h1); G.push_back(h1);
	}
	
}

void Find_II(vector<int>& G, int& L, int& R) {
	L=0, R=0;
	int i=3;
	while(i<=12) {
		int j=i;
		while(a[j]>=2) j++;
		if(j-i-1>R-L) L=i, R=j-1;
		if(j>i) i=j;
		else i++;
	}
	if(R-L+1>=3) {
		G.push_back(L); 
	}
}

void Find_III(vector<int>& G) {           
	int select=0;						  
	for(int i=3; i<=16; i++) {
		if(a[i]>=3) {
			select=i; break;
		}
	}
	if(!select) return;
	
	for(int i=1; i<=3; i++)
		G.push_back(select);
	
	for(int i=3; i<=17; i++) {
		if(a[i]==1) {
			G.push_back(i); break;
		}
		if(a[i]==2 && i!=17) {
			G.push_back(i); G.push_back(i);
			break;
		}
	}
}


void Find_IIISZ(vector<int>& G, int& L, int& R) {
	L=0, R=0;
	int i=3;
	while(i<=12) {
		int j=i;
		while(a[j]>=3) j++;
		if(j-i-1>R-L) L=i, R=j-1;
		if(j>i) i=j;
		else i++;
	}
	if(R-L+1>=3) {
	    G.push_back(L);
	}
}

int Over()
{
	for(int i=3; i<=17; i++) {
		if(a[i]) return 0;
	}
	return 1;
}

int TP() {
	int cnt=0;
	for(int i=3; i<=17; i++) {
		if(a[i]) cnt++;
	}
	return cnt;
}

void dfs(int dep) {

	if(dep>=ans) return;
	
	if(Over()) {
		ans=min(ans, dep);
		return;
	}
	
	int s1=0, s2=0, s3=0, s4=0, s5=0;
	int L, R;
		
	vector<int> G;
	
	Find_IIISZ(G, L, R);
	
	if(G.size()) {
		G.clear();
		s5=1;
		
		int h=L, t=R;
		while(t-L+1>=3) {
			for(int i=L; i<=t; i++) a[i]--, a[i]--, a[i]--;
			dfs(dep+1);
			for(int i=L; i<=t; i++) a[i]++, a[i]++, a[i]++;
			t--;
		}
		h++;
		while(R-h+1>=3) {
			for(int i=h; i<=R; i++) a[i]--, a[i]--, a[i]--;
			dfs(dep+1);
			for(int i=h; i<=R; i++) a[i]++, a[i]++, a[i]++;
			h++;
		}
	}
	
	
	Find_SZ(G, L, R);
	
	if(G.size()) {
		s1=1;
		G.clear();
		int h=L, t=R;
		while(t-L+1>=5) {
			for(int i=L; i<=t; i++) a[i]--;
			dfs(dep+1);
			for(int i=L; i<=t; i++) a[i]++;
			t--;
		}
		
		h++;
		while(R-h+1>=5) {
			for(int i=h; i<=R; i++) a[i]--;
			dfs(dep+1);
			for(int i=h; i<=R; i++) a[i]++;
			h++;
		}
		
	}
	
	Find_IV(G);
	
	if(G.size()) {
		s2=1;
		for(int i=0; i<(int)G.size(); i++) a[G[i]]--;
		dfs(dep+1);
		for(int i=0; i<(int)G.size(); i++) a[G[i]]++;
		G.clear();
	}
	
	Find_II(G, L, R);
	
	if(G.size()) {
		G.clear();
		s3=1;
		int h=L, t=R;
		while(t-L+1>=3) {
			for(int i=L; i<=t; i++) a[i]--, a[i]--;
			dfs(dep+1);
			for(int i=L; i<=t; i++) a[i]++, a[i]++;
			t--;
		}
		h++;
		while(R-h+1>=3) {
			for(int i=h; i<=R; i++) a[i]--, a[i]--;
			dfs(dep+1);
			for(int i=h; i<=R; i++) a[i]++, a[i]++;
			h++;
		}
	}
	
	Find_III(G);
	
	if(G.size()) {
		s4=1;
		for(int i=0; i<(int)G.size(); i++) a[G[i]]--;
		dfs(dep+1);
		for(int i=0; i<(int)G.size(); i++) a[G[i]]++;
		G.clear();
	}
	
	if(!s1 && !s2 && !s3 && !s4 && !s5) {
		ans=min(ans, dep+TP());
		return;
	}
}

void init() {
	scanf("%d%d", &T, &n);
	while(T--) {
		memset(a, 0, sizeof(a));
		for(int i=1; i<=n; i++) {
			int a1, b1;
			scanf("%d%d", &a1, &b1);
			if(a1==1) a[14]++;
			else if(a1==2) a[16]++;
			else if(a1==0) a[17]++;
			else a[a1]++;
		}
		ans=INF;
		dfs(0);
		printf("%d\n", ans);
	}
}

int main()
{
	freopen("landlords.in", "r", stdin);
	freopen("landlords.out", "w", stdout);
	init();
	return 0;
}