去年元夜时,花市灯如昼。月上柳梢头,人约黄昏后。
今年元夜时,月与灯依旧。不见去年人,泪湿春衫袖。
这是一道交互题。仅支持使用 C++ 语言(版本不低于 C++ 14)提交。
题目描述
在跳蚤王国的古老传说中,尘雨巷是一条被迷雾笼罩的环形秘巷。每当雨季来临,尘埃与水雾交织成帘,巷中的
尘雨巷是一个长度为
为了勘破巷子的长度
- 雨幕穿行(顺):顺时针移动到下一盏魔法灯面前,消耗
点体力; - 雨幕穿行(逆):逆时针移动到下一盏魔法灯面前,消耗
点体力; - 尘埃之窥:查询你面前的魔法灯的状态,消耗
点体力; - 雾中秘仪:改变你面前的魔法灯的状态(即将开启状态变为关闭状态,将关闭状态变为开启状态),不消耗体力。
由于你的时间有限,你必须在雨季结束前(至多使用
实现细节
选手不需要,也不应该实现 main
函数。
选手应确保提交的程序包含头文件 lane.h
,可在程序开头加入以下代码实现:
#include "lane.h"
选手需要实现以下函数:
int solve(int c);
表示伏特国王颁布的子任务编号;- 该函数需要返回
的值,表示巷子的长度 ; - 由于伏特国王可能要求你进行多次探险,因此对于每个测试点,该函数可能会被交互库调用多次。
选手可以通过调用以下函数向交互库发送一次魔法的使用:
void clockwise();
- 调用该函数表示使用魔法“雨幕穿行(顺)”:消耗
点体力,顺时针移动到下一盏魔法灯面前。
void anticlockwise();
- 调用该函数表示使用魔法“雨幕穿行(逆)”:消耗
点体力,逆时针移动到下一盏魔法灯面前。
bool ask();
- 调用该函数表示使用魔法“尘埃之窥”:消耗
点体力,查询你面前的魔法灯的状态; - 该函数会返回一个
bool
类型的值:若魔法灯是开启状态,则返回true
,否则返回false
。
void flip();
- 调用该函数表示使用魔法“雾中秘仪”:不消耗体力,改变你面前的魔法灯的状态(即将开启状态变为关闭状态,将关闭状态变为开启状态)。
测试程序方式
试题目录下的 grader.cpp
是提供的交互库参考实现,最终测试所用的交互库与该参考实现有所不同,因此选手的解法不应该依赖交互库实现。
最终的评测交互库与样例交互库的实现不同,且可能是适应性的:在不与 ask
此前返回的结果相矛盾的前提下,最终的评测交互库可能会动态调整
选手可以在本题目录下使用如下命令编译得到可执行程序:
g++ grader.cpp lane.cpp -o lane -O2 -std=c++14 -static
你也可以添加 -DDEBUG
选项来开启调试模式,此时编译命令如下:
g++ grader.cpp lane.cpp -o lane -O2 -std=c++14 -static -DDEBUG
对于编译得到的可执行程序:
- 可执行文件将从标准输入读入以下格式的数据:
- 输入的第一行包含两个整数
,表示子任务编号和探险次数; - 对于每组数据包含两行:
- 第一行包含一个正整数
; - 第二行包含一个由
个字符组成的字符串,每个字符都是0
或者1
,表示从初始位置开始,开关的初始状态(0
表示关闭,1
表示开启)按照顺时针排列得到的数组。
- 第一行包含一个正整数
- 输入的第一行包含两个整数
- 对于每组数据,交互库将调用一次函数
solve
进行测试,测试全部完成后,交互库将会输出以下信息:- 第一行包含你的得分信息;
- 第二行包含交互库关于测试结果给出的描述;
- 如果开启了调试模式,交互库会向标准错误流打印每一组数据以及每一次操作的详细信息。请确保开启调试模式时输入的测试数据较小从而避免意外产生。
交互示例
假设
选手程序 | 交互库 | 说明 |
---|---|---|
调用 solve(2) |
开始探险 | 该次探险属于子任务 |
调用 ask() |
返回 |
当前位于初始状态中的第 |
调用 clockwise() |
无返回值 | 顺时针移动一个位置,到初始状态中的第 |
调用 ask() |
返回 |
当前位于初始状态中的第 |
调用 clockwise() |
无返回值 | 顺时针移动一个位置,回到初始状态中的第 |
调用 ask() |
返回 |
当前位于初始状态中的第 |
调用 flip() |
无返回值 | 改变当前位置的魔法灯的状态,开关状态变为 |
调用 anticlockwise() |
无返回值 | 逆时针移动一个位置,到初始状态中的第 |
调用 anticlockwise() |
无返回值 | 逆时针移动一个位置,到初始状态中的第 |
调用 ask() |
返回 |
当前位于初始状态中的第 |
运行结束并返回 |
向屏幕打印交互结果 | 交互结束,结果正确;共使用 |
题目附件说明
本题附件中包含:
grader.cpp
是提供的交互库参考实现。lane.h
是头文件,选手不用关心具体内容。template_lane.cpp
是提供的示例代码,选手可在此代码的基础上实现。lane1.in
、lane2.in
和lane3.in
是大样例,分别对应三个子任务。
子任务
记总探险次数,即函数 solve
的总调用次数为
伏特国王共颁布了
- 初探尘雨(子任务 1,
分):- 保证
; - 保证初始状态下所有魔法灯均为关闭状态;
- 只要对于单个测试点的每次探险,选手程序都使用不超过
次魔法,正确确定巷子的长度 ,就可以得到满分;否则不得分。
- 保证
- 雾锁千巷(子任务 2,
分):- 保证
, ; - 对于单个测试点的每次探险,选手程序至多使用
次魔法,否则不得分; - 对于单个测试点,设在
次探险中, 表示消耗的体力点数 与巷子的长度 的比值 的最大值,则选手程序在该测试点的得分:- 若
,则得到 分(满分); - 若
,则得到 分; - 若
,则得到 分。
- 若
- 保证
- 终勘轮回(子任务 3,
分):- 无特殊限制;
- 对于单个测试点的每次探险,选手程序至多使用
次魔法,否则不得分; - 若一次探险设消耗的体力点数为
,巷子的长度 ,那么伏特对这次探险的满意度为:- 若
,则满意度等于 - 若
,则满意度等于
- 若
- 对于单个测试点,设
表示在 次探险中伏特的满意度的最大值,则选手程序在该测试点的得分:- 若
,则得到 分(满分); - 若
,则得到 分; - 若
,则得到 分。
- 若
一个子任务的得分为其中所有测试点得分的最小值,得分向下取整保留两位小数。
题目保证在规定的魔法使用次数限制下,交互库运行所需的时间不超过
提示
注意:
- 选手不应通过非法方式获取交互库的内部信息,如试图直接读取魔法灯的状态,或直接与标准输入、输出流进行交互。此类行为将被视为作弊;
- 最终的评测交互库与样例交互库的实现不同,且可能是适应性的:在不与
ask
此前返回的结果相矛盾的前提下,最终的评测交互库可能会动态调整 的值和魔法灯的状态。
本题首先会受到和传统相同的限制,例如编译错误会导致整道题目得
时间限制:
空间限制: