TLE比赛结束 经典题目回顾
icon2 Program Impossible | icon4 2009-02-16 21:26| icon312 Comments | 本文内容遵从CC版权协议 转载请注明出自matrix67.com

    创意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);
}


    另一个牛题目是Print 'D Penguin,要求你写一个打印企鹅ASCII Art的程序,程序的输出结果必须和这个文件一模一样,代码越短越好。最牛的代码有点让人摸不着头脑:

main(i,z,n){for(;z="_���?��T���G�T��J��T��N�T��P�T�Qp�T�:�?�@�T��9��<��?T��9�8č;�9č?T��9�:�;�;��>T��9��9�;�Č9��?T�9��9�Ď?T�9�����?T��8�����@�T��9�먎AT��9�稐�A�T��9��㨓�A�T��;��@�T��;��@�T��<�A�T��<ਥB�T��=�ĖĒ���B��T��>���⩗��C�T�=���CT��;ਗ�C�T��<���CT�;ਧ��CT�;�ġ�C�T���=���C�T�?���D�T�?���D�T���=����C�T���Č9�ħ���D�T��Ĩ9�ė���B��T���Ĩ;ħ�?���T��Ĩ<��Ĩ�9Ĩ��T��Ĩ;�Ģ�ĩ�T���Ĩ9ਠĨ��T��Ĩ9����T���Č9���;��T��Ĩ:œ��>��T���N��T���N��T����=��A���T����騣���T"[i++]&255;)for(n=z%28;putchar(" `x\nX '.:_"[z/28]),n--;);}

    这个代码实质上是将整个图片压缩为了一个字符串。由于图片中连续字符出奇的多,我们便想到把“n个字符c”编码为一个字节。字符串的每一个字节取值都是0到255,而图片中只有10种字符(用0到9编号),因此一个字节最多可以表示出255/9=28个连续的相同字符。对于每一个0到255的数,令字符c等于它除以28的商所对应的字符,令n等于它除以28的余数,然后程序打印出n个连续的字符c出来。例如,106=3*28+22,它就代表了22个连续的3号字符。一个麻烦问题是,9*28已经等于252了,因此你最多只能处理连续的三个9号字符。不过没关系,令9号字符为“_”就行了,这是该图片中出现次数最少的字符,而且每次它都是单独出现的。

12 条回复

  • 楼层: 沙发 | | printf 说:

    激动的抢个沙发!

  • 楼层: 板凳 | | zvaly 说:

    学习是学不了了,当个激励吧

  • 楼层: 地毯 | | zfaustk 说:

    这个..怎么想出来的..

  • 楼层: 地板 | | oldherl 说:

    大牛对print和think这两道题解释一下吧……

  • 楼层: 地下室 | | Superwyh 说:

    那个ASCII的Tux好可爱……

  • 楼层: 地基 | | 123 说:

    完整源码?用啥编译的?

  • 楼层: 地壳 | | sqybi 说:

    PENGUIN这题...我做的时候以为编译器处理不了不可见字符的...

  • 楼层: 地幔 | | leehark 说:

    class那题其实可以这么定义
    class multiply{int*mult(int(a),int(b)){...}};
    其中空格,可用不可见字符代替比如alt+12

  • 楼层: 地核 | | Matrix67: My Blog » Blog Archive » 经典证明:Chaitin定理 不可能编程判断代码的最简性 说:

    [...]     今天学到一个好玩的东西。仿照停机问题的研究方法,我们可以想出很多有趣的不可解问题。Gregory Chaitin曾经提出过下面这个问题。如果两段代码运行之后能够输出相同的结果,我们就称较短的代码比长一点的那个更简洁(注意,如果程序需要读入数据,读入数据也算进代码长度)。对于一个指定的输出,一定存在一个“最简的”代码,它是所有能输出此内容的程序代码中最短的一个。在刚刚结束的TLE比赛比赛中,参数选手拼了命地缩减每一个字符,写出来的代码一个比一个短。有人或许在想,这些代码究竟能短到什么程度?你如何才能知道你的代码已经不再有改进的空间了?受此启发,我们的问题出来了:你能否编写一个程序,使得该程序能够判断任意一段代码是否是最简的?     Chaitin定理指出,上述问题是一个不可解问题,再牛的人也不可能编写出这样的程序。证明方式与大多数此类问题一样,都是采用反证加构造的方法证明的。你能想到这个证明方法吗? [...]

  • 楼层: 10楼 | | aw 说:

    我是来看看楼层效果的……

  • 楼层: 11楼 | | lonelycorn 说:

    g++吧?要么就是GCC,反正不是gcc。

  • 楼层: 12楼 | | 永远的魔灵 说:

    基本上所有用"*"可以消除空格的地方用一对括号也行

您也随便说几句吧:

您可以在 Gravatar 设置您的头像。