Google code jam - World Finals 2017-Problem A. Dice Straight

程序员文章站 2022-04-27 13:18:19

...

Google code jam - World Finals 2017-Problem A. Dice Straight

Problem

You have a special set of N six-sided dice, each of which has six different positive integers on its faces. Different dice may have different numberings.

You want to arrange some or all of the dice in a row such that the faces on top form a straight (that is, they show consecutive integers). For each die, you can choose which face is on top.

How long is the longest straight that can be formed in this way?

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case begins with one line with N, the number of dice. Then, N more lines follow; each of them has six positive integers D_ij. The j-th number on the i-th of these lines gives the number on the j-th face of the i-th die.

Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the length of the longest straight that can be formed.

Limits

1 ≤ T ≤ 100.
1 ≤ D_ij ≤ 10⁶ for all i, j.

Small dataset

1 ≤ N ≤ 100.

Large dataset

1 ≤ N ≤ 50000.
The sum of N across all test cases ≤ 200000.

Google code jam - World Finals 2017-Problem A. Dice Straight

我的想法：

以：

1 2 3 4 5 6

1 4 2 6 5 3

为例，将第一组输入作为6个“树根”，对于后面两组中的每一个输入，依次向6个“树根”里插入，（向树根root中插入val的操作定义为：如果val等于树root的最小值减去1，且树root在本轮中尚无新的最小值插入，则将val作为树root的最小值，如果本轮中没有对树的高度进行增加，则树的高度加1；如果val等于树root的最大值加上1，且树root在本轮中尚无新的最大值插入，则将val作为树root的最大，值如果本轮中没有对树的高度进行增加，则树的高度加1），最后扫描6个“树根”，输出最大的高度。

以下是我的代码，根据输入文件得到输出文件提交后提示Incorrect，感兴趣可以一起交流一下算法哪里存在问题。

#include <stdio.h>

struct link
{
    long int maxv;
    long int minv;
    long int len;
};

//为某个link赋初值
void Init(long int key, struct link *node)
{
    node->len=1;
    node->maxv=key;
    node->minv=key;
}

//将key插入到某个link中
void Insert(long int key, struct link *node)//需要解决的问题是,如何传入结构体变量的实参
{
    if(key==node->maxv+1)
    {
        //node->len+=1;
        node->maxv+=1;
    }
    else if(key==node->minv-1)
    {
        //node->len+=1;
        node->minv-=1;
    }
}

//求出所有集合的长度最大值
int maxlen(struct link root[])
{
    long int maxlen=1, i;
    for(i=0; i<6; i++)
    {
        if(maxlen<root[i].len)
            maxlen=root[i].len;
    }
    return maxlen;
}

int main()
{
    long int T, N, i, j, k, maxl, p, times;
    long int x[6];
    int min_index[6], max_index[6];


    if(freopen("A-large-practice.in","r",stdin)==NULL)
    {
        return -1;
    }
    if(freopen("A-large-practice.out","w",stdout )==NULL)
    {
        return -2;
    }

    scanf("%ld", &T);//测试样例的组数

    struct link forest [6];//定义结构体数组

    for(times=1; times<T+1; times++)
    {
        scanf("%ld", &N);//骰子的个数
        scanf("%ld %ld %ld %ld %ld %ld", &x[0], &x[1], &x[2], &x[3], &x[4], &x[5]);

        for(i=0; i<6; i++)
        {
            Init(x[i], &forest[i]);
            min_index[i]=0;
            max_index[i]=0;
        }


        for(j=0; j<N-1; j++)
        {
            scanf("%ld %ld %ld %ld %ld %ld", &x[0], &x[1], &x[2], &x[3], &x[4], &x[5]);

            /*
            对于forest[0],轮流考察x[0],x[1],x[2],x[3],x[4],x[5].
            对于forest[1],轮流考察x[0],x[1],x[2],x[3],x[4],x[5].
            对于forest[2],轮流考察x[0],x[1],x[2],x[3],x[4],x[5].
            对于forest[3],轮流考察x[0],x[1],x[2],x[3],x[4],x[5].
            对于forest[4],轮流考察x[0],x[1],x[2],x[3],x[4],x[5].
            对于forest[5],轮流考察x[0],x[1],x[2],x[3],x[4],x[5].
            */

            for(p=0; p<6; p++)
            {

                for(i=0; i<6; i++)
                {
                    if(min_index[p]!=1)//最小值还可以插入
                    {
                        if(x[i]==(forest[p].minv-1))
                        {
                            Insert(x[i], &forest[p]);
                            min_index[p]=1;
                            if(max_index[i]!=1)//如果最大值那边没有插入，则长度加1；反之，如果已经在最大值那边插入，则不重复累加
                            {
                                forest[p].len+=1;
                            }
                        }
                    }
                    if(max_index[p]!=1)//最大值还可以插入
                    {
                        if(x[i]==(forest[p].maxv+1))
                        {
                            Insert(x[i], &forest[p]);
                            max_index[p]=1;
                            if(min_index[p]!=1)
                            {
                                forest[p].len+=1;
                            }
                        }
                    }
                }

                for(k=0; k<6; k++) //向每一个集合插入后，要清空标志位
                {
                    min_index[k]=0;
                    max_index[k]=0;
                }

            }


        }

        maxl=maxlen(forest);
        printf("Case #%ld: %ld\n", times, maxl);
        maxl=0;
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}