题目名称 | 雪球游戏 | 这是一道送分题 - IO交互 | 这是一道送分题 - grader交互 | 打倒llq |
---|---|---|---|---|
题目类型 | dark模拟 | 水的一批的交互题 | 更水的交互题 | 这场娱乐赛的核心,奇奇怪怪的对抗题 |
题目目录 | snewbal1l | hackllq | hackllq_again | f1ght |
源程序文件名 | snewbal1l.cpp | hackllq.cpp | hackllq_again.cpp | name.cpp |
输入文件名 | snewbal1l.in | \ | \ | \ |
输出文件名 | snewbal1l.out | \ | \ | \ |
时间限制 | 50ms | 1000ms | 1000ms | \ |
内存限制 | 1024MiB | 512MiB | 1024MiB | \ |
提交文件限制 | 100KiB | 100KiB | 100KiB | 100KiB |
数据组数 | 10 | 10 | 10 | \ |
满分分数 | 100 | 100 | 100 | 100 |
main()
函数返回值必须为 int
且为 g++ -o sample sample.cpp -lm -Wl,--stack=2147483647 -std=c++14 -O2
。-fsanitize=undefined,signed-integer-overflow,address
以检测未定义行为、整数溢出,地址越界等问题。从 OI 的角度来看,这道题是很失败的、很无意义的、很浪费时间的,这道题可能更符合“为了出而出”,而并未考察任何算法,只是超过 12K 的码量的堆砌而形成的高难度长时间以及难以调试。
而我出这道题的本意更多也就只是“为了出而出”,因为是第一次出题,这道 T1 更多是希望能够通过这一道题面几千字的大模拟,来让我更去注意与考虑到题目的细枝末节,尽量让题目更严谨更合理。
因此,这道很奇怪的 T1 便诞生了,所以最终这道 T1 可以认为是一个 ex,也就是附加题,可以仅作观赏食用,当然如果真的能做出来也是可以得到
当然,实话实说,这道题按照我原来的想法,是想要出的更巧妙点的,按照我的本意,这道题最终会形成一个与 Unity3D 的实现机制十分相似的模拟,全程的判定都与帧率这一核心息息相关,但是最终确实实力不济,如果按照这个思路强行模拟的话,码量实在是太大了,题目本身的叙述也将需要更加严谨很多,所以最终选择加了很多的限制让这道题变得没有那么巧妙,为了让实现变得简单,从而使题变得有些呆板与无趣,也请各位见谅。
于是——这道题便被放到了娱乐赛中。
某一天早上,当 tsawke 打开机房大门的时候,突然发现天地之间一片苍茫——机房下雪了!tsawke 自然想去打雪仗,但是这样可能会感冒,于是 tsawke 决定趁着 llq 还没到机房,拉着 cc0000,sssmzy,zpair 一起去玩风靡全球的游戏 Snewbal1l,首字母最接近的 tsawke 和 sssmzy 被分配到了一组,首字母差距最大的 zpair 和 cc0000 被分配到了一组。
而对于常玩游戏的你们一定知道,很多游戏的帧率会影响到游戏过程中的判定。
如果你了解过 Unity3D,一定知道每一帧都会调用一次 Update()
函数,且其中我们经常使用这样一个常量:Time.deltaTime
,举个例子,对于 C# 中的 transform.Translate(x, y, z)
函数,我们可以这么理解:
若写成 transform.Translate(0, 0, 1 / 60 * 10)
即 Update()
每执行一次物体移动
若写成 transform.Translate(0, 0, Time.deltaTime * 10)
,则若 Update()
每秒执行
而对于上面的写法,若 Update()
每秒执行
可以粗略地认为,Time.deltaTime
的值就是
我们一般通过这种方式来保证对于使用不同帧率的玩家,游戏总是公平的,而游戏 Snewbal1l 却默认不使用 Time.deltaTime
。
对于 2v2 非回合制游戏 Snewbal1l,存在一个有边界的二维矩形地图,横纵的单位距离均定义为
定义瞬时性操作为瞬时完成的,持续性操作为需要消耗帧数的,且保证对于未限定消耗帧数的均认为是瞬时性操作。
显然在游戏中一定会出现每一秒操作后不同玩家的游戏结果不同的情况,由于这是一个不公平的游戏,对于持续性操作,所以我们会按照玩家之间输入操作顺序的先后作为优先级并叠加影响,即若 tsawke 在 sssmzy 之前操作,在 tsawke 的帧率下处理一遍持续性操作,并记录最终的状态,若游戏未结束,则保留当前的状态并在 sssmzy 操作时再次以 sssmzy 的帧率重新处理一遍所有人的持续性操作。换句话说,每个人的持续性操作都可能被执行四遍。
对于任意一个角色有如下几个信息:
对于所有玩家都有如下的操作:
"*"
:向着当前朝向丢一个雪球,每一帧向前闪现 "+"
:在接下来的 "w"
:在一帧的时间里向上移动 "a"
:在一帧的时间里向左移动 "s"
:在一帧的时间里向下移动 "d"
:在一帧的时间里向右移动 "t"
:向右旋转方向,即将朝向进行如下变换:对于不同的职业,有如下信息和特定操作组合:
基础信息:
特定操作:
"f"
:对自己周围八个方向的距离小于等于 "g"
:若 基础信息:
特定操作:
"f"
:对自己面前距离小于等于 "g"
:将自己的血量变为原来的 基础信息:
基础信息:
特定操作:
"f"
:使所有敌人的 "g"
:使所有队友的 "x"
:敌对方所有人任意一人若满足 "p"
:使敌对方所有人的帧率变为原来的 基础信息:
特定操作:
"f"
:使所有队友的 "g"
:使所有队友的 一些细节:
"waa"
,则第一帧向上走 首四行每行两个字符串,第一个字符串为玩家名称,第二个字符串保证格式为数字+fps后缀,如 "60fps"
,表示某个玩家电脑的初始帧率。
接下来一行为两个整数,分别表示地图的纵和横的大小。
接下来四行每行两个字符串,第一个字符串为玩家名称,第二个字符串为职业名称。
接下来四行每行一个字符串和三个整数,分别表示玩家名称、初始坐标的横坐标和纵坐标、朝向。
接下来有若干组数据,每组数据满足如下格式:
"+"
最多仅出现一次,并一定在 "wasd"
之前。"*"
最多仅出现连续的一段,并一定在 "wasd"
之前。保证输入文件以
首行一行字符串,表示获胜方:
具体地,若 tsawke 和 sssmzy 获胜,则输出
"tsawke & sssmzy are the winners!"
。若 zpair 和 cc0000 获胜,则输出
"zpair & cc0000 are the winners!"
。若两方平局,则输出
"No one is the winner!"
。
第二行,输出一个整数,表示游戏的具体结束时刻,若游戏未结束则输出
第三行,输出四个整数,按顺序表示 tsawke, sssmzy, zpair, cc0000 四个人的剩余血量,已死亡输出
(注意此时输出的是在某一秒,任意一个玩家的操作完成后的血量,具体定义可参考细节中的对判定游戏是否胜利的限制)
第四行,输出四个整数,按顺序表示四个人电脑的最终帧率。
xxxxxxxxxx
191tsawke 60fps
2sssmzy 60fps
3zpair 60fps
4cc0000 60fps
55 5
6tsawke tank
7sssmzy soldier
8zpair assassin
9cc0000 magician
10tsawke 1 2 3
11sssmzy 2 2 3
12zpair 3 3 3
13cc0000 4 4 3
141
15tsawke s
16sssmzy a
17zpair a
18cc0000 w
19-1
xxxxxxxxxx
41tsawke & sssmzy are the winners!
21
3500 0 0 0
460 60 60 60
xxxxxxxxxx
241tsawke 30fps
2sssmzy 60fps
3zpair 144fps
4cc0000 60fps
520 20
6tsawke priest
7sssmzy tank
8zpair magician
9cc0000 soldier
10tsawke 7 7 3
11sssmzy 5 5 2
12zpair 10 15 1
13cc0000 6 6 4
141
15tsawke fgfg
16sssmzy +******sdwaasdasdasd
17zpair pfffxfffffffffffxx
18cc0000 fffffffffffffffgg
19128
20tsawke *gggfgfgf
21sssmzy ****
22zpair pfffffffffffff
23cc0000 fffff**tttffffffffffffgg
24-1
xxxxxxxxxx
41zpair & cc0000 are the winners!
21
30 0 21 49
436 72 115 48
xxxxxxxxxx
491tsawke 253
2cc0000 91
3sssmzy 33
4zpair 209
528268 9400
6tsawke priest
7cc0000 tank
8sssmzy priest
9zpair magician
10sssmzy 27753 5628 2
11zpair 9531 3692 4
12cc0000 8676 4963 3
13tsawke 1440 8070 4
1473
15sssmzy ***********************************wsaadtswgwtwtfswtdasatfaaswatdwsawstwwwaaaasga
16zpair +aawwttw
17cc0000 +*****************************************dswaasawaasadsaawtwtssawdwstadwtsdwsawsdtswaw
18tsawke ********************wfagswagdssgsgfwdasgwwwdadtfadtfwsdswswwfwswdsada
19127
20zpair ***********************************gdwadtpwaawffdxxpsxwsgxpxdpfwwaptttadxatwawaaag
21cc0000 *******************twwdsdsdsawstda
22sssmzy ***awwagsdsdwtgwwstw
23tsawke +******************************************fwasawtfs
24223
25sssmzy +***************************wsfwastgdafawdtgtwgwwggatdwatwswfwgdatsdsagas
26zpair aa
27tsawke ****************************************agadggdawttasgwdtsffgfawfaawgfwgsfswswtadw
28cc0000 ********daatsdwssatatwsstwdsaswsswswtsdawda
29244
30zpair *************axsftpxwtwadfxwxasxpwxxsaapagxxaafxwtxf
31tsawke wtwtsttafsfwfawggawawdgffsdgfaswawdfswdfwwasasttawdwdaawgswsttawwwgttwfgwfww
32sssmzy +*****************************wttgw
33cc0000 twtwwsaassawadasattdwtawwtwwwdwaadssaaawdaawwaswdwstawaswwswsdwswastsaatadsstaawsstatssdtattssdtddtt
34282
35sssmzy +******************************************fwfdwgwwtadfgtsfwsttfaddaaddgwddwwa
36cc0000 ***********dswstatwwawwasdddaaadwssssddstawdwtwwwswasadswwwsdtawwsaawsaaadtsadattttwtaatwdwwsadwwasd
37tsawke ****************************wsawtgfdswwdw
38zpair ************************fwfftdwpxaxgaxppdpwdaxxxgspsxtwwdwwaawtpswawtsxtpdgdtsfpxtxxxxsassstpwgpddgs
39379
40cc0000 ************wawdswwswdwwadsddwsaaswsdddwwsttdwwwataassdwwsstddwwadwtsawttwtawwssadsdsdsadaaaawwwasta
41sssmzy *******ddwfwwawaaw
42zpair *************************************************xtpawafxwwggatdfxpxpwtsgxdgwttpttxwpfsspaswxawstasw
43tsawke +**********************wwsswfwsawfwgfwatwwd
44476
45cc0000 tasswwsdttsddtaadasasasawwdsadwawaswataadwwaawatsdsdsadaaaswwastwwddswdwddad
46zpair +ftwsttt
47sssmzy *********************************tfwwswgtgwsttaga
48tsawke +ftwdtfgwdtftdffwwsddgttwasawassaffdfswgwgdaadwtdaddwsfswtwwftawwsass
49-1
xxxxxxxxxx
41No one is the winner!
2-1
3100 100 0 413
459598 7312 0 0
部分数据范围及约定已在题面中标注,剩余数据范围限制如下:
我们定义输入操作数据的组数为
对于 "wasd"
。
对于
对于
数据很友好。
请仔细阅读题目背景,并注意题面中的细节提示,思考应如何处理。
注意当游戏结束时请使游戏直接结束,可以直接忽略后面的输入,否则可能会导致超时。
Tips:可以考虑将瞬时性操作与持续性操作分开考虑,并且对于每一位玩家每秒的状态分开考虑。
以下信息均为个人理解,不保证正确性,如果发现不对的地方随时跟我说~
一般来讲交互题大致分为两种,grader 交互和 IO 交互。
grader 交互题大多是给你一个可以调用的函数,并让你实现一个函数。你只需要将提供给你的函数声明出来,并写好需要实现的函数,最终提交这一部分代码即可,而不需要实现 main()
函数。
而对于 IO 交互题,大多会“重载”你的输入与输出,通过 stdout 来向提供的交互库传参,通过 stdin 来获取交互库的返回值,同时需要注意这类题均需要在每次询问后清空缓冲区。
回到本题,因为 T1 不可做,为了保证标准的
同时对于这几道交互题和 SPJ,tsawke 会尽力去使其严谨,但不保证不会漏下在交互库里对所有数据的大小范围的限定,所以烦请各位不要特意去卡超出范围的数据,否则可能有直接 RE 的可能。
对于刷新缓冲区,一般有以下几种写法:
xxxxxxxxxx
21fflush(stdout);
2std::cout << std::flush;
同时 endl
也可以在输出换行的同时刷新缓冲区,即:
xxxxxxxxxx
11std::cout << std::endl;
如对于 IO 交互题,比较尽人皆知的便是“猜数游戏”,这里提供一个 Luogu 上的样例程序来便于理解交互的方式:
xxxxxxxxxx
191
2
3
4int main() {
5 for (int l = 1, r = 1000000000, mid = (l + r) >> 1, res; l <= r; mid = (l + r) >> 1) {
6 std::cout << mid << std::endl;
7 std::cin >> res;
8 if (res == 0) {
9 return 0;
10 } else if (res == -1) {
11 l = mid + 1;
12 } else if (res == 1) {
13 r = mid - 1;
14 } else {
15 puts("OvO, I AK IOI"); // this statement will never be executed.
16 }
17 }
18 return 0;
19}
对于以上的程序我们通过 cout
来向交互库传递参数,并刷新缓冲区,此时交互库便会返回一个值,我们通过 cin
来实现获取交互库的返回值。需要注意这里并不必须是 cin
或 cout
,只要使用的是标准输入输出的均适用。当程序结束时 return 0;
。
而对于 grader 交互题,有如下 Luogu 上的样例:
xxxxxxxxxx
131// 在本题中并不是必须的
2
3extern "C" int Seniorious(int); // 在这里需要声明一次交互库给出的函数。
4
5extern "C" int Chtholly(int n, int OvO) { // 在这里实现交互库要求你实现的函数。
6 int ans = 1;
7 for (int l = 1, r = n, mid = (l + r) >> 1; l <= r; mid = (l + r) >> 1) if (Seniorious(mid) >= 0) {
8 r = (ans = mid) - 1;
9 } else {
10 l = mid + 1;
11 }
12 return ans;
13}
首先我们需要在全局作用域声明交互库中的函数,与你需要实现的函数,见样例程序。
然后你需要实现这个函数,如样例程序,可以直接通过调用声明过的交互库中的函数,即 Seniorious(int)
,计算结束后返回要求的返回值即可,提交时也只需要提交这些代码片段。
Tips:因为咱们大多为 Windows 环境,所以这里以 Windows 为例,Linux 可以类比一下,差别不大。
Tips:以下均对于 grader 交互题而言,若为 IO 交互题,则仅需按一般形式测试即可。
对于交互题一般会给交互库的源代码,假设交互库为 interactive_lib.cpp
,提交的程序为 submit.cpp
,假设两个文件在同一目录,且命令行中所在位置为文件所在位置,那么可以使用如下命令:
xxxxxxxxxx
11g++ interactive_lib.cpp submit.cpp -o 1.exe -std=c++14 -lm -Wl,--stack=2147483647
即可生成名为 1.exe
的可执行文件。
关于 g++ 的配置,命令行和 powershell 的用法等,这里不再赘述。
生成可执行文件后在命令行输入:
xxxxxxxxxx
211.exe
2(examples)
也就是说,回车后输入将样例输入输入,即可得到程序的输出。
似乎 NOI 系列的比赛均采用 grader 交互?不太确定。
如果 IO 类的交互 NOI 系列赛不考的话,可以把这个当成一个小拓展~
是的这是一道送分题。
tsawke 成功 hack 进了 neooj.com:8082/oldoj,但是他只获得了数据库中大量用户密码的 md5 形式,tsawke 需要获取这些用户的明文密码来勒索 llq,但是他不知道如何做,只能帮你进行 md5 的正向过程,靠你来实现 md5 的破解。
为了机房的未来,这道题一定要切呀!
注意:由于 LemonLime 似乎不支持 IO 交互题,所以 tsawke 在 Luogu 上配置了这道题,最终会在 Luogu 上评测,然后记录分数。
我们得到了 llq 网站数据库中 "Completely Hacked!"
,并在这之后输出着
Tips:此题时间复杂度可以通过一些优化而去掉一个
Tips:同时这道题也并不是一个优秀的交互题,因为此题并没有去可变地限制函数调用次数,当成练手题即可。
这里我们规定,“输入”即为从标准输入中获取,“输出”即为向标准输出中输出,并刷新缓冲区。
Tips:这里的输入实际上指的是交互库输出的返回值,你进行读入,输出即为向交互库传参。
第一行输入一个整数
接下来
接下来至多
接下来一行输出 Completely Hacked!
,表示询问结束。
接下来
令明文字符串长度为
对于
对于
若你的询问次数超过
若你的输出不合法,则获得
若你输出的密码明文有任何错误,则 tsawke 将无法成功勒索 llq,获得
若你的输出全部正确,获得
对于 IO 交互题,似乎一般难以进行本地调试,可能也就是因此,NOI 系列比赛都采用的是 grader 交互,这里为了方便各位调试提供了一个头文件。
头文件可在 Tsawke's Exam - Issue/hackllq/md5.h
找到。
你可以调用一个叫做 md5_hash_hex
的函数,其原型是:
xxxxxxxxxx
11inline std::string websocketpp::md5::md5_hash_hex(std::string const &)
使用方法:在需要生成 md5 的 cpp 文件引入如下头文件:
xxxxxxxxxx
11
调用该函数,并在将明文字符串作文参数传入,将会返回 md5 形式的字符串。
注意在提交的程序中不能使用 md5.h。
xxxxxxxxxx
413
245c48cce2e2d7fbdea1afc51c7c6ad26
3eccbc87e4b5ce2fe28308fd9f2a7baf3
41679091c5a880faf6fb5e6087eb1b2dc
xxxxxxxxxx
319
23
36
是的这是一道送分题。
tsawke 成功 hack 进了 neooj.com:8082/oldoj,但是他只获得了数据库中大量用户密码的 md5 形式,tsawke 需要获取这些用户的明文密码来勒索 llq,但是他不知道如何做,只能帮你进行 md5 的正向过程,靠你来实现 md5 的破解。
为了机房的未来,这道题一定要切呀!
我们得到了 llq 网站数据库中
Tips:此题时间复杂度可以通过一些优化而去掉一个
Tips:同时这道题也并不是一个优秀的交互题,因为此题并没有去可变地限制函数调用次数,当成练手题即可。
注意:你的程序禁止从标准输入读数据、向标准输出写数据或与任何文件交互。
你需要实现一个函数:
xxxxxxxxxx
11std::string HackLLQ(string md5);
这个函数的作用是,对于参数中的 md5,将其变为明文并返回。
你可以调用交互库中的以下函数:
xxxxxxxxxx
11std::string EncryptMD5(std::string plaintext);
这个函数将会返回字符串 plaintext
的 md5,你最多可以调用
令明文字符串长度为
对于
对于
若你的函数调用次数超限,则获得
若你的函数返回值错误,则 tsawke 将无法成功勒索 llq,获得
若你的函数全部正确,获得
对于前文提到的函数的声明,在这道题里即为:
xxxxxxxxxx
51extern std::string EncryptMD5(std::string);
2extern std::string HackLLQ(std::string);
3std::string HackLLQ(std::string md5){
4 //TODO
5}
关于交互库的源代码已下发到 Tsawke's Exam - Issue/hackllq_again/interactive_lib.cpp
。
注意,此交互库仅供测试样例使用,实际评测时的交互库此交互库不同。
Tips:这里的输入格式仅为本地调试时使用,与交互过程本身无关。
第一行输入一个整数
接下来
一共
Tips:对于本地调试时,即为你的程序计算出来的明文,可以和样例输出比对。
Tips:样例仅供本地调试使用,样例输入你都不必读取,样例输出你都不必输出。
xxxxxxxxxx
413
245c48cce2e2d7fbdea1afc51c7c6ad26
3eccbc87e4b5ce2fe28308fd9f2a7baf3
41679091c5a880faf6fb5e6087eb1b2dc
xxxxxxxxxx
319
23
36
在 JDFZ 的一楼半最深处的房间,明亮的灯光下却驱不散机房中 tsawke, sssmzy, zpair, cc0000 心中的黑暗...机房已经数年在 llq 的统治之下,OIer 们苦不堪言。
终于,在一个雷雨交加的夜晚,随着夜空被一道闪光划破,OIer 们决定奋起反抗 llq,誓要推翻 llq 的统治。
表面上,他们团结一心,众志成城,但每个人的心里却仍然暗流涌动...人人都有着野心,因为即使推翻了 llq 的统治,机房最终也只能由一人统治,显然 OIer 们都想当这个人,在共同对抗 llq 的同时,他们心中也在思考如何同时打败其他人...
在众人的努力下,llq 终于被打败了,但是 OIer 们之间的竞争才刚刚开始。
众所周知,人与人之间的天赋不能一概而论,OIer 们的各项属性将会由当天娱乐模拟赛的 T1-T3 的成绩决定。
llq 已经被打败了,现在为了获得更多的 pts,最终目标即为打败其他的 OIer。
我们定义当天的模拟赛中:
tsawke, sssmzy, zpair, cc0000 的分数百分比分别为
每一位 OIer 都会根据分数百分比获得一定的属性。(大模拟分数更高哦~)
共有如下几种属性:
我们会根据前三道题的得分,来决定每一帧 OIer 的操作顺序。
对于每位 OIer,每一帧里有如下几种操作:
"f"
:攻击面朝方向的所有敌人(默认面朝方向为上)。"w"
:向上移动 "a"
:向左移动 "s"
:向下移动 "d"
:向右移动 Tips:每秒会根据分数排名有一定概率固定扣除
注意:以下代码块函数名称中如果有 name 字段,您均需要将其改成您自己的名字!
我们目前支持的名字有:tsawke, sssmzy, zpair, cc0000。
请在其中选择您自己的名字并将 name 替换。
如对于:
xxxxxxxxxx
11pair < int, int > name_SetInitialPosition(void);
应该写成如下的形式:
xxxxxxxxxx
31pair < int, int > tsawke_SetInitialPosition(void){
2 return make_pair(1, 1);
3}
同时我们定义四个玩家 tsawke, sssmzy, zpair, cc0000 的序号分别为 1, 2, 3, 4。
我们为您提供了如下的 API,您需要在程序全局声明这些函数,也就是加上以下代码段:
xxxxxxxxxx
41
2
3
4extern GameStatus GetGameStatus(void);
以下是对这些函数作用的说明:
我们存在如下结构体:
xxxxxxxxxx
61struct GameStatus
2{
3 int height, width;
4 int mapStatus[::height + 1][::width + 1] = {};
5 Player player[5];
6};
height
和 width
记录了地图的高和宽,默认均为
mapStatus
记录了当前地图的状态,0为空地,1~4对应着对应玩家的位置,-1 对应着抵达该位置将会回复
player[i]
记录了玩家
xxxxxxxxxx
101class Player {
2public:
3 int HP;
4 int maxHP;
5 int attack;
6 int defence;
7 int posX, posY;
8 int towards;//1-up, 2-left, 3-down, 4-right
9 int rank;
10};
含义估计你们能看出来
Tips:
您可以通过调用如下函数以获取最新的游戏状态:
xxxxxxxxxx
11GameStatus GetGameStatus(void);
但是注意每帧您只能调用一次此函数,也就是仅每次执行您的 name_NextFrame
函数时可以调用一次该函数,我们并未对其进行限制,但请自觉遵守。
您需要实现如下的函数,以下是对这些函数的要求与说明:
xxxxxxxxxx
11pair < int, int > name_SetInitialPosition(void);
设置你最初在地图上的位置,返回一个 pair < int, int >
,表示位置在第 first 行 second 列。
注意:如果您返回的位置超出限制将会直接失败。
xxxxxxxxxx
11char name_NextFrame(void);
根据您获得的信息来决定这一帧里您将进行什么操作。
合法的返回值有 'w', 'a', 's', 'd', 'f', ' '
。
返回空格或其他值即意味着这一帧您将原地不动。
注意请不要在此函数中运算过长的时间!
注意:由于该题测评环境为 Visual Studio,不支持万能头文件,提交时请将万能头文件删去。