出了一道好题目却不知道该怎样投递到各大OJ上?现在不用担心这个问题了,因为你可以直接把自己的Blog变成一个OJ。Scarky是一个建立在SPOJ系统上的OJ平台。所不同的是,任何人无需注册便可以编写自己的题目并发在自己的网站上与网友分享,并且网友们提交答案时也不需要进行注册。这个网站的功能还在不断扩充中,但目前就Programming Challenge模块看来,这个网站已经很强大了。以后我有了好题目就用这种方式和大家分享了,这里先试用一下,题目来源好像是某次USACO月赛。
SPOJ
终于AC了:用BrainFuck语言过SPOJ测试题
SPOJ的多语言确实很牛,竟然连WhiteSpace语言也支持(很早就听说过这种语言,它的代码仅仅包含空格、Tab和回车三个字符,其余字符一律不认)。今天,我在提交语言的列表里看到了另一个叫brainf**k的语言,顿时来了兴趣。
brainf**k=BrainFuck。如果哪天我发明一种语言叫“太他妈的牛逼了”,矜持一点的OJ也会称呼它“太XXX牛B语言”。这种语言符合图灵机模型,语法暴简单,通篇8种字符,一看就会:
> 指针加一
< 指针减一
+ 指针指向的字节的值加一
– 指针指向的字节的值减一
. 输出指针指向的单元内容(ASCII码)
, 输入内容到指针指向的单元(ASCII码)
[ 如果指针指向的单元值为零,向前跳转到对应的]指令的次一指令处
] 如果指针指向的单元值不为零,向回跳转到对应的[指令的次一指令处
比如,下面这段代码可以在屏幕上打印出“Hello World!”:++++++++++[>+++++++>++++++++++>+++>+<<<<-]
>++.>+.+++++++..+++.>++.<<+++++++++++++++.
>.+++.------.--------.>+.>.
后来,我看了看SPOJ的第一题,读一串数,读什么你就输出什么,直到你读到一个数字42位置。这个题目出得比A+B Prob要好,因为几乎所有的语言都可以AC。我决定用BrainFuck把这道题过了。我仔细想了一下,主要是在想如何用这个语言来表示and运算。后来调试了一会儿,发现了几个错误,最终成功AC了。给大家看一下我的AC代码:>>,>,
< <<++++++[>>--------<<-]>>---- [>>+>]<[<]> <<++++++[>>++++++++<<-]>>++++
> <<++++++[>>--------<<-]>>-- [>+>]<[<]>> <<++++++[>>++++++++<<-]>>++ >
[<<. [-]>[-<+>],>[-]<<
<<++++++[>>--------<<-]>>---- [>>+>]<[<]> <<++++++[>>++++++++<<-]>>++++
><<++++++[>>--------<<-]>>-- [>+>]<[<]>> <<++++++[>>++++++++<<-]>>++ >]
后来我看到了SPOJ论坛上的一个标程,虽然标程比我的代码长得多,但也漂亮的多。+[>>----------
[++++++++++<,----------]
>--------------------------------------------------
>----------------------------------------------------
>
[
<++++++++++++++++++++++++++++++++++++++++++++++++++++
<++++++++++++++++++++++++++++++++++++++++++++++++++
[>]<
[.<]++++++++++.---------->
[>]>>
]<
[++++++++++++++++++++++++++++++++++++++++++++++++++++
<++++++++++++++++++++++++++++++++++++++++++++++++++
[>]<
[.<]++++++++++.---------->
[>]>
]<
[>++++++++++++++++++++++++++++++++++++++++++++++++++++
<++++++++++++++++++++++++++++++++++++++++++++++++++
[>]<
[.<]++++++++++.---------->
[>]
]<
]
任何一个领域里总是有牛人出现。我在网上看到,居然还有BrainFuck编程比赛。比如,有一次比赛题目叫大家用BrainFuck语言编写3x+1问题。输入一串数,你需要编程求出这些数按照3x+1变换规则进入循环各自需要多少步。标程短得惊人:>,[
[
----------[
>>>[>>>>]+[[-]+<[->>>>++>>>>+[>>>>]++[->+<<<<<]]<<<]
++++++[>------<-]>--[>>[->>>>]+>+[<<<<]>-],<
]>
]>>>++>+>>[
<<[>>>>[-]+++++++++<[>-<-]+++++++++>[-[<->-]+[<<<<]]<[>+<-]>]
>[>[>>>>]+[[-]<[+[->>>>]>+<]>[<+>[<<<<]]+<<<<]>>>[->>>>]+>+[<<<<]]
>[[>+>>[<<<<+>>>>-]>]<<<<[-]>[-<<<<]]>>>>>>>
]>>+[[-]++++++>>>>]<<<<[[<++++++++>-]<.[-]<[-]<[-]<]<,
]
这种语言语法之简单,还产生出很多有意思的东西。比如,你可以想到用c语言或者pascal语言完全可以编写一个不到50行的BrainFuck编译器。还有,我们也可以用BrainFuck语言来写一个BrainFuck的编译器。事实上,有人真的也写出来了,我也看到代码了。太牛B了。
做人要厚道
转贴请注明出处