Posts Tagged “python”

上上次上次的题解,补上这最后一部分。这次的三道题分别是我出的程序员六级阅读理解题Crack Me II;复数表达式解析计算题(误)Complex Calculator;和大自然数值积分题(大误)Bessel Function II

ZOJ3441. Crack Me II

[cpp + indent, sorting, set_difference]

题目就是要求写一个和这段天书一样的代码(ZOJ3441txt.c)功能完全相同的程序。

这一题是程序员四级阅读理解题ZOJ1584 Crack Me的加强版。首先说说这段天书是怎么来的吧,其实最初是一段非常简单的Haskell程序(ZOJ3441hs.hs)。然后我简单的用C重写的了一遍所有函数,于是得到了下面的C语言程序(ZOJ3441c.c),因为是按Haskell的思路来写的,所以几乎没有循环,全是递归。之后就是人肉宏替换了,其实写这段代码远比看懂它要辛苦啊。

如果你直接提交这段代码,会MLE,一看程序你就会发现,不断的malloc,完全不free。即使处理了内存泄漏,依然会TLE。有的时候可以通过只修改瓶颈代码来AC,比如ZOJ1584就可以这样做,不过这一题就行不通。

解决这道题的一种办法是通过够找各种sample,测出这段程序的功能。这是一个比较可取的办法,不过如果遗漏掉了任何一个地方都会WA,通常也会设置一些这样的陷阱,比如ZOJ1584在长度大于某个阈值的时候要数出”0″,这是很难测出来的。这段程序没有太xe的地方,不过对于负数的处理,也是要花点时间来找规律的。

另一种方法就是阅读代码了,这段代码的直接阅读难度要远远大于ZOJ1584。不过我们为什么要直接阅读呢?宏展开这种事编译器不就能做么,何必人肉?gcc -E命令就可以将宏展开,其实背后就是调用了GCC中一个叫cpp的程序,cpp是The C Preprocessor,只要

cpp ZOJ3441txt.c > ZOJ3441cpp.c

就得到了宏展开的代码,不过代码缺少良好的缩进,还是不可读,再利用代码格式化工具,比如indent,来处理一下

indent ZOJ3441cpp.c

这样代码(ZOJ3441cpp.c)的可读性就比较强了,唯一的麻烦就是变量名都没有意义,你可以在阅读的同时替换成有意义的名字。

Comments 2 Comments »

接着上次4道比较简单的题的解题报告写。这次是Detect the Virus IIAn Unusual Problem的解题报告,主要涉及如何在C, C++, Java, Perl, Python中使用正则表达式与及无损压缩算法

ZOJ3440. Detect the Virus II

[regex, topSort]

题目简单来讲就是通过上下文无关语法(context-free grammar, CFG)描述了virus。问一个字符串是否存在virus形式的子串。题目保证描述不会有环/递归。

这题用正则表达式(Regular expressions, regex)来做是再自然不过了,比如sample就等价于下面这段perl代码:

# subparta:=fg|g
$subparta = qr(fg|g);
# parta:=a|b|c
$parta = qr{a|b|c};
# partb:=d|e[subparta]h
$partb = qr{d|e($subparta)h};
# virus:=[parta][partb][partb]
$virus = qr{($parta)($partb)($partb)};

printf 'abcdefghijklm' =~ $virus ? "YES\n" : "NO\n";
printf 'nopqrstuvwxyz' =~ $virus ? "YES\n" : "NO\n";

当然,因为代码是顺序执行的,所以我们调整了几个record的顺序。顺插一句,如果是函数式编程语言的话,那顺序就完全无关紧要了。于是问题就是给定的字符串能否匹配题目所描述的正则表达式,不过因为输入的顺序不确定,所以要麻烦一点,不过即然没有环,一个拓扑排序就搞定了(ZOJ3440watashi2.pl)。

Comments 15 Comments »

ZOJ在建站105个月之后迎来了第一百场比赛。

””\\( ̄ー ̄) ( ̄ー ̄)//””

办一场比赛来庆祝一下,这个想法最先是姐姐在邮件中提出的:

所谓求人不如求己,我自己的记录里是有序号的,所以知道我们目前有98场原创比赛和10场Practice了!喂,要不要庆祝一下第100场呀??!^_^

而我们在ZOJ2.1提供了几个脚本语言的支持后,也一直想办一场“非主流”的比赛。所以便有了今天的 Let’s Celebrate the 100th Contest on ZOJ! — An Unusual Contest powered by ZOJ Staff 这场9道非同寻常的题组成的9小时9分9秒的比赛。题目的准备还是比较匆忙的,事实上除了hhanger的一道题以外,所有题都是最近几天出的。感谢参与出题和验题的navi, hhanger, quark, hsys猛犸也钻地等童鞋,也感谢大家的捧场和支持。


Let’s Celebrate the 100th Contest on ZOJ!
100A ZOJ3437 Very Hard Problem 6.89% (28/406)
100B ZOJ3438 Tripartite Graph 62.28% (71/114)
100C ZOJ3439 Substitution Cipher 7.86% (36/458)
100D ZOJ3440 Detect the Virus II 0.00% (0/26)
100E ZOJ3441 Crack Me II 2.06% (2/97)
100F ZOJ3442 Complex Calculator 0.00% (0/1)
100G ZOJ3443 Bessel Function II 0.00% (0/0)
100H ZOJ3444 An Unusual Problem 5.12% (2/39)
100I ZOJ3445 1KB 9.09% (4/44)

下面是解题报告:


剧透的分割线,看题解之前建议您自己先思考一下


Comments 11 Comments »


ZOJ Monthly, October 2010
A ZOJ3406 Another Very Easy Task 34.45% (317/920)
B ZOJ3407 Doraemon’s Cake Machine 9.41% (55/584)
C ZOJ3408 Gao 8.38% (29/346)
D ZOJ3409 KKV 53.33% (8/15)
E ZOJ3410 Layton’s Escape 9.90% (99/999)
F ZOJ3411 Special Special Judge 18.87% (127/673)
G ZOJ3412 Special Special Judge II 30.23% (13/43)
H ZOJ3413 Special Special Judge III 4.79% (13/271)
I ZOJ3414 Trail Walk 34.31% (257/749)
J ZOJ3415 Zhou Yu 12.08% (11/91)

发现十月份已经被Regional占满了,所以只好把Monthly安排在了国庆节的最后一天,星期四……最近事情比较多,所以Monthly的准备也比较仓促,题型和难度的控制可能不是很好,最后原计划的压轴题也没有整理出来,于是临时换上了一道水题(就是A题)。赛前moondy看了这套题就说要有无数队提前圆满了,还好最后这种事没有发生。

ZOJ3406. Another Very Easy Task

downloadsource code (ZOJ3406.pl) [regex]

题目虽然没有描述,但摘自wiki的sample input本身就是题目描述,再一看sample output应该马上就知道要做什么了:只要把超过2个字符的单词都转成由首字母加上省略字母个数加上尾字母组成的缩写就好了。

临时换上这题的想法原先是希望有人能快速用perl/python/php这些新加的脚本语言,通过正则秒杀掉。不过事实上只有一个人用了python写这道题。标程是用perl写的,非常短,顺带一提,这题的测试数据就是rfc2616

ZOJ3407. Doraemon’s Cake Machine

downloadsource code (ZOJ3407.py) [math, enumeration]
cake-3-5

这题问的就是n个小朋友分一个蛋糕,切m刀,在保证公平的前提小,最少要砍死几个小朋友克隆几个蛋糕。

Comments 24 Comments »

Python里有个特殊的变量__name__,如果当前模块是主模块,则为’__main__’,否则为模块名。通过判断

if __name__ == '__main__':

执行不同的代码,这样一个模块即可被重用,又可以单独执行,这种结构在Python里非常常见。也可以在if里简单的做一些模块的测试:

# gao.py
def scanl(s, f, a):
	retval = [s]
	for v in a:
		s = f(s, v)
		retval.append(s)
	return retval

if __name__ == '__main__':
	print scanl(1, int.__mul__, range(1, 10))
else:
	print __name__, 'imported'
#> [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880]

而当gao被import时,这些测试将不被执行:

# gaogao.py
import gao
print 'in' + __name__ + ':', sum(gao.scanl(10000000, int.__div__, range(1, 20)))
#> gao imported
#> in__main__: 27182814

在Perl中虽然有个类似的__PACKAGE__可以得到包的名字(get package name),但是却不像Python中的__name__那样可以判断是否是直接执行的。我没

Comments No Comments »