美文网首页程序员
拨钟问题新解

拨钟问题新解

作者: PIOVA | 来源:发表于2020-04-18 23:34 被阅读0次

    题目描述
    Time limit: 10000 ms
    Memory limit: 256 MB
    Standard I/O
    表店里有9个时钟,钟表被编号为A到I。时钟只有一个时针,在初始时,每个时钟可能指向整3点、6点、9点或12点。你被给予九种“操作”,每种操作可以将某些时钟的时间前进3小时(顺时针旋转),操作编号0到8,每种操作影响的时钟列表:

    0: A B C
    1: A B D E
    2: A D G
    3: B C E F
    4: B D E F H
    5: C F I
    6: D E G H
    7: E F H I
    8: G H I
    给你一个对9个时钟当前指针位置的描述,请给出一个操作数最少的操作序列,使得按照这个序列操作后,每个时钟的指针都指向12点。

    输入描述
    输入有若干行(不给出具体数目),每行包含以一个空格分开的9个整数,每个整数取值可能为3、6、9、12,依次标识时钟A到I的初始指针位置。不会每个指针都指向12点。
    在本“完整版”,你将被一次测试全部可能的输入:4的9次方减1共262143组,而仍只有10s的时间限制。 这些输入对应的最少操作序列依旧都是唯一的(这是一个有趣的线性代数问题)。

    输出描述
    输出包括若干行,对应每个输入,输出最小操作序列;输入保证对应的最小操作序列是 “唯一” 的:如果将序列中的每个操作按编号升序输出的话。
    在可能的情况下,行末多余的空格也会导致你 wrong answer!

    逆向思维 如果可以从初始状态顺时针旋转到全12点,那么从全12点,用同样的操作序列,让其逆时针转动,就会回到初始状态,并且这个操作序列也是(唯一)最少操作的。
    你需要做的可能是一个与A题相反的对称操作:将加变成减,将负数“同余”(不一定是取模)回到一定的范围。
    然后,你需要做一次“全面”的初始计算:从全12点的状态出发,枚举计算到所有其他262143个时钟状态的最少(逆时针)操作序列。将这些答案存到表或数组里,然后再处理 262143 个询问。

    样例输入
    9 9 12 6 6 6 6 3 6
    3 3 12 9 12 9 12 9 6
    样例输出
    2 4 7 8
    1 1 1 3 4 4 4 5 5 5 6 6 6 7 7 8

    通常情况下我们使用九重循环的方法暴力求解.但是这里我们有如此海量的数据,直接九重循环定然超时.

    为此,我们需要削减循环次数.

    从最后一步考虑.我们此时还剩下几个钟,只需要一次操作即可复原为12点.由于拨钟的顺序不影响结果(比如你先拨AB,再拨AC与先AC后AB是一样的),所以最后剩余的钟我们是可以任意定义的.

    观察我们的所有操作.可以发现,只有操作1同时对ABC进行操作,故我们将最后的三个钟设定为ABC.于是我们得到如下思路:

    通过op1-op8八个操作,使得最后只剩下ABC未复原,且ABC状态相同.因为只有状态相同的情况才可以通过op0一步到位.

    现在我们只需要考虑6个钟了.与ABC相同,我们可以将这六个钟再度划分为DEF与GHI.由于只有op8是对GHI同时操作的.我们需要:
    通过op1-op7七个操作,使得最后只剩下GHI未复原,且状态相同.

    由于op8与op0互不干扰,所以上述条件应当同时成立.总而言之:

    通过op1-op7七个操作,使得DEF全部复位,而ABC与GHI分别处于某个相同状态.

    于是我们的循环变为7重,总共减少了15\cdot4^7次运算.

    代码如下:

    #define _CRT_SECURE_NO_WARNINGS
    
    #include<stdio.h>
    #include<string.h>
    
    int main(void) {
        int Alarm[9] = { 0 };
        while (scanf("%d%d%d%d%d%d%d%d%d", &Alarm[0], &Alarm[1],
            &Alarm[2], &Alarm[3], &Alarm[4], &Alarm[5], &Alarm[6], &Alarm[7], &Alarm[8])==9) {
            int i;
            for (i = 0; i < 9; i++) {
                Alarm[i] = (Alarm[i] / 3) % 4;
            }
            int OpNum[10];
            int Answer[10];
            Answer[9] = 50;
            for (OpNum[1] = 0; OpNum[1] < 4; OpNum[1]++) {
                for (OpNum[2] = 0; OpNum[2] < 4; OpNum[2]++) {
                    for (OpNum[3] = 0; OpNum[3] < 4; OpNum[3]++) {
                        for (OpNum[4] = 0; OpNum[4] < 4; OpNum[4]++) {
                            for (OpNum[5] = 0; OpNum[5] < 4; OpNum[5]++) {
                                for (OpNum[6] = 0; OpNum[6] < 4; OpNum[6]++) {
                                    for (OpNum[7] = 0; OpNum[7] < 4; OpNum[7]++) {
                                        if ((OpNum[1] + OpNum[2] + OpNum[4] + OpNum[6] + Alarm[3]) % 4 == 0 &&
                                            (OpNum[1] + OpNum[3] + OpNum[4] + OpNum[6] + OpNum[7] + Alarm[4]) % 4 == 0 &&
                                            (OpNum[3] + OpNum[4] + OpNum[5] + OpNum[7] + Alarm[5]) % 4 == 0) {
                                            int A0= ( OpNum[1] + OpNum[2] + Alarm[0]) % 4;
                                            int A1 = (OpNum[1] + OpNum[3] + OpNum[4] + Alarm[1]) % 4;
                                            int A2 = ( OpNum[3] + OpNum[5] + Alarm[2]) % 4;
                                            if (A0==A1  && A1==A2) {
                                                int A6 = (OpNum[2] + OpNum[6] + Alarm[6]) % 4;
                                                int A7 = (OpNum[4] + OpNum[6] + OpNum[7] +  Alarm[7]) % 4;
                                                int A8 = (OpNum[5] + OpNum[7]+ Alarm[8]) % 4;
                                                if (A6==A7&&A7==A8 ) {
                                                    OpNum[0] = (4 - A0) % 4;
                                                    OpNum[8] = (4 - A8) % 4;
                                                    OpNum[9] = OpNum[0] + OpNum[1] + OpNum[2] + OpNum[3] + OpNum[4] + OpNum[5] + OpNum[6] + OpNum[7] + OpNum[8];
                                                    if (OpNum[9] < Answer[9]) {
                                                        memcpy(Answer, OpNum, 10 * sizeof(int));
                                                    }
                                                }
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
            for (i = 0; i < 8; i++) {
                for (int j = 0; j < Answer[i]; j++) {
                        printf("%d ", i);
                }
            }
            if (Answer[8] != 0) {
                for (int j = 0; j < Answer[8] - 1; j++) {
                    printf("8 ");
                }
                printf("8\n");
            }
            else {
                putchar('\n');
            }
        }
        return 0;
    }
    

    在codia平台上测试,6853ms通过.比起九重循环快了将近一倍.

    这里快了近一倍还有一个因素,在于if判断语句上面.我们并不需要计算出所有情况再判断,边算边判断会节省大量时间.

    相关文章

      网友评论

        本文标题:拨钟问题新解

        本文链接:https://www.haomeiwen.com/subject/xgozvhtx.html