Posts Tagged “ZOJ”

这是第11届浙江大学程序设计竞赛(The 11th Zhejiang University Programming Contest)的比赛点评。这不是官方的解题报告,裁判组也将不会提供官方的解题报告和测试数据。不过我可能会在点评中介绍一下我们是如何出题、验题和构造测试数据的。


The 11th Zhejiang University Programming Contest
A ZOJ3477 Akasim Matrix 0.00% (0/21)
B ZOJ3478 Binary Land 50.00% (2/4)
C ZOJ3479 Chinese Zodiac 47.61% (150/315)
D ZOJ3480 Duck Typing 17.28% (14/81)
E ZOJ3481 Expand Tab 8.33% (4/48)
F ZOJ3482 For Loop 0.00% (0/4)
G ZOJ3483 Gaussian Prime 5.32% (60/1127)
H ZOJ3484 How Many Parallelograms on the Grids? 0.00% (0/120)
I ZOJ3485 Identification Number 8.41% (9/107)
J ZOJ3486 Judge Internal Error 32.58% (145/445)

现场赛没有人过AFH,特等奖7题,比较可喜的是Ranklist上百花齐放,比较遗憾的是4题以上的队伍偏少。由于机器存在“时差”,网上同步赛其实只相差十几分钟,最后有4个8题,没有人AC H题实属意外。比赛的时限应该是比较合适的,除了A题,都有10倍TL,其中G和J都是按照比较暴力简单的算法来设置的。测试数据应该是比较强的,经过认真设计和严格测试。


The 11th Zhejiang University Programming Contest (online)
A ZOJ3477 Akasim Matrix 0.00% (0/33)
B ZOJ3478 Binary Land 21.42% (18/84)
C ZOJ3479 Chinese Zodiac 62.41% (382/612)
D ZOJ3480 Duck Typing 14.37% (46/320)
E ZOJ3481 Expand Tab 11.82% (11/93)
F ZOJ3482 For Loop 4.80% (5/104)
G ZOJ3483 Gaussian Prime 14.76% (216/1463)
H ZOJ3484 How Many Parallelograms on the Grids? 0.00% (0/126)
I ZOJ3485 Identification Number 19.77% (70/354)
J ZOJ3486 Judge Internal Error 46.06% (375/814)

校赛和省赛的题目出到一半,突然想整理一套A-J,所以对题目做了一番调整,把原来准备放校赛的题目踢到了省赛,又临时yy了几道题。DEG都是我特意为校赛准备的,可以说没太多算法,比的就是基本功。这次完全没有出那种接触过ACM就秒杀,没接触过就不会的那种没有营养的题目。

ZOJ3477. Akasim Matrix

downloadsource code (ZOJ3477.cpp) [矩形切割, 线段树, parameter search, off-by-1]

坂御矩阵(Misaka.reverse Network Matrix)是学园都市超牛的网格计算平台。里面的姐妹们节点们都有一个唯一的2元组序列号(serial number),她们像矩阵中的元素一样排列。最近魔法少女小◯攻击了坂御矩阵,注入了名为“爱的战士”的治愈系病毒。病毒将在第di天感染序列号(xi, yi)的节点,并以天为单位传播开来。学院都市想要在所有节点被感染前,在某个节点上制作出杀毒程序。题目要求所能争取的最多的时间和对应的字典序最小的节点。

Comments 27 Comments »


ZOJ Monthly, February 2011
A ZOJ3467 3D Knight Moves 7.14% (5/70)
B ZOJ3468 Dice War 39.82% (92/231)
C ZOJ3469 Food Delivery 13.33% (24/180)
D ZOJ3470 Magic Squares 42.85% (72/168)
E ZOJ3471 Most Powerful 21.23% (86/405)
F ZOJ3472 Play Bridge 66.66% (2/3)
G ZOJ3473 Radio Matrix 20.40% (20/98)
H ZOJ3474 Taekwondo 11.62% (15/129)
I ZOJ3475 The Great Wall I 46.15% (6/13)
J ZOJ3476 The Great Wall II 11.11% (1/9)

summer2010的题用得差不多了,无论简单题还是中等题都有些紧俏了,自己的几个idea又准备留给校赛和省赛,不舍得扔出来,于是从summer2008和summer2009里抠了几道题出来。即使去掉校赛和省赛两个monthly,到7月还要再坚持整理两套monthly呢,果然每场比赛都用10+道题太贅沢了么,难道要求助summer2007了……总觉得一场比赛有太多的圆满不太好,不过有好几道题没人过或没提交也不是太漂亮呢,选题验题好难啊 >______<

ZOJ3467. 3D Knight Moves

downloadsource code (ZOJ3467.cpp) [双向搜索, Bidirectional search]

判断在三维棋盘中,一步能跳(x, y, z)的马能否在6步之内从(x1, y1, z1)跳到(x2, y2, z2)。如果有,输出步数最少的字典序最小的方案。

Comments 55 Comments »


ZOJ Monthly, January 2011
A ZOJ3457 Absence Number 19.32% (23/119)
B ZOJ3458 A Simple Math Problem 8.33% (7/84)
C ZOJ3459 Extraordinary 24-Point Game 0.00% (0/0)
D ZOJ3460 Missile 21.73% (20/92)
E ZOJ3461 Money Transfer 30.43% (7/23)
F ZOJ3462 Nobita’s New Filesystem 11.53% (3/26)
G ZOJ3463 Piano 40.74% (11/27)
H ZOJ3464 Rugby Football 42.37% (114/269)
I ZOJ3465 The Hive 28.51% (71/249)
J ZOJ3466 The Hive II 11.11% (1/9)

因为学校忙完才到家,所以monthly的准备显得有些仓促,结果原本推迟安排在这个月的几道题还是没有整理出来,转而挑了几道不那么需要fix的题。下个月的monthly在两周后,寒假应该有些闲暇去整理他们了,争取能放出来。J题有人过了,但C题没人提交,原本以为I题是最水的,结果比较意外,没被圆满,值得庆幸。已经是2011年了,summer2010的题也用了过大半了,之后就是校赛和省赛了,然后离summer2011也不远了^ ^

ZOJ3457. Absence Number

downloadsource code (ZOJ3457.cpp) [misc]

给定一个两位数N,求最小的m,使得1/m的十进制表示中恰好包含除N以外的所有两位数。

最大的解是N=0时m=76344。题目的输入只有100种,所以可以暴力跑表,1/m十进制表示是循环小数,且在m步内开始循环,所以很容易求得其包含的所有两位数,最后判断一下是否满足条件就好了。注意不要漏数了两个循环节头尾组成的那个两位数,否则有几个数据会WA。更简单的方法是不判断循环节,直接循环m+1步。加上一些优化后,这个表实际可以在1s之内跑出。

ZOJ3458. A Simple Math Problem

downloadsource code (ZOJ3458.py) [math]

find \lfloor(\sqrt{a}+\sqrt{b})^n\rfloor \mod 2(a+b) , where 0 < b - a < 1 + 2\sqrt{a} \text{ and } n \text{ is even}

Comments 23 Comments »


ZOJ Monthly, December 2010
A ZOJ3446 Doraemon’s Battle 13.84% (54/390)
B ZOJ3447 Doraemon’s Number Game 29.66% (35/118)
C ZOJ3448 Doraemon’s Number Game II 0.00% (0/4)
D ZOJ3449 Doraemon’s Number Game III 18.77% (40/213)
E ZOJ3450 Doraemon’s Railgun 11.28% (22/195)
F ZOJ3451 Doraemon’s Shooting Practice 8.33% (2/24)
G ZOJ3452 Doraemon’s Stone Game 33.89% (20/59)
H ZOJ3453 Doraemon’s Sweet Bullet 25.00% (5/20)
I ZOJ3454 Nobita’s Letter 36.36% (8/22)
J ZOJ3455 Shizuka’s Letter 27.95% (26/93)
K ZOJ3456 Traveler Nobita 7.50% (3/40)

ZOJ3446. Doraemon’s Battle

downloadsource code (ZOJ3446.cpp) [search, bfs]

Doraemon初始有lh的血量和0的技能值,有n个敌人,他每回合有4种选择:

  • 消灭一个敌人并增加一个技能值;
  • 回复lh/5血量;
  • 用尽现有技能值s,打掉Ds个敌人;
  • 不动。

Doraemon回合之后,若剩下m个敌人,则其血量减少m,技能值增加m%3。Doraemon的血量若小于等于0,就挂了。问最少多少回合消灭所有敌人。

不动这个选择显然是没有好处的。只要从初始状态出发,用[h][s][n]标记走过状态,bfs就可以了。注意D数组不一定是递增的,所以每一步都要尝试三种可能的操作,过度的剪枝可能会WA。不过有一个很有效的剪枝就是:“实际上对于相同的敌人数与技能值,HP越多越好,因此只要记录HP最多的状态就可以了”(by pxhdg)。加上这个剪枝之后,原本350ms的程序一下减到了10ms。

ZOJ3447. Doraemon’s Number Game

downloadsource code (ZOJ3447.py) [greedy, BigInteger]

贪心。结果最大的策略就是:不断最小的两个数,计算后放回数集之中;相反的,结果最小的策略就是:不断取出K个(如果不足则取出全部)最大的数,计算后放回数集之中。题目结果很大,需要高精度。

Comments 12 Comments »

上上次上次的题解,补上这最后一部分。这次的三道题分别是我出的程序员六级阅读理解题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 »