Posts Tagged “solution”


ZOJ Monthly, May 2011
A ZOJ3500 Electron Cloud 27.20% (139/511)
B ZOJ3501 Roman Order 30.79% (400/1299)
C ZOJ3502 Contest 15.11% (78/516)
D ZOJ3503 Quadratic Surface 2.28% (4/175)
E ZOJ3504 P-norm 49.43% (262/530)
F ZOJ3505 Yet Another Set of Numbers 28.00% (42/150)
G ZOJ3506 Cut the Tree 17.94% (21/117)
H ZOJ3507 Fractal 13.20% (66/500)
I ZOJ3508 The War 13.53% (226/1670)
J ZOJ3509 Island Communication 4.24% (7/165)

一是准备给包括在去年参加过集训在内的xpies一次新手上路前热身的机会。二是因为神奇的原因,存有summer2009和summer2010数据的ZOJ服务器在省赛后被拔网线了。所以这次的题目来自校赛省赛未用题(ABCD)、summer2007(J)和summer2008(EFGHI)。就算题目总体看来水题很多啦,不过两个小时被圆满什么的>_<,何方神圣啊orz(台大一队?)……不管怎样把五月份混过去了,下次Monthly大概在六月底了吧……

ZOJ3500. Electron Cloud

downloadsource code (ZOJ3500.cpp) [math]

求两个球的并的体积。

判断两个球的位置关系和圆没有区别,在相离、相切和包含的时候很简单,所以主要就是要考虑相交的情况。这时候的体积是两个球冠的体积,球冠的体积可以很简单的积分得到:

\int_{z=-r}^{h}{\pi\sqrt{r^2-z^2}^2}=\pi r^2(h+r)-\frac{1}{3}\pi(h^3+r^3)

而要求h1h2,也只要解:

Comments 46 Comments »

这是第8届浙江省大学生程序设计竞赛(The 8th Zhejiang Provincial Collegiate Programming Contest)的比赛点评。这不是官方的解题报告,裁判组也将不会提供官方的解题报告和测试数据。


第8届浙江省大学生程序设计竞赛
A ZOJ3487 Ordinal Numbers 39.24% (312/795)
B ZOJ3488 Conic Section 21.27% (160/752)
C ZOJ3489 Old Labels 2.00% (1/50)
D ZOJ3490 String Successor 10.86% (88/810)
E ZOJ3491 Wall-nut Bowling 0.00% (0/12)
F ZOJ3492 Kagome Kagome 38.00% (233/613)
G ZOJ3493 Palm Up and Palm Down 0.00% (0/1)
H ZOJ3494 BCD Code 18.75% (3/16)
I ZOJ3495 Lego Bricks 8.33% (2/24)
J ZOJ3496 Assignment 11.11% (2/18)
K ZOJ3497 Mistwald 16.66% (13/78)
L ZOJ3498 Javabeans 28.44% (225/791)
M ZOJ3499 Median 30.47% (263/863)

原定的题目只有A-L,比赛前一周姐姐看过题目后表示还是太难,于是又加了一道M。13道题,是姐姐的吉利数字(参考试机赛B题Lucky Number)。其中水题有5道,结果开场对于OJ来说压力实在太大,ZOJ上一长排的Queuing,直到90min后system load才降下来。由于省赛专科和本科在一起比,实力跨度也很大,所以难度控制一直是比较困难的。这次简单题稍微多了一些,而原本我们以为只是中等题的K和I似乎对于很多队伍来说还是太难了。最主要的是,除了冠军队HDU-Knuth外,其它队伍的跳坑顺序完全出乎裁判们的预料= =b 有很多队伍都热衷于折腾赛前被认为是不适合在中期搞的题,而悲剧的是,他们也确实没有搞出来……


The 8th Zhejiang Provincial Collegiate Programming Contest (online)
A ZOJ3487 Ordinal Numbers 51.24% (413/806)
B ZOJ3488 Conic Section 29.45% (291/988)
C ZOJ3489 Old Labels 5.26% (6/114)
D ZOJ3490 String Successor 15.50% (198/1277)
E ZOJ3491 Wall-nut Bowling 0.00% (0/13)
F ZOJ3492 Kagome Kagome 55.55% (345/621)
G ZOJ3493 Palm Up and Palm Down 10.52% (4/38)
H ZOJ3494 BCD Code 15.90% (7/44)
I ZOJ3495 Lego Bricks 10.20% (5/49)
J ZOJ3496 Assignment 12.19% (10/82)
K ZOJ3497 Mistwald 10.97% (46/419)
L ZOJ3498 Javabeans 46.88% (339/723)
M ZOJ3499 Median 51.83% (381/735)

赛前vls曾预测冠军会有10~11题,而我表示今年题目虽然和去年相当,但冠军只有9题,最后还是我猜对了。六年之后,浙大又一次省赛丢杯,不过这一次丟得毫无意外,虽然如此,我还是很看好现在这一批集训队或有意进入集训队的xpies的。比较意外的是我原以为同步赛会有11题的,结果是只有4个10题的。也许是由于我们的失误,J题赛后rejudge了,影响了某些队伍向11题进发的脚步吧。

ZOJ3487. Ordinal Numbers

downloadsource code (ZOJ3487.cpp) [if-else]

输入基数词,输出序数词。为了降低难度,还直接把规则给你了,题目描述里还附带无数测试数据。

Comments 59 Comments »

这是第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 »