#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int t,n,a[20],ans;
int putout(){
int i,j,b[20];
int num=0,flag=0;
memcpy(b,a,sizeof(a));
for(i=3;i<=17;i++){
if(b[i]>=3){
flag=0;
for(j=3;j<=17;j++){
if((b[j]==2)&&i!=j){
b[j]-=2;
b[i]-=3;
num++;
flag=1;
}
else if(b[j]==1&&i!=j){
b[j]-=1;
b[i]-=3;
num++;
flag=1;
}
if(flag==1) break;
}
if(flag==0){
b[i]-=3;
num++;
}
}
}
for(i=3;i<=15;i++){
if(b[i]){
b[i]=0;
num++;
}
}
if(b[16]||b[17]) num++;
return num;
}
void dfs(int step){
int i,j,k,l,flag,book=1;
if(step>ans) return;
int tmp=putout();
if(ans>(step+tmp)){
ans=step+tmp;
}
for(i=3;i<=17;i++){
if(a[i]!=0) book=0;
}
if(book) return;
for(i=3;i<=17;i++){
flag=0;
if(a[i]==4){
if(i!=16&&i!=17){
if(a[16]>=1&&a[16]<=2&&a[17]>=1&&a[17]<=2){
flag=1;
a[i]-=4;a[16]-=1;a[17]-=1;
dfs(step+1);
a[i]+=4;a[16]+=1;a[17]+=1;
}
}
if(flag) continue;
for(j=3;j<=17;j++){
if(i!=j&&a[j]){
for(k=j+1;k<=17;k++){
if(k==i||(!a[k]))continue;
for(l=1;l<=2;l++){
if(a[j]>=l&&a[k]>=l){
a[i]-=4; a[j]-=l;a[k]-=l;
dfs(step+1);
a[i]+=4; a[j]+=l;a[k]+=l;
}
}
}
}
}
a[i]-=4;
dfs(step+1);
a[i]+=4;
}
}//四张牌时
int sta=15,end=0;
for(i=3;i<=14;i++){
if(a[i]>=3&&a[i+1]>=3&&a[i+2]>=3){
sta=min(sta,i);end=max(end,i+2);
}
}
for(i=sta;i<=end-2;i++){
for(j=sta+2;j<=end;j++){
if((j-i+1)>=3){
for(k=i;k<=j;k++){
a[k]-=3;
}
dfs(step+1);
for(k=i;k<=j;k++){
a[k]+=3;
}
}
}
}//三顺子
sta=15;end=0;
for(i=3;i<=14;i++){
if(a[i]>=2&&a[i+1]>=2&&a[i+2]>=2){
sta=min(sta,i);end=max(end,i+2);
}
}
for(i=sta;i<=end-2;i++){
for(j=sta+2;j<=end;j++){
if((j-i+1)>=3){
for(k=i;k<=j;k++){
a[k]-=2;
}
dfs(step+1);
for(k=i;k<=j;k++){
a[k]+=2;
}
}
}
}
sta=15;end=0;
for(i=3;i<=14;i++){
if(a[i]>=1&&a[i+1]>=1&&a[i+2]>=1&&a[i+3]>=1&&a[i+4]>=1){
sta=min(sta,i);end=max(end,i+4);
}
}
for(i=sta;i<=end-4;i++){
for(j=sta+4;j<=end;j++){
if((j-i+1)>=5){
for(k=i;k<=j;k++){
a[k]-=1;
}
dfs(step+1);
for(k=i;k<=j;k++){
a[k]+=1;
}
}
}
}///单顺子
}
int main(){
freopen("ddz.txt","r",stdin);
int k,i,car,col;
cin>>t>>n;
for(k=1;k<=t;k++){
ans=n;
memset(a,0,sizeof(a));
for(i=1;i<=n;i++){
cin>>car>>col;
if(car==1) a[14]++;
else if(car==2) a[15]++;
else if(car==0&&col==1) a[16]++;
else if(car==0&&col==2) a[17]++;
else a[car]++;
}
dfs(0);
cout<<ans<<endl;
}
return 0;
}
1 条评论
-
wuwangmao LV 8 @ 2016-09-21 21:52:32
**
测试数据 #0: Accepted, time = 0 ms, mem = 560 KiB, score = 1测试数据 #1: Accepted, time = 0 ms, mem = 560 KiB, score = 1
测试数据 #2: Accepted, time = 15 ms, mem = 560 KiB, score = 1
测试数据 #3: Accepted, time = 0 ms, mem = 560 KiB, score = 1
测试数据 #4: Accepted, time = 0 ms, mem = 560 KiB, score = 1
测试数据 #5: Accepted, time = 15 ms, mem = 560 KiB, score = 1
测试数据 #6: Accepted, time = 0 ms, mem = 560 KiB, score = 1
测试数据 #7: Accepted, time = 15 ms, mem = 560 KiB, score = 1
测试数据 #8: Accepted, time = 0 ms, mem = 564 KiB, score = 1
测试数据 #9: Accepted, time = 15 ms, mem = 560 KiB, score = 1
测试数据 #10: Accepted, time = 0 ms, mem = 560 KiB, score = 1
测试数据 #11: Accepted, time = 0 ms, mem = 560 KiB, score = 1
测试数据 #12: Accepted, time = 0 ms, mem = 560 KiB, score = 1
测试数据 #13: Accepted, time = 0 ms, mem = 560 KiB, score = 1
测试数据 #14: Accepted, time = 0 ms, mem = 560 KiB, score = 1
测试数据 #15: Accepted, time = 0 ms, mem = 560 KiB, score = 1
测试数据 #16: Accepted, time = 0 ms, mem = 560 KiB, score = 1
测试数据 #17: Accepted, time = 0 ms, mem = 560 KiB, score = 1
测试数据 #18: Accepted, time = 0 ms, mem = 560 KiB, score = 1
测试数据 #19: Accepted, time = 15 ms, mem = 564 KiB, score = 1
测试数据 #20: Accepted, time = 0 ms, mem = 556 KiB, score = 1
测试数据 #21: Accepted, time = 0 ms, mem = 560 KiB, score = 1
测试数据 #22: Accepted, time = 0 ms, mem = 560 KiB, score = 1
测试数据 #23: Accepted, time = 0 ms, mem = 560 KiB, score = 1
测试数据 #24: Accepted, time = 0 ms, mem = 560 KiB, score = 1
测试数据 #25: Accepted, time = 0 ms, mem = 560 KiB, score = 1
测试数据 #26: Accepted, time = 15 ms, mem = 560 KiB, score = 1
测试数据 #27: Accepted, time = 0 ms, mem = 560 KiB, score = 1
测试数据 #28: Accepted, time = 0 ms, mem = 556 KiB, score = 1
测试数据 #29: Accepted, time = 0 ms, mem = 560 KiB, score = 1
测试数据 #30: WrongAnswer, time = 0 ms, mem = 560 KiB, score = 0
测试数据 #31: WrongAnswer, time = 0 ms, mem = 560 KiB, score = 0
测试数据 #32: WrongAnswer, time = 0 ms, mem = 560 KiB, score = 0
测试数据 #33: WrongAnswer, time = 0 ms, mem = 560 KiB, score = 0
测试数据 #34: WrongAnswer, time = 15 ms, mem = 560 KiB, score = 0
测试数据 #35: WrongAnswer, time = 0 ms, mem = 560 KiB, score = 0
测试数据 #36: WrongAnswer, time = 15 ms, mem = 560 KiB, score = 0
测试数据 #37: WrongAnswer, time = 0 ms, mem = 560 KiB, score = 0
测试数据 #38: WrongAnswer, time = 0 ms, mem = 560 KiB, score = 0
测试数据 #39: WrongAnswer, time = 15 ms, mem = 560 KiB, score = 0
测试数据 #40: WrongAnswer, time = 0 ms, mem = 560 KiB, score = 0
测试数据 #41: WrongAnswer, time = 0 ms, mem = 560 KiB, score = 0
测试数据 #42: WrongAnswer, time = 0 ms, mem = 560 KiB, score = 0
测试数据 #43: WrongAnswer, time = 0 ms, mem = 560 KiB, score = 0
测试数据 #44: WrongAnswer, time = 0 ms, mem = 560 KiB, score = 0
测试数据 #45: WrongAnswer, time = 0 ms, mem = 560 KiB, score = 0
测试数据 #46: WrongAnswer, time = 0 ms, mem = 560 KiB, score = 0
测试数据 #47: WrongAnswer, time = 0 ms, mem = 560 KiB, score = 0
测试数据 #48: WrongAnswer, time = 0 ms, mem = 560 KiB, score = 0
测试数据 #49: WrongAnswer, time = 15 ms, mem = 564 KiB, score = 0
测试数据 #50: WrongAnswer, time = 0 ms, mem = 560 KiB, score = 0
测试数据 #51: WrongAnswer, time = 0 ms, mem = 560 KiB, score = 0
测试数据 #52: WrongAnswer, time = 0 ms, mem = 560 KiB, score = 0
测试数据 #53: WrongAnswer, time = 0 ms, mem = 560 KiB, score = 0
测试数据 #54: WrongAnswer, time = 0 ms, mem = 560 KiB, score = 0
测试数据 #55: WrongAnswer, time = 15 ms, mem = 560 KiB, score = 0
测试数据 #56: WrongAnswer, time = 0 ms, mem = 560 KiB, score = 0
测试数据 #57: WrongAnswer, time = 0 ms, mem = 560 KiB, score = 0
测试数据 #58: WrongAnswer, time = 15 ms, mem = 560 KiB, score = 0
测试数据 #59: WrongAnswer, time = 0 ms, mem = 560 KiB, score = 0
测试数据 #60: WrongAnswer, time = 15 ms, mem = 560 KiB, score = 0
测试数据 #61: WrongAnswer, time = 0 ms, mem = 560 KiB, score = 0
测试数据 #62: WrongAnswer, time = 0 ms, mem = 560 KiB, score = 0
测试数据 #63: WrongAnswer, time = 0 ms, mem = 560 KiB, score = 0
测试数据 #64: WrongAnswer, time = 0 ms, mem = 556 KiB, score = 0
测试数据 #65: WrongAnswer, time = 0 ms, mem = 560 KiB, score = 0
测试数据 #66: WrongAnswer, time = 0 ms, mem = 560 KiB, score = 0
测试数据 #67: WrongAnswer, time = 15 ms, mem = 560 KiB, score = 0
测试数据 #68: WrongAnswer, time = 0 ms, mem = 560 KiB, score = 0
测试数据 #69: WrongAnswer, time = 0 ms, mem = 560 KiB, score = 0
测试数据 #70: WrongAnswer, time = 0 ms, mem = 560 KiB, score = 0
测试数据 #71: WrongAnswer, time = 0 ms, mem = 564 KiB, score = 0
测试数据 #72: WrongAnswer, time = 0 ms, mem = 560 KiB, score = 0
测试数据 #73: WrongAnswer, time = 0 ms, mem = 564 KiB, score = 0
测试数据 #74: WrongAnswer, time = 0 ms, mem = 556 KiB, score = 0
测试数据 #75: WrongAnswer, time = 0 ms, mem = 560 KiB, score = 0
测试数据 #76: WrongAnswer, time = 0 ms, mem = 560 KiB, score = 0
测试数据 #77: WrongAnswer, time = 0 ms, mem = 560 KiB, score = 0
测试数据 #78: WrongAnswer, time = 0 ms, mem = 560 KiB, score = 0
测试数据 #79: WrongAnswer, time = 15 ms, mem = 560 KiB, score = 0
测试数据 #80: WrongAnswer, time = 15 ms, mem = 560 KiB, score = 0
测试数据 #81: WrongAnswer, time = 0 ms, mem = 560 KiB, score = 0
测试数据 #82: WrongAnswer, time = 15 ms, mem = 564 KiB, score = 0
测试数据 #83: WrongAnswer, time = 0 ms, mem = 560 KiB, score = 0
测试数据 #84: WrongAnswer, time = 0 ms, mem = 560 KiB, score = 0
测试数据 #85: WrongAnswer, time = 15 ms, mem = 560 KiB, score = 0
测试数据 #86: WrongAnswer, time = 0 ms, mem = 560 KiB, score = 0
测试数据 #87: WrongAnswer, time = 0 ms, mem = 564 KiB, score = 0
测试数据 #88: WrongAnswer, time = 0 ms, mem = 556 KiB, score = 0
测试数据 #89: WrongAnswer, time = 0 ms, mem = 560 KiB, score = 0
测试数据 #90: TimeLimitExceeded, time = 1031 ms, mem = 560 KiB, score = 0
测试数据 #91: WrongAnswer, time = 0 ms, mem = 564 KiB, score = 0
测试数据 #92: WrongAnswer, time = 171 ms, mem = 560 KiB, score = 0
测试数据 #93: TimeLimitExceeded, time = 1203 ms, mem = 560 KiB, score = 0
测试数据 #94: WrongAnswer, time = 46 ms, mem = 564 KiB, score = 0
测试数据 #95: WrongAnswer, time = 421 ms, mem = 560 KiB, score = 0
测试数据 #96: WrongAnswer, time = 203 ms, mem = 560 KiB, score = 0
测试数据 #97: TimeLimitExceeded, time = 1203 ms, mem = 560 KiB, score = 0
测试数据 #98: WrongAnswer, time = 109 ms, mem = 560 KiB, score = 0
测试数据 #99: TimeLimitExceeded, time = 1015 ms, mem = 556 KiB, score = 0
TimeLimitExceeded, time = 5672 ms, mem = 564 KiB, score = 30**
- 1
