测试电脑开机密码破解

"知乎杯"2018CCF大学生计算机系统与程序设计竞赛CCFCCSP2018时间:2018年10月25日09:0021:00目录A.
绝地求生/Battleground2B.
贪心算法/Greedy7C.
卷积/Convolution11D.
分组加密器/Encryption14E.
内存分配器/Malloc25"知乎杯"2018CCF大学生计算机系统与程序设计竞赛A.
绝地求生/BattlegroundA.
绝地求生/Battleground.
时.
间.
限.
制:4.
0秒.
空.
间.
限.
制:512MB【题目描述】《绝地求生》是一款战术竞技型射击类沙盒游戏,玩家需要在游戏地图上收集各种资源,并在不断缩小的安全区域内对抗其他玩家,让自己生存到最后.
本题简化了游戏规则,需要你计算出最终的游戏结果,简化版规则如下.
【游戏规则】游戏地图是n*n的正方形棋盘,由1*1的方格组成,每个玩家用一个1*1的方格表示.
在不超出棋盘边界的情况下,玩家可以向.
八.
个.
方.
向(上、下、左、右、左上、左下,右上、右下)移动,进入周围的格子,一次移动称为一步.
下图示意性地给出了玩家a和玩家b可能的移动方向,由于玩家b位于棋盘的边缘,因此可能的移动方向仅有5种.
第2页共34页"知乎杯"2018CCF大学生计算机系统与程序设计竞赛A.
绝地求生/Battleground棋盘中可能有.
障.
碍.
物,障碍物也是1*1的方格,玩家不能进入障碍物的方格,也不能穿越两个斜向相邻障碍物方格的间隙.
不同玩家之间.
互.
不.
影.
响,他们可以出现在一个方格里面.
【游戏流程】游戏开始时,会给出棋盘的大小、玩家数量、障碍物数量、每个障碍物的位置、每个玩家的初始位置.
所有的玩家在游戏开始时,都会被赋予相等的"生命值".
一次游戏分为多个回合,在游戏开始时,会给出本次游戏的回合数目.
每回合开始时,都会给出每个玩家的目标位置.
在这一回合内,玩家需要从上一回合结束时的位置(对于第一回合则为初始位置)移动到这一回合的目标位置,移动的步数不限.
如果玩家在这一回合的起始位置和某一障碍物重合,那么假定在这一回合内,该障碍物对于.
该.
玩.
家是失效的.
下图中给出了某一回合开始时,玩家a的位置(1,2)和目标位置(1,3),以及玩家b的位置(2,0)和目标位置(3,3).
第3页共34页"知乎杯"2018CCF大学生计算机系统与程序设计竞赛A.
绝地求生/Battleground每一回合内,都会出现大小、位置都固定不变的一个圆形的安全区域,直到本回合结束.
安全区域的圆心位于方格中心,如果某个方格的中心到圆心的.
直.
线.
距.
离小于或等于安全区域的半径,那么这个方格就是.
安.
全.
的.
从不安全的方格移动一步到其他位置会被.
扣.
除1.
点.
生.
命.
值.
安全的方格内的障碍物将会.
在.
本.
回.
合.
失.
效,允许玩家通过.
所有玩家的目标位置保证是安全的.
图中圆心的方格坐标是(2,3),半径为2,浅灰色的方格是安全的方格,安全的方格内的障碍物会在本回合失效.
你的任务是,为每一位玩家找到.
生.
命.
值.
扣.
除.
最.
少的移动路线.
若对于某位玩家,任何到达本回合目标位置的移动路线都会导致生命值扣除至0,则称该玩家.
死.
亡.
死亡的玩家不参与之后回合的游戏.
下图展示生命值扣除最少的移动路径,在此过程中,玩家a不被扣除生命值,玩家b被扣除1点生命值.
所有回合结束后,你需要输出所有玩家剩余的生命值,已经死亡的玩家输出0.
第4页共34页"知乎杯"2018CCF大学生计算机系统与程序设计竞赛A.
绝地求生/Battleground【输入格式】从标准输入读入数据.
输入第一行包括五个整数:n、m、e、f、h,表示棋盘为n*n大小,一共有m个玩家,棋盘上有e个障碍物,游戏一共有f个回合,玩家的初始生命值是h.
1≤n≤400,1≤m≤105,0≤e≤n*n,1≤f≤10,0:进行一个特定的测试,输出正确性、时间等信息.
-c:进行一次特定的测试,仅评测正确性,用来检测正确性很方便.
-v:对每一个测试点进行测试时输出额外信息.
-h:输出命令行参数.
Java解题框架你需要在Solve.
java中实现myInit(),myMalloc(),myFree(),myRealloc()函数.
第29页共34页"知乎杯"2018CCF大学生计算机系统与程序设计竞赛E.
内存分配器/Malloc具体地,在所给的框架中,包含以下一些文件/文件夹:src/Makefile:用于编译,生成.
class文件.
src/MyMain.
java:测试程序的入口.
运行时会调用Tester类,读取相应的测试点,按照操作指令调用你实现的函数进行测评.
src/MyUtils.
java:一些工具函数.
src/Tester.
java:Tester类,用于读取相应的测试点并进行测评.
src/Solve.
java:你所需要填写的代码文件,提交时仅能修改该文件.
其中:–你需要实现myInit(),myMalloc(),myFree(),myRealloc()函数.
–你可以在该文件中添加你可能要用到的变量、函数和其他代码.
Readme.
pdf:针对Java框架的额外说明,请.
务.
必阅读.
src/short1src/short2:用于测试你程序的两个较小的测试样例,便于你调试.
data:一些你可以用于本地测试的测试文件.
在答题中,有以下.
注.
意.
事.
项:提交的代码运行后务必不能输出任何额外信息,即你最终提交的Solve.
java文件中不应该包含println类似的输出.
.
测.
试.
程.
序.
运.
行.
方.
法:你可以在下发框架的src目录下,在终端中执行make命令编译代码.
编译成功后,直接执行javaMyMain,即可进行完整测试,并得到相应的输出,可选的参数如下:-f:进行一次特定的测试,输出正确性、时间等信息.
-c:进行一次特定的测试,仅评测正确性,用来检测正确性很方便.
-v:对每一个测试点进行测试时输出额外信息.
-h:输出命令行参数.
【输入格式】本题的测试程序会运行一系列的测试点,按照其中的操作指令,调用你自己实现的动态内存分配器执行相应的操作,并进行正确性检验以及相应性能指标的统计.
测试点的输入是文本格式,前两行格式如下:[num_ids]/*numberofrequestid's*/[num_ops]/*numberofoperations*/第30页共34页"知乎杯"2018CCF大学生计算机系统与程序设计竞赛E.
内存分配器/Malloc从第3行开始每行对应着一个具体的操作指令,分别对应malloc、free和realloc中的一种操作,格式如下:a[id][size]/*ptr_[id]=malloc([size])*/r[id][size]/*realloc(ptr_[id],[size])*/f[id]/*free(ptr_[id])*/其中size为在[0,226]之间的整数.
一个非常简单的测试点示例如下:38a0512a1128r0640a2128f1r0768f0f2其中有些测试点中会出现f-1,表示实际为执行free(NULL).
以及测试点中可能出现下述形式的片段:a341234a33a23a30f49a38a17a35a31a43600这种形式实际可以理解成下述形式:第31页共34页"知乎杯"2018CCF大学生计算机系统与程序设计竞赛E.
内存分配器/Malloca341234a331234a231234a301234f49a381234a171234a351234a311234a43600(其实你不需要过多研究测试点的格式,因为你需要编写的内存分配器不需要处理输入数据.
)【输出格式】你正确实现内存分配器后,编译并运行测试程序,会输出相应的测试结果,其中包括正确性、堆利用率以及耗费时间等指标信息.
对于某个测试点,如果你的程序未能通过正确性检验,则并不会输出利用率等信息.
其中堆利用率的输出为(0,1)之间的小数,时间的输出为以秒为单位的小数,两者都保留到小数点后6位.
堆利用率.
堆.
利.
用.
率是测试程序调用你实现的my_malloc、my_realloc等函数的过程中请求分配的"内存"累计总量的最大值与你的分配器最终所使用的堆大小之比.
你需要尽量减少堆内碎片化程度从而让堆利用率提高.
例如对于下面的测试文件:38a0512a1128r0640a2128f1r0768f0f2第32页共34页"知乎杯"2018CCF大学生计算机系统与程序设计竞赛E.
内存分配器/Malloc测试程序向你的程序请求分配的"内存"累计总量最大值为:896Bytes(512+128+(640512)+128).
假如你实现的分配器通过调用mem_sbrk函数申请的堆大小为:1024Bytes,则堆利用率此时为:8961024=0.
875.
耗费时间.
耗.
费.
时.
间是指测试程序读取一个测试文件的指令序列后,按照其中的操作指令,依次调用你实现的动态内存分配器执行所有相应的操作所用的总时间,用t表示.
样例输出一个可能的测试运行结果如下:Resultsforyourmalloc:idvalidutilsecsfilename0yes0.
8578240.
0286091.
in1yes0.
7613530.
0007572.
in2no--3.
in上述输出表示:你实现的代码可以通过1.
in的测试,其中堆利用率为0.
857824,耗费时间为0.
028609秒(2.
in测试文件类似).
但是你的代码并不能通过3.
in的测试.
【评分方式】本题的分数分为两部分:正确性分数和性能分数.
正确性分数满分为20分,包括20个测试点.
若选手的程序能够在给定的时间、空间限制下正确处理.
全.
部测试点,则得20分,否则得0分.
这里的时间限制即评测网站上显示的时间限制,与前文所述的.
耗.
费.
时.
间不同,这里的时间限制.
包.
括我们提供的框架运行的时间,而.
耗.
费.
时.
间不包括.
对于每个测试点,我们保证我们的框架运行总时长不超过4s,因此可以认为只要你的函数每个测试点的运行时长不超过6s,就能保证不会超过时间限制.
性能分数满分为80分,包括20个测试点,每个测试点的满分是4分.
若正确性分数为0分,那么性能分数也为0分;否则每个测试点的分数计算方式如下:对于第i个测试点,设ui为选手程序的堆利用率,ti为选手程序的耗费时间,Ui为所有选手程序运行此测试点堆利用率的最大值,Ti为所有选手程序运行此测试点耗费时间的最小值,并取:αi=1Ui1ui第33页共34页"知乎杯"2018CCF大学生计算机系统与程序设计竞赛E.
内存分配器/Mallocβi=Titi那么选手在该测试点的性能得分si为:si=4*(0.
7αi+0.
3βi)选手的性能分数为各测试点的性能得分之和,本题的得分为正确性分数和性能分数之和,共计满分100分.
【阅读材料】本题为了还提供了一些关于动态内存分配的阅读材料,你可以在下发文件夹中找到相应的文件,有选择性的进行学习.
这里对一些阅读材料进行简要的说明.
basic文件夹:该文件夹下主要提供了关于动态内存分配基本原理的一些资料,其中包括一些经典的综述论文、相关教材章节以及相关的Slides等.
你可以通过学习该文件下的资料,掌握动态内存分配的基本模型与原理,从而能更轻松的解决本题.
advanced文件夹:该文件夹下主要提供了一些进阶的阅读材料,其中既包括例如实际环境中采用的tcmalloc、ptmalloc、jemalloc等算法与实现分析,也有诸如对针对实时系统进行优化的内存分配算法TLSF的介绍.
你通过阅读学习其中的一些材料可能能够得到一些启发,从而更好更高效的解决本题.
第34页共34页