首页
论坛
专栏
课程

[比赛题目] [结束][第二阶段◇第二题]看雪论坛.腾讯公司2008软件安全技术竞赛

2008-10-21 11:51 10727

[比赛题目] [结束][第二阶段◇第二题]看雪论坛.腾讯公司2008软件安全技术竞赛

2008-10-21 11:51
10727
【进行中】[第二阶段◇第二题]看雪论坛.腾讯公司2008软件安全技术竞赛
本次比赛规则及奖品请参看此帖:http://bbs.pediy.com/showthread.php?t=73422

第二阶段比赛说明

本阶段共二道题目,每题计分每题的计分方法,将在题目放出时公布。(各题的分数将算入最后的总数,在决定最终名次时,每一题都很重要)。二道题不是同时给出,在第一题结束后,再放出第二题,以此类推。但无论答题正确与否,都有资格参与下一题的回答。若题目答错或未答,该题均计0分。


第二阶段第二题

请编写程序解决附件文档中的大数运算问题,使运算速度尽可能快。

答题要求

1. 请按照文档要求答题。
2. 上传方式:将分析文档和相关源代码打包后,一起上传到“看雪论坛.腾讯公司2008软件安全竞赛答案提交区”,多次提交,请提交在一个帖子内。

其他注意事项

1.比赛答题期间,不得在论坛或群等公开场所讨论。
2.比赛答题期间,不得泄露测试程序任何相关技术细节。
3.违反第1,2条,取消相关人员比赛资格


提交机会:此题每个选手有多次提交附件的机会.但从第二次提交附件起,每提交一次分数减4分做为惩罚,详见计分公式.以最后一次提交结果为最终计分结果,之前的提交不进行计分.

计分公式

参数说明:
提交后测试机器为AMD和Intel多核处理器,内存均为2G。
结果提交后,均分别在上述两台机器上运行10次,取GetTickCount差值的平均值分别作为x与y,则运行时间t计算为t= (x+y)/2,提交后统计运算速度最快的选手的时间为T。
其他见文档描述。

答题时间:2008-10-21 12:00 至 2008-10-26 12:00止.

通过标准
见文档描述。

赛事预告:休赛二天后,2008-10-28中午12点正式开始第三阶段比赛。

补充说明
1.文档中符号描述部分不是很精确,符号包涵小数点'.',等于号'='(这个主要可以明确定位最后的位置,方便解析),负号'-'等,另外空白符自动过滤掉。
2.“文件output.txt中输出运算结果,要能输出结果小数点后至少40位。”这句话中40位是说明在超过40位小数的情况下保留40位小数,其余有多少位就保留多少位,或者愿意补足0也可以。
3.不能专门对输入做优化这句话说得是不能特地输出特定输入的结果。
4.“参与运算的数位不限”,这个不考虑超过2^30的情况(考虑的话也非常欢迎)。
5.另外补充说明,最终测试结果所用input.txt由评委提供,不会出现极端情况,大家不要过虑。

[公告]安全服务和外包项目请将项目需求发到看雪企服平台:https://qifu.kanxue.com

上传的附件:
最新回复 (118)
windsun 1 2008-10-21 12:02
2
0
sf....
海风月影 17 2008-10-21 12:04
3
0
题目太难了
123456
Aker 4 2008-10-21 12:04
4
0
这道题目与时间无关,而且把周末也包含进去了,大家慢慢做题目,哈哈,有问题随时给我论坛短消息



你就扯吧,每道题目都说完全不懂,每道都做得不错:D
这道题大家都能做,但是能做到啥程度就八仙过海了



k是代码风格和文档等:)看那个说明文档里面。
海风月影 17 2008-10-21 12:06
6
0
评委的机器真好
我只有迅驰1.5G单核CPU+512M内存
windsun 1 2008-10-21 12:08
7
0
要判断四则运算式的合法性吗?
沙金 4 2008-10-21 12:11
8
0
这题太难了!!!
海风月影 17 2008-10-21 12:12
9
0
我想问个问题?
附件提供了bigcalc函数模板,我能不能自己添加其他的函数?
比如bigadd,bigsub,bigmul,bigdiv等等

还有,一定要按照bigcalc.cpp里面来写嘛?能不能自己重写?
还有,算时间一定是按照bigcalc.cpp代码来算嘛?能不能自己重写?

还有第三阶段要做多少分才能进啊?
Aker 4 2008-10-21 12:13
10
0
需要判定四则运算式的合法性,过会给个例子测试程序,非最终计算的运算式
frozenrain 2008-10-21 12:19
11
0
算QQ位数 12位 13位。。。TX要让老外人手一个QQ
sessiondiy 4 2008-10-21 12:24
12
0
N久N久以前用postfix写过这题
N太大代码不见了
shoooo 16 2008-10-21 12:30
13
0
都可以google到的啊
海风月影 17 2008-10-21 12:34
14
0
shoooo 16 2008-10-21 12:38
15
0
www.google.cn
输入
0xAAAAAAAAAAAAAAAAAAAAAAAAAA*0xBBBBBBBBBBBBBBBBBBBBBBBBBBBB
马上有答案,太强了
DiKeN 5 2008-10-21 12:40
16
0
1.输入合法性检测是否需要;
2.输入/输出样例必须需要, 不管是IOI还是ACM好像对于有输入输出的都给出了样例的;
3.这题超出了一般人研究范围, 至少超出我的研究范围了啊.
4. 可以用汇编或者扣别人的汇编代码不?
DiKeN 5 2008-10-21 12:45
17
0
自己写大数运算还是可以使用别人的现成的?
DiKeN 5 2008-10-21 12:50
18
0
参与运算的数位不限?这个是不是就有问题。如果这个有2^32^32^32^32bits了还可以吗?
如果要精确的结果, 肯定不能使用cpu的浮点数运算了, 有点不懂哦.
shoooo 16 2008-10-21 13:01
19
0
第二轮这两题都和软件安全无关
看来TX想招程序员
glery 2 2008-10-21 13:04
20
0
先回复,再等大牛的思路
shoooo 16 2008-10-21 13:08
21
0
这题不需要思路
google源码就行了
google不到可以去csdn散分求助
qdk 2008-10-21 13:10
22
0
csdn去年有人弄了个大数运算的库。
据说很强
ccfer 13 2008-10-21 13:27
23
0
没限制层数啊,可能所有的利用栈实现的答案都是不正确的

比如A写的程序可以处理10000层的栈,而你给个10001层的表达式让他算呢
而B写的程序刚好可以处理10001层的栈,就侥幸通过了
vxasm 6 2008-10-21 13:43
24
0
Google 计算器
111 111 111 111 111 111 111 + 222 222 222 222 222 222 222 222 - (((333 333 333 333 333 * 44 444 444 444 444 444) / 555 555 555 555 555) * (666 666 666 666 666 666 666 - 7 777 777 777) * 8 888 888) = -1.58024676 × 1044 


要是有人写个东西,直接把输入递交给Google,然后Google返回的作为输出打印出来,不知这样算不算哦?
busy 2008-10-21 13:45
25
0
Python里计算貌似不限位数,但是也是有说内存限制的...
Aker 4 2008-10-21 13:49
26
0
1.需要扫描式子的合法性,要解析优先级等等。
2.输入输出样例已添加
3.大家都能做一点:)
4.可以用汇编,但是要说明优化思路。



自己写


理论上不限参与位数,优化的策略.....



优化阿优化,题目大家一起参与,呵呵



可能会存在这种情况,
限制层数不太好操作,大家自由发挥~



要自己做,Google的结果和要求不太一样
glery 2 2008-10-21 13:49
27
0
搜了一下发现,还真是不少源码啊

这题估计不是考查编程能力,而是考查搜索以及测试评估的能力
popeylj 6 2008-10-21 13:52
28
0
比武招人 ?
DiKeN 5 2008-10-21 13:58
29
0
下次是会写求微分积分,微分方程的算法的

最后就可以做一个Maple,MATLAB,MathCAD或者Mathematica出来了.  

加油吧.
DiKeN 5 2008-10-21 14:03
30
0
http://www.portal-to-web.de/pub/pkgsrc/distfiles/entropy_rsa-0.9.0-433.tgz
http://caml.inria.fr/pub/distrib/caml-light-0.75//cl75unix.tar.gz
http://www.openssl.org/source/openssl-0.9.7d.tar.gz
http://www.bullfreeware.com/download/sources/aix43/pgp-6.5.1i.tar.gz
ftp://ftp.sunfreeware.com/pub/freeware/SOURCES/bind-8.4.6.tar.gz
ftp://sh.wide.ad.jp/WIDE/free-ware/pet/pet-3.56.tar.gz
http://entropy.stop1984.com/files/entropy_rsa-0.9.1-439.tgz
http://omniorb.sourceforge.net/snapshots/omniORB-3.0-latest.tar.gz
http://www.cs.chalmers.se/pub/haskell/yale/hugs0src.tar.gz
http://www.ip2location.com/download/C-IP2Location-2.1.1.tar.gz
http://ftp.debian.org/debian/pool/main/p/putty/putty_0.58.orig.tar.gz
http://www.apfloat.org/apfloat/2.31/apf231.zip
http://www.netsw.org/crypto/toolkits/cryptlib-2.1-beta.tar.gz
http://www.lirmm.fr/~plantard/TER/rsa_rns.tgz  (简单的rsa)
ftp://ftp.compapp.dcu.ie/pub/crypto/miracl.zip
http://ftp.gnu.org/gnu/libg++/libg++-2.8.1.1a.tar.gz

除了上述四款软件用到小数了,好像其他的都没有哦。
google的运算是利用浮点数运算的好像,因此计算结果好像有误差的,不知道现在改没有。
Aker 4 2008-10-21 14:07
31
0
这里没几个和大数相关的~
另外比赛期间不讨论的说
dttom 3 2008-10-21 14:57
32
0
[QUOTE=Aker;524022]【进行中】[第二阶段◇第二题]看雪论坛.腾讯公司2008软件安全技术【进行中】[第二阶段◇第二题]看雪论坛.腾讯公司2008软件安全技术竞赛
本次比赛规则及奖品请参看此帖:http://bbs.pediy.com/showthread.php?t=73422
..........
第二阶段第一题

请编写程序解决附件文档中的大数运算问题,使运算速度尽可能快。

...[/QUOTE]

应该是第二阶段第二题吧?
shoooo 16 2008-10-21 15:04
33
0
文件output.txt中输出运算结果,要能输出结果小数点后至少40位
楼主的output.txt附件的结果,小数点后只有1位
笨笨雄 14 2008-10-21 15:18
34
0
这条题可否理解为即使提交源码的情况下也能神不知,鬼不觉地HOOK了GetTickCount
我怀疑他们也找到VC6或者VS2005,VS2008上的可执行任意代码的漏洞
qdk 2008-10-21 15:24
35
0
发个paper链接,应该不算违规
http://cr.yp.to/papers/m3.pdf

Abstract.This paper surveys techniques for multiplying elements of various communicative rings.
It covers Karatsuba multiplication,dual Karatsuba multiplication,Toom multiplication,dual Toom multiplication,the FFT trick,the twisted trick…
ccfer 13 2008-10-21 15:27
36
0
评委的测试机是具有抗干扰能力的,能自动修复对GetTickCount的hook
ccfer 13 2008-10-21 16:05
37
0
疑问1.
关于"-"符号,文档中只说到: - 代表减法
应该意思是输入表达式中是没有负数的吧
如果出现负数情况就算作无效表达式了
比如:2+(-1)=
就应该当无效表达式对待?

疑问2.
根据提供的样例,输入表达式最后以'='结尾的
如果所给的表达式最后没有'=',是不是也按无效表达式处理?
ccfer 13 2008-10-21 16:23
38
0
发现一个矛盾的地方,文档中有下面几条描述

四则运算符号:
+ ,- ,* ,/ 以及(,)
+代表加法,-代表减法,*代表乘法,/代表除法,优先级按照通常的约定,乘除大于加减,括号内的优先级高于括号外。
数字:
0 ~ 9,十进制
输入:
文件input.txt,文件中为上述符号组成的运算式子,input.txt将由评委提供,不能专门对输入做优化。

意思是说input.txt中只会有+-*/()0123456789一共16种符号,出现空格也算无效输入吗?
而提供的样例input.txt中却在最后出现一个'=',这个'='显然不属于前面所述的16个符号之一
mstwugui 6 2008-10-21 16:32
39
0
支持楼上的,按照文档理解应该只有16种符号,否则输入时还要额外考虑正负数,小数点,空格等等,但这些都不在文档中了
Aker 4 2008-10-21 16:43
40
0
1、有效,描述不太恰当
2、文档描述不是很全,=号,.号也是需要的,
3、空格都过滤就是

见上描述,我在最顶上修改下说明。
qdk 2008-10-21 16:54
41
0
1、数字前面可以有 - 号,那会不会有 + 号
2、这样的数字  .0003456  、(-.0003456)  、 (+.0003456)       算不算合法
海风月影 17 2008-10-21 16:57
42
0
判断输入是否合法就可以作为一条题目来做了
无限位的大数运算又是一条题目
四则混合运算又是一条

总结:这是一条综合题
mstwugui 6 2008-10-21 17:00
43
0
这也允许那也允许,越来越糊涂了
qdk 2008-10-21 17:05
44
0
数字合法判断是某oj上的一条水题,但是我一直没有AC
nkspark 3 2008-10-21 17:10
45
0
严重怀疑海风月影每次都从shoooo那里要答案..................
Aker 4 2008-10-21 17:12
46
0
测试文件中表达式不会出现该类情况,但是常规情况下,qdk所说的也是合法的,解析更优,发现问题越来越多,也就说明题目还是有做头的,加油...
海风月影 17 2008-10-21 17:16
47
0
其实我每次都是威逼利诱aker后得到的答案



你给个最bt的测试文件吧,我按那个标准做
qdk 2008-10-21 17:23
48
0
严重支持
shoooo 16 2008-10-21 17:33
49
0
我提议,大家都把自己的t控制在1分钟整
有速度快的,自觉Sleep一下
这样你好我好大家好

同意的来顶
海风月影 17 2008-10-21 17:38
50
0
我要算10分钟,无法控制啊
大家还是把自己的t控制在1小时吧
if(t<1小时)
t=1小时;
游客
登录 | 注册 方可回帖
返回