## 11210 - Chinese Mahjong

All about problems in Volume 112. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

hi!man!
New poster
Posts: 48
Joined: Fri Dec 29, 2006 1:26 pm

### 11210 - Chinese Mahjong

I got WA several times but I do not know why
Here are some test cases.
Input:

Code: Select all

``````1S 1S 2S 2S 2S 3S 3S 3S 7S 8S 9S FA FA
1S 2S 3S 4S 5S 6S 7S 8S 9S 1T 3T 5T 7T
1W 2W 3W 3W 4W 4W 5W 5W 6W 7W 8W 8W 8W
2W 2W 3W 3W 4W 4W 4W 5W 6W 6W 7W 8W 8W
1W 2W 3W 3W 4W 4W 4W 5W 6W 6W 7W 8W 8W
0``````
My AC output:

Code: Select all

``````Case 1: 1S 4S FA
Case 2: Not ready
Case 3: 1W 3W 4W 6W 7W 9W
Case 4: 5W 8W
Case 5: 7W``````
Are there more tricky cases?
thanks in advance.
Last edited by hi!man! on Thu Jun 07, 2007 2:55 pm, edited 1 time in total.

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
Your output is correct.

Code: Select all

``````4T 5T 6T 6T 6T 6T 7T 7T 8T 8T 9T BAI BAI
0``````
You should find only 3 waiting tiles.
The biggest problem with most problems is not how to solve the problem, but how to not solve what is not the problem.

hi!man!
New poster
Posts: 48
Joined: Fri Dec 29, 2006 1:26 pm
After I modified my program, my output of your input is 3T 9T and BAI,
I think this is correct.
but still WA

Maybe there are a lot of tricky inputs that I can't notice.

Here are other test cases.
Input:

Code: Select all

``````4T 5T 6T 6T 6T 6T 7T 8T 9T 9T 9T BAI BAI
4T 5T 6T 6T 6T 6T 7T 8T 9T 9T 9T 1W 1W
2T 3T 3T 3T 4T 4T 4T 5T 5T 6T 6T 7T 7T
1T 1T 2T 2T 2T 3T 3T 3T 4T 4T 5T 5T 5T
1T 1T 1T 2T 2T 3T 3T 3T 4T 4T 5T 5T 5T
1T 1T 1T 2T 2T 3T 3T 3T 4T 4T 5T 5T 6T
1T 1T 1T 2T 2T 3T 3T 3T 4T 4T 5T 6T 6T
1T 1T 1T 2T 2T 3T 3T 3T 4T 4T 6T 6T 6T
1T 1T 1T 2T 2T 3T 3T 3T 4T 5T 6T 6T 6T
1T 1T 1T 2T 2T 3T 3T 4T 4T 5T 6T 6T 6T
1T 1T 2T 2T 2T 3T 3T 4T 4T 5T 6T 6T 6T
1T 1T 2T 2T 3T 3T 3T 4T 4T 5T 6T 6T 6T
1T 1T 2T 2T 3T 3T 4T 4T 4T 5T 6T 6T 6T
1T 1T 2T 2T 3T 4T 4T 4T 4T 5T 6T 6T 6T
1T 2T 2T 2T 2T 3T 4T 4T 4T 5T 6T 6T 6T
2T 2T 2T 2T 3T 3T 4T 4T 4T 5T 6T 6T 6T
2T 2T 2T 2T 3T 3T 4T 4T 4T 5T 5T 6T 6T
1T 2T 2T 2T 3T 3T 4T 4T 4T 5T 6T 6T 6T
1T 1T 2T 2T 2T 3T 4T 4T 4T 5T 6T 6T 6T
1T 2T 2T 2T 3T 4T 4T 4T 5T 6T 6T 6T 7T
0``````
My AC output:

Code: Select all

``````Case 1: 3T 9T BAI
Case 2: 3T 9T 1W
Case 3: 1T 2T 3T 4T 6T 7T
Case 4: 1T 3T 4T 6T
Case 5: 1T 2T 3T 4T 5T
Case 6: 1T 2T 3T 4T 6T 7T
Case 7: 1T 4T 5T 6T
Case 8: 2T 3T 4T 5T
Case 9: 1T 2T 3T 4T 6T
Case 10: 1T 2T 3T 4T 5T 6T 7T
Case 11: 1T 2T 3T 5T
Case 12: 1T 2T 4T 5T
Case 13: 1T 3T 4T 5T 6T 7T
Case 14: 1T 2T 3T
Case 15: 3T 4T 5T 6T 7T
Case 16: 1T 3T 4T 5T 6T
Case 17: 1T 3T 4T 6T 7T
Case 18: 2T 3T 4T
Case 19: 1T 4T
Case 20: 2T 6T``````
Last edited by hi!man! on Thu Jun 07, 2007 2:54 pm, edited 1 time in total.

rujialiu
New poster
Posts: 37
Joined: Mon Mar 05, 2007 2:42 am
well i cannot think about any tricky test case besides the reason why little joy's test case has only 3 waiting tiles.

maybe you're ordering waiting tiles in a wrong way, or you mispelled something (if you don't know Chinese Characters it's easy to make mistakes). So I suggest you review your code first.

anyway, try these two test cases

Code: Select all

``````ZHONG ZHONG FA FA BAI BAI BAI DONG DONG DONG NAN NAN NAN
BEI 6T 6T 7T 7T 7T 7T 8T 8T 8T 8T 9T 9T``````
the output should be

Code: Select all

``````Case 1: ZHONG FA
Case 2: BEI``````

hi!man!
New poster
Posts: 48
Joined: Fri Dec 29, 2006 1:26 pm
Thank you for your reply.
I already checked my code for misspelling, but nothing wrong.

Do I need post my code here?

rujialiu
New poster
Posts: 37
Joined: Mon Mar 05, 2007 2:42 am
yes you can

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
Your second testcases outputs inlcluding wrong answers.
For example, for seventh case:

Code: Select all

``````1T 1T 1T 2T 2T 3T 3T 3T 4T 4T 5T 6T 6T
``````
You could also wait with 1T and 6T.

Code: Select all

``````(1,2,3) (2,3,4) (3,4,5) (1,1) (6,6)
``````
----
Rio

rujialiu
New poster
Posts: 37
Joined: Mon Mar 05, 2007 2:42 am
Oh, i just did not check his second test sets since I don't have my program now

hi!man!
New poster
Posts: 48
Joined: Fri Dec 29, 2006 1:26 pm
ok, I know where is my bug.
now I have to think how to determine the answers.

[EDIT] Finally I got a AC

kn
New poster
Posts: 28
Joined: Fri Apr 13, 2007 8:53 am

### Re: 11210 - Chinese Mahjong

Hi guys, I have been trying different test cases for many times... My code passed all available test cases, and I have been checking the code again and again... but I still don't have any idea on how my program could be wrong. Would anyone please take a look on my code?

The comment should be clear enough.

Code: Select all

``````#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
#define x first
#define y second
typedef pair<int,int> P;
void bug(int x){
for(int i=0;i<13;i++)
putchar((x&(1<<i))?'1':'0');
puts(""); }
map<int,int> mp;
P p[13];
int f2(char *p){ return (*p-'A') * 26 + p[1]-'A'; }
const int M = 1<<13;
char tile[] = "TSW";
char fan[7][6] = {"DONG", "NAN", "XI", "BEI", "ZHONG", "FA", "BAI"};
int toPai(P p){
putchar(' ');
if(p.x <= 2){ printf("%d%c", p.y, tile[p.x]); }
else            { printf("%s", fan[p.y]); }
}
int main(){
// "style" mapping
{
for(int r=0; r<3; r++)
mp[tile[r]] = r;
for(int r=0; r<7; r++)
mp[f2(fan[r])] = r;
}

int Zz = 0;
char s[14][7];
while(scanf("%s",s[0]), s[0][0]!='0'){
for(int r=1; r<13; r++)
scanf("%s", s[r]);

for(int r=0; r<13; r++)
{
if(isdigit(s[r][0])){
p[r].x = mp[s[r][1]];
p[r].y = s[r][0] - '0';
}else{
p[r].x = 3;
p[r].y = mp[f2(s[r])];
}
}

sort(p, p+13);

vector<int> a3, a6, a9, a2;
// a2, a3 (pong)
for(int a=0; a<13; a++)
for(int b=a+1; b<13; b++){
if(p[b]!=p[a])  continue;
int t = (1<<a) | (1<<b);
a2.push_back(t);
for(int c=b+1; c<13; c++){
if(p[c]!=p[b])  continue;
a3.push_back(t | (1<<c));
}
}

// a3 (chow)
for(int a=0; a<13 && p[a].x<3; a++)
for(int b=a+1; b<13; b++){
if(p[b].x != p[a].x)    continue;
if(p[b].y != p[a].y+1)  continue;
for(int c=b+1; c<13; c++){
if(p[c].x != p[b].x)    continue;
if(p[c].y != p[b].y+1)  continue;
int t = (1<<a) | (1<<b) | (1<<c);
a3.push_back(t);
}
}

// a6
for(int a=0; a<a3.size(); a++)
for(int b=a+1; b<a3.size(); b++){
int t = a3[a] | a3[b];
if( t== a3[a] + a3[b] )
a6.push_back(t);
}

// a9
for(int a=0; a<a6.size(); a++)
for(int b=0; b<a3.size(); b++){
int t = a6[a] | a3[b];
if( t== a6[a] + a3[b] )
a9.push_back(t);
}

vector<P> ans;
// a11
for(int a=0; a<a2.size(); a++)
for(int b=0; b<a9.size(); b++){
int t = a2[a] | a9[b];
if( t== a2[a] + a9[b] ){
int res = ~t;

int x=0;
while(((1<<x)&res)==0)  x++;
int y=x+1;
while(((1<<y)&res)==0)  y++;

if(p[x].x != p[y].x)    continue;
else{
if(p[x].y==p[y].y)
ans.push_back(p[x]);
else if(p[x].x < 3){
if(p[x].y==p[y].y-2)    // "Ka Loong"
ans.push_back(P(p[x].x, p[x].y+1));
else if(p[y].y==p[x].y+1){      // "Double Fly"
int a[2] = {p[x].y-1, p[x].y+2};
for(int k=0; k<2; k++)
if(a[k]>=1 && a[k]<=9)
ans.push_back(P(p[x].x, a[k]));
}
}
}
}
}

// a12
for(int a=0; a<a3.size(); a++)
for(int b=0; b<a9.size(); b++)
{
int t = a3[a] | a9[b];
if( t== a3[a] + a9[b] ){
int res = ~t;
int x = 0;
while(!(res&(1<<x))) x++;
ans.push_back(p[x]);
}
}

//              printf("a2=%d a3=%d a6=%d a9=%d\n",
//                      a2.size(), a3.size(), a6.size(), a9.size());

printf("Case %d:", ++Zz);
if(ans.size()){
sort(ans.begin(), ans.end());
vector<P>::iterator ed = unique(ans.begin(), ans.end());
for(vector<P>::iterator it = ans.begin(); it != ed; ++it){
// Chk whether there are 4 already
int cnt = 0;
for(int i=0; i<13; i++) cnt += *it==p[i];
if(cnt < 4)
toPai(*it);
}
puts("");
}else{
puts(" Not ready");
}
}
return 0;
}
``````

kn
New poster
Posts: 28
Joined: Fri Apr 13, 2007 8:53 am

### Re: 11210 - Chinese Mahjong

Let me explain a little bit of my algorithm:

First of all, I use 13-bit-pattern to represent a combination.

e.g. 1110011100000 means 1+2+3+6+7+8 piece.

Algorithm:
1) I search for "Chow" and "Pong" (3 pieces), store them in vector<int> a3.
2) Then I search for pair (2 pieces), store them in vector<int> a2
2) Then, I group every 2 compatible combinations in a3, to form an element in vector<int> a6.
e.g. 1110000000000 + 0001110000000 -> 1111110000000
3) Then, I use similar method to search a6, a9, a12, a11
a6 + a3 --> a9
a6 + a6 --> a12
a2 + a9 --> a11
4) Last of all, for each element in a12 and a11 respecitively, I know what Mahjong should I need.
5) I sort all "needed" Mahjong and print them out.

Is my algorithm correct?