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

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

11210 - Chinese Mahjong

Post by hi!man! »

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

Post by little joey »

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

Post by hi!man! »

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

Post by rujialiu »

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

Post by hi!man! »

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

Post by rujialiu »

yes you can
:-)

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio »

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

Post by rujialiu »

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

Post by hi!man! »

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

Post by kn »

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. :D

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

Post by kn »

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?

Post Reply

Return to “Volume 112 (11200-11299)”