Japanese Mahjong is a four-player game. The game needs four people to sit around a desk and play with a set of Mahjong tiles. A set of Mahjong tiles contains four copies of the tiles described next:
One to nine Man, which we use 1m to 9m to represent;
One to nine Sou, which we use 1s to 9s to represent;
One to nine Pin, which we use 1p to 9p to represent;
Character tiles, which are:Ton, Nan, Sei, Pei, Haku, Hatsu, Chun, which we use 1c to 7c to represent.
A winning state means a set of 14 tiles that normally contains a pair of same tiles (which we call "eyes") and four melds. A meld is formed by either three same tiles(1m, 1m, 1m or 2c, 2c, 2c for example) or three continuous non-character tiles(1m, 2m, 3m or 5s, 6s, 7s for example).
However, there are two special winning states that are different with the description above, which are:
"Chii Toitsu", which means 7 different pairs of tiles;
"Kokushi Muso", which means a set of tiles that contains all these tiles: 1m, 9m, 1p, 9p, 1s, 9s and all 7 character tiles. And the rest tile should also be one of the 13 tiles above.
And the game starts with four players receiving 13 tiles. In each round every player must draw one tile from the deck one by one. If he reaches a winning state with these 14 tiles, he can say "Tsu Mo" and win the game. Otherwise he should discard one of his 14 tiles. And if the tile he throws out can form a winning state with the 13 tiles of any other player, the player can say "Ron" and win the game.
Now the question is, given the 13 tiles you have, does there exist any tiles that can form a winning state with your tiles?
(Notes: Some of the pictures and descriptions above come from Wikipedia.)
InputThe input data begins with a integer T(1≤T≤20000). Next are T cases, each of which contains 13 tiles. The description of every tile is as above. OutputFor each cases, if there actually exists some tiles that can form a winning state with the 13 tiles given, print the number first and then print all those tiles in order as the description order of tiles above. Otherwise print a line "Nooten"(without quotation marks). Sample Input
One to nine Man, which we use 1m to 9m to represent;
One to nine Sou, which we use 1s to 9s to represent;
One to nine Pin, which we use 1p to 9p to represent;
Character tiles, which are:Ton, Nan, Sei, Pei, Haku, Hatsu, Chun, which we use 1c to 7c to represent.
A winning state means a set of 14 tiles that normally contains a pair of same tiles (which we call "eyes") and four melds. A meld is formed by either three same tiles(1m, 1m, 1m or 2c, 2c, 2c for example) or three continuous non-character tiles(1m, 2m, 3m or 5s, 6s, 7s for example).
However, there are two special winning states that are different with the description above, which are:
"Chii Toitsu", which means 7 different pairs of tiles;
"Kokushi Muso", which means a set of tiles that contains all these tiles: 1m, 9m, 1p, 9p, 1s, 9s and all 7 character tiles. And the rest tile should also be one of the 13 tiles above.
And the game starts with four players receiving 13 tiles. In each round every player must draw one tile from the deck one by one. If he reaches a winning state with these 14 tiles, he can say "Tsu Mo" and win the game. Otherwise he should discard one of his 14 tiles. And if the tile he throws out can form a winning state with the 13 tiles of any other player, the player can say "Ron" and win the game.
Now the question is, given the 13 tiles you have, does there exist any tiles that can form a winning state with your tiles?
(Notes: Some of the pictures and descriptions above come from Wikipedia.)
2 1s 2s 3s 2c 2c 2c 2p 3p 5m 6m 7m 1p 1p 1p 1p 2p 3p 4s 5s 6s 7c 7c 3s 3s 2m 2mSample Output
2 1p 4p Nooten
解题思路：
模拟麻将，三种情况赢，分别判断。
暴力每一种麻将，然后对14个麻将判断，注意：麻将个数不能超过4个
判断的时候，先遍历取两个一对的情况，然后对其他的是否能组成4副进行判断。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iomanip>
#include <algorithm>
#include <climits>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <list>
#define rep(i,m,n) for(int i=m;i<=n;i++)
#define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++)
const int inf_int = 2e9;
const long long inf_ll = 2e18;
#define inf_add 0x3f3f3f3f
#define mod 1000000007
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pi acos(-1.0)
#define pii pair<int,int>
#define Lson L, mid, rt<<1
#define Rson mid+1, R, rt<<1|1
const int maxn=5e2+10;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
inline int read(){int ra,fh;char rx;rx=getchar(),ra=0,fh=1;
while((rx<'0'||rx>'9')&&rx!='-')rx=getchar();if(rx=='-')
fh=-1,rx=getchar();while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,
rx=getchar();return ra*fh;}
//#pragma comment(linker, "/STACK:102400000,102400000")
ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}
ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p;p=p*p;q>>=1;}return f;}
typedef vector<int> vi;
int dir[4][2]={{1,0},{0,-1},{-1,0},{0,1}};
const int N = 1e5+5;
int m[20];
int s[20];
int p[20];
int c[20];
int mm[20];
int ss[20];
int pp[20];
int cc[20];
void initer()
{
memset(m,0,sizeof(m));
memset(s,0,sizeof(s));
memset(p,0,sizeof(p));
memset(c,0,sizeof(c));
memset(mm,0,sizeof(mm));
memset(ss,0,sizeof(ss));
memset(pp,0,sizeof(pp));
memset(cc,0,sizeof(cc));
}
void copyy()
{
for(int i=1;i<=9;i++)
{
mm[i] = m[i];
}
for(int i=1;i<=9;i++)
{
ss[i] = s[i];
}
for(int i=1;i<=9;i++)
{
pp[i] = p[i];
}
for(int i=1;i<=7;i++)
{
cc[i] = c[i];
}
}
/*void print_m()
{
for(int i=1;i<=9;i++)
{
cout << m[i]<<" ";
}
cout << endl;
for(int i=1;i<=9;i++)
{
cout << s[i]<<" ";
}
cout << endl;
for(int i=1;i<=9;i++)
{
cout << p[i]<<" ";
}
cout << endl;
for(int i=1;i<=9;i++)
{
cout << c[i]<<" ";
}
cout << endl;
}
void print_mm()
{
for(int i=1;i<=9;i++)
{
cout << mm[i]<<" ";
}
cout << endl;
for(int i=1;i<=9;i++)
{
cout << ss[i]<<" ";
}
cout << endl;
for(int i=1;i<=9;i++)
{
cout << pp[i]<<" ";
}
cout << endl;
for(int i=1;i<=9;i++)
{
cout << cc[i]<<" ";
}
cout << endl;
cout << "&&&&&&&&&&&&&&&"<<endl;
}
*/
bool judge();
bool _judge();
bool judge_2();
bool judge_3();
int T;
int main()
{
int re= 0;
int t = 13;
string st;
string sst;
cin >>T;
while(T--)
{
t = 13;
initer();
re = 0;
vector<string> ans;
ans.clear();
while(t--)
{
cin >> st;
if(st[1]=='s')
{
s[st[0]-'0']++;
}
if(st[1]=='m')
{
m[st[0]-'0']++;
}
if(st[1]=='c')
{
c[st[0]-'0']++;
}
if(st[1]=='p')
{
p[st[0]-'0']++;
}
}
for(int i=1;i<=9;i++)
{
m[i]++;
if(judge()&&m[i]<=4)
{
sst = (i+'0');
sst+="m";
ans.push_back(sst);
}
m[i]--;
}
for(int i=1;i<=9;i++)
{
s[i]++;
if(judge()&&s[i]<=4)
{
sst = (i+'0');
sst+="s";
ans.push_back(sst);
}
s[i]--;
}
for(int i=1;i<=9;i++)
{
p[i]++;
//cout<<i<<endl;
//cout <<"@@@@@"<<endl;
if(judge()&&p[i]<=4)
{
sst = (i+'0');
sst+="p";
ans.push_back(sst);
}
p[i]--;
}
for(int i=1;i<=7;i++)
{
c[i]++;
if(judge()&&c[i]<=4)
{
sst = (i+'0');
sst+="c";
ans.push_back(sst);
}
c[i]--;
}
re = ans.size();
if(re>0)
{
cout << re;
for(auto &r : ans)
{
cout <<" "<< r;
}
cout << endl;
}
else
{
cout <<"Nooten"<<endl;
}
}
return 0;
}
bool judge()
{
int ff =0;
for(int i=1;i<=9;i++)
{
copyy();
// print_mm();
if(mm[i]>=2)
{
mm[i]-=2;
if(_judge())
{
return true;
}
}
copyy();
if(pp[i]>=2)
{
pp[i]-=2;
if(_judge())
{
return true;
}
}
copyy();
if(ss[i]>=2)
{
ss[i]-=2;
if(_judge())
{
return true;
}
}
}
for(int i=1;i<=7;i++)
{
copyy();
if(cc[i]>=2)
{
cc[i]-=2;
if(_judge())
{
return true;
}
}
}
//2 Chii Toitsu
copyy();
if(judge_2())
{
return true;
}
//3 Kokushi Muso
copyy();
if(judge_3())
{
return true;
}
return false;
}
bool judge_2()
{
int cct=0;
for(int i=1;i<=9;i++)
{
if(pp[i]==2)
cct++;
if(ss[i]==2)
cct++;
if(cc[i]==2)
cct++;
if(mm[i]==2)
cct++;
}
if(cct==7)
return true;
else
return false;
}
bool judge_3()
{
int cct=0,sum =0 ;
for(int i=1;i<=7;i++)
{
if(cc[i])
{
sum += cc[i];
cct++;
}
}
if(pp[1])
cct++;
if(ss[1])
cct++;
if(mm[1])
cct++;
if(pp[9])
cct++;
if(ss[9])
cct++;
if(mm[9])
cct++;
sum+=pp[1];
sum+=ss[1];
sum+=mm[1];
sum+=pp[9];
sum+=ss[9];
sum+=mm[9];
if(cct==13&&sum==14)
return true;
else
return false;
}
bool _judge()
{
int ct = 0;
// print_mm();
for(int k=1;k<=7;k++)
{
if(mm[k]<3&&mm[k]>0)
{
mm[k+1]-=mm[k];
mm[k+2]-=mm[k];
if(mm[k+1]<0) return false;
if(mm[k+2]<0) return false;
ct+=mm[k];
mm[k]=0;
}
else if(mm[k]>=3)
{
mm[k]-=3;
ct++;
ct+=mm[k];
mm[k+1]-=mm[k];
mm[k+2]-=mm[k];
mm[k]=0;
if(mm[k+1]<0) return false;
if(mm[k+2]<0) return false;
}
}
if(mm[8]==3)
{
mm[8]-=3;
ct++;
}
if(mm[9]==3)
{
mm[9]-=3;
ct++;
}
//print_mm();
for(int k=1;k<=7;k++)
{
if(ss[k]<3&&ss[k]>0)
{
ss[k+1]-=ss[k];
ss[k+2]-=ss[k];
if(ss[k+1]<0) return false;
if(ss[k+2]<0) return false;
ct+=ss[k];
ss[k]=0;
}
else if(ss[k]>=3)
{
ss[k]-=3;
ct++;
ct+=ss[k];
ss[k+1]-=ss[k];
ss[k+2]-=ss[k];
ss[k]=0;
if(ss[k+1]<0) return false;
if(ss[k+2]<0) return false;
}
}
if(ss[8]==3)
{
ss[8]-=3;
ct++;
}
if(ss[9]==3)
{
ss[9]-=3;
ct++;
}
for(int k=1;k<=7;k++)
{
if(pp[k]<3&&pp[k]>0)
{
pp[k+1]-=pp[k];
pp[k+2]-=pp[k];
if(pp[k+1]<0) return false;
if(pp[k+2]<0) return false;
ct+=pp[k];
pp[k]=0;
}
else if(pp[k]>=3)
{
pp[k]-=3;
ct++;
ct+=pp[k];
pp[k+1]-=pp[k];
pp[k+2]-=pp[k];
pp[k]=0;
if(pp[k+1]<0) return false;
if(pp[k+2]<0) return false;
}
}
if(pp[8]==3)
{
pp[8]-=3;
ct++;
}
if(pp[9]==3)
{
pp[9]-=3;
ct++;
}
for(int k=1;k<=7;k++)
{
if(cc[k]==3)
{
cc[k]-=3;
ct++;
}
}
int fff = 1;
for(int i=1;i<=9;i++)
{
if(pp[i]!=0) fff = 0;
if(ss[i]!=0) fff = 0;
if(mm[i]!=0) fff = 0;
}
for(int i=1;i<=7;i++)
{
if(cc[i]!=0) fff = 0;
}
if(fff&&ct==4)
{
return true;
}
else
{
return false;
}
}