V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
CEBBCAT
V2EX  ›  程序员

有参加 第五届“图灵杯”NEUQ-ACM 程序设计大赛(个人赛)网络同步赛 的吗? ACMClub.cn 的程序是不是有问题啊?

  •  
  •   CEBBCAT ·
    Zhang-Siyang · 2017-12-03 17:39:40 +08:00 · 3259 次点击
    这是一个创建于 2544 天前的主题,其中的信息可能已经有所发展或是发生改变。

    举例来讲,第一题是:

    1855: 逃出生天
    
    题目描述:
    gold 学长从昏迷中醒来以后发现自己被困在一个山洞里,他找了很久,终于找到一个门。门上写着:想要逃出去,只有一个办法 你可以选择一个数 n,设 m=1 * 2 * ... * (n-1)。如果 m 是 n 的倍数,那么门就会自动打开,否则你就别想出去了。gold 学长内心充满了绝望,他想了一些数,但他不知道这些数能不能保证自己逃出去。你能帮助 gold 学长逃出生天吗?
    输入:
    第一行一个数 T ( T<=1000 ),表示 gold 学长想的数的个数 接下来每一行一个数 n ( 2<=n<=1e8 ),表示 gold 学长想的数
    输出:
    每行一个输出 对于每一个数,如果学长能逃出去,则输出“ escape ”(不含引号),否则输出“ trapped ”(不含引号)
    

    我的代码是:

    #include <stdio.h>
    int main()
    {
    	int shuru[1000] = { 0 };
    	int shuru_len = 0;
    	char pass[7] = "escape";
    	char non_pass[8] = "trapped";
    	int flag = 0;
    
    	scanf("%d", &shuru_len);
    
    	for (int i = 0; i < shuru_len; i++)
    		scanf("%d", &shuru[i]);
    
    	for (int i = 0; i < shuru_len; i++) {
    		flag = 0;
    		if (!(shuru[i] & 1)) {
    			flag = 1;
    		} else {
    			for (int i = 3; i < shuru[i] / 2; i += 2) {
    				if (shuru[i] % i == 0) {
    					flag = 1;
    				}
    			}
    		}
    		if (flag)
    			printf("%s\n", pass);
    		else
    			printf("%s\n", non_pass);
    	}
    	return 0;
    }
    

    这代码应该没问题吧?

    编译提示了 编译错误

    可我在本地使用 gcc ./escape.c -o escape -std=c99编译顺利通过, 使用测试数据[4, 5 6 7 8]也输出了应有的结果, gcc --version 输出的是:

    ➜  ~ gcc --version
    gcc (Raspbian 4.9.2-10) 4.9.2
    Copyright (C) 2014 Free Software Foundation, Inc.
    This is free software; see the source for copying conditions.  There is NO
    warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
    
    

    uname -a 执行结果为:

    Linux RaspberryPi-2B 4.9.65-v7+ #1056 SMP Fri Nov 24 13:58:07 GMT 2017 armv7l GNU/Linux
    

    请大家帮忙看看是怎么回事, 多谢啦

    16 条回复    2017-12-06 19:24:43 +08:00
    ayyll
        1
    ayyll  
       2017-12-03 18:24:23 +08:00   ❤️ 1
    貌似求约数也可以,如果 m % n == 0 那么 n 至少要有两个以上的约数(除了 1 和本身),而求约数的复杂度是 O(sqrt(n)) 总复杂度为 T * O(sqrt(n))
    tigerstudent
        2
    tigerstudent  
       2017-12-03 18:33:32 +08:00   ❤️ 2
    试试选 c++去提交。会不会是 for 循环里的 int 定义不能放里面?
    wwqgtxx
        3
    wwqgtxx  
       2017-12-03 18:33:39 +08:00   ❤️ 1
    你确定人家说了可以用 C99 语法了么
    CEBBCAT
        4
    CEBBCAT  
    OP
       2017-12-03 18:39:46 +08:00
    @ayyll #1 您的意思是说假如 n 有两个因数那 n 即为合乎要求的数字吗?我也是这样想的呢;可能是我代码太抽象, 哈哈

    如果(n 为偶数)
    n 肯定存在另一个因子,使这个因子与 2 乘积为 n, 这二者会使(n-1)!是 n 的整数倍
    如果(n 为奇数, 且在 3~n-1 的范围内有因数,那么 n 同样合乎题意,不再证明)
    CEBBCAT
        5
    CEBBCAT  
    OP
       2017-12-03 18:42:10 +08:00
    @tigerstudent #2
    @wwqgtxx #3

    谢谢两位的提醒, 我看过了, 只写了内存与时间的限制, 并没有说明对应语言的编译程序与编译选项, 但我稍微修改过代码是可以编译的, 只是不能 100%通过, 所以应该不是标准的事
    leewangyang
        6
    leewangyang  
       2017-12-03 21:57:06 +08:00 via Android   ❤️ 1
    @CEBBCAT 这题本质就是判断素数呗,要用筛法才能全过。

    编译问题的话,他们之前说的应该没错,c89 for 里面不能直接 int,我们学校 oj 就不说,但是默认 c89,最好交的时候直接选 c++
    CEBBCAT
        7
    CEBBCAT  
    OP
       2017-12-03 22:11:32 +08:00
    @leewangyang #6
    好像你的解法更接近出题着的意愿, 可是我没看明白; 我提交是用了 C++ 的
    leewangyang
        8
    leewangyang  
       2017-12-03 22:18:06 +08:00 via Android
    @CEBBCAT m=(n-1)的阶乘,考虑如果 n 是一个质数,m 不可能是 n 的倍数是吧,n 是一个合数,那么 n=k*j ( kj 是两个质因子,而且 kj 均小于 n )也就是说 m=k*j*(其他剩下的),所以 m 一定是 n 的倍数
    CEBBCAT
        9
    CEBBCAT  
    OP
       2017-12-03 22:32:37 +08:00
    是四楼里那样的吗?我也是把 m 分拆为 m = n * other 的
    leewangyang
        10
    leewangyang  
       2017-12-03 22:46:40 +08:00 via Android
    @CEBBCAT 噢噢噢,你在那楼的分析已经差不多了,可以推出这题就是找质数问题了
    但是后来我想了一下有一点小问题,刚才的分析忘记考虑 kj 相等的情况(也就是 n 是完全平方数),如果 kj 相等,m=k*(除了 k 的部分)这个时候就要考虑 k 是否是质数,是质数则 m 不是 n 倍数(比如 n=4 或者 n=49 时候 m 不是 n 的倍数),不是质数则 n 是 m 倍数(比如 n=16 或者 n=81 ),所以你分析的里面对于偶数一定有 2*n ( n=4 是反例),奇数的时候,如果不是完全平方数,则判断 n 是否是质数,如果是完全平方数,则判断平方根是否是质数。。。。手机码字,见谅
    leewangyang
        11
    leewangyang  
       2017-12-03 22:51:44 +08:00 via Android
    @CEBBCAT 刚才理论有点乱

    结论是,偶数 2 4 不满足
    奇数,质数不满足,质数的完全平方数不满足

    逻辑:
    1. 判断奇偶,偶数判断是否是 2 4,奇数进入 2
    2. 判断是否是完全平方数,完全平方数判断平方根是否是质数,不是完全平方数进入 3
    3. 判断是否是质数

    判断质数最好用筛法
    CEBBCAT
        12
    CEBBCAT  
    OP
       2017-12-03 22:54:46 +08:00
    @leewangyang #10 这次可真是 哇!(Wrong Answer)了, 没想到 4 = 2 * 2 这种情况, 多谢指教啦
    CEBBCAT
        13
    CEBBCAT  
    OP
       2017-12-03 22:57:57 +08:00
    @leewangyang #11 嗯嗯,好的,我再想想为什么 n 为质数时不可能合乎题意
    ayyll
        14
    ayyll  
       2017-12-06 17:36:09 +08:00
    @CEBBCAT 是滴 我有点傻了 竟然忘了素数的概念了。。 这题本质就是判断 n 是否是素数 , 判断素数的算法多的是,随便搞就可以了 看你的代码是除到了 n/2,其实到根号 n 就可以了。。不明白可以百度体会下其中的奥妙
    ayyll
        15
    ayyll  
       2017-12-06 18:28:39 +08:00
    额 大概是我 1L 说的思路,判断约数比较直观
    代码 : http://paste.ubuntu.com/26124159/
    我注册试了一下可以过的~
    CEBBCAT
        16
    CEBBCAT  
    OP
       2017-12-06 19:24:43 +08:00 via Android
    @ayyll 对呀对呀,现在想明白了,就是判断素数。但我觉得除到 n/2 的理由是……觉得开平方太费时间了,多引入一个库也挺讨厌的……

    好吧,其实我是心存侥幸的啦,确实是到平方根比较好😅
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   3779 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 29ms · UTC 10:37 · PVG 18:37 · LAX 02:37 · JFK 05:37
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.