TLE比赛结束 经典题目回顾

    创意C/C++编程挑战赛Time Limit Exceeded结束,题目果然非常有创意。大家可以在这里看到比赛题目和获胜选手的代码。其中两道题很有意思,我特别喜欢。

    一道叫做Compile Error的题目要求你写一个叫做multiply的类,里面包含一个mult(int a,int b)的函数,该函数用于打印出a和b的乘积。代码中不允许出现空格、“/”和“#define”。

    第一个问题就是,定义一个类的语句是class multiply{…},这个空格要怎么避免?只要你知道typedef int foo也可以写成int typedef foo,我们就可以利用typedef来消除空格,把类的定义写成class{…}typedef multiply。但这下后面又冒出一个空格来,这个空格怎么消呢?一个巧妙的方法就是利用int typedef foo,bar的语句,把类定义语句写成class{…}typedef*foo,multiply,其中*foo是一个不会用到的类型,但是它帮助我们奇迹般地消除了一个空格。巧妙利用星号可以消除很多空格,例如我们在定义mult函数时就可以写成void*mult(…){…}。最后一个难题就是,定义函数mult(int a,int b),参数表里面的两个空格怎么办?其实办法依然很多。不少网友都用到了typeof,这样便可以把int a写成typeof(int)a了。完整的类定义如下:

class{public:void*mult(typeof(int)a,typeof(int)b){cout<<a*b<<endl;return(0);}}typedef*m,multiply;

    在gcc下,即使警告全开,下面这个程序编译时也一声不吱。

#include <iostream>
using namespace std;
 
class{public:void*mult(typeof(int)a,typeof(int)b){cout<<a*b<<endl;return(0);}}typedef*m,multiply;
 
int main()
{
    multiply foo;
    foo.mult(23,67);
}

Read more…

比比谁的代码短:TLE测试赛结束

    上次提到,我非常关注一个即将举办的另类编程挑战赛Time Limit Exceeded,这个比赛的得分算法很另类,它将根据你代码的总长度和特定字符的多少而定。在刚刚结束的测试赛中,有几个题目非常具有挑战性,参赛者提交的代码也是牛气冲天。

 
Power of 2
问题:
    输入数据含有多行,每行一个正整数。对每个数,检查看它是否是2的幂,是则输出yes,不是则输出no。
    你的程序不允许使用分号。
    规定0也是2的幂。

得分:
    S= length of code + number of whitespaces;
    score = (250000)/(S^2);

Read more…

预告:几个有趣的编程比赛

刚过完年回到家,也跟大家说一声新年快乐。
今天莫名其妙地收到一封邮件,邀请我参加felicity.iiit.ac.in举办的几个编程比赛。我看了一下介绍,这些比赛还是挺有意思的,这里向大家推荐一下。

http://felicity.iiit.ac.in/codecraft/
CodeCraft,举办了两三年了,一个传统方式的编程比赛。
测试赛:14th Feb, 6pm – 8pm IST (GMT +5:30).
正式比赛:15th Feb, 2pm – 10pm IST (GMT +5:30).

http://felicity.iiit.ac.in/~math/
MathematiKa,已经举办过一年了,这是第二年的比赛。比赛共12道数学题,你只需要提交答案即可。例如,去年的第四题叫你计算前30个正整数x使得F(x) = 5x^2 + 14x + 1是一个完全平方数。提交时,把所有30个数从小到大连接在一起即可。最大的那个x有十几位,因此这题硬算是不行的。
测试赛:12th Feb, 6pm – 9pm IST (GMT +5:30).
正式比赛:13th Feb, 2pm – 10pm IST (GMT +5:30)

Read more…

Al Zimmermann编程大赛已经开始

    来自MathPuzzle的消息:新一轮的Al Zimmermann编程大赛开始了。这次比赛的问题描述如下:

对于一个给定的n,找出n个正整数,使得通过它们之间的加减运算能够得到尽可能多的质数。

    具体的说,对于一个指定的n,参数选手需要提交n个数A1, A2, …, An。这n个数将由公式ΣAi*Ci产生3^n个和(其中每个Ci可以取-1、0和1中的任一个),这3^n个和中(不同的)质数越多越好。例如,当n=4时,10, 29, 82, 106可以产生9个不同的质数:

5 = 106 + 10 – 82 – 29
19 = 29 – 10
29 = 29
43 = 82 – 29 – 10
53 = 82 – 29
67 = 106 – 29 – 10
101 = 82 + 29 – 10
149 = 106 + 82 – 29 -10
227 = 106 + 82 + 29 + 10

    参赛者需要完成n=3, 4, …, 14共12个问题,提交的每一组数的和不能超过2^32-1。比赛将在2008年11月10日结束,你可以在此之前提交任意多次。获胜者可以从下面两个网页中任选一个雕刻品作为奖品。说实话,奖品很诱人,我很想要。
    http://www.bathsheba.com/sculpt/
    http://www.bathsheba.com/math/