UOJ Logo Universal Online Judge

UOJ

#980. 【UR #31】决战尘雨巷

附件下载 统计

English Problem Statement

去年元夜时,花市灯如昼。月上柳梢头,人约黄昏后。

今年元夜时,月与灯依旧。不见去年人,泪湿春衫袖。

这是一道交互题。仅支持使用 C++ 语言(版本不低于 C++ 14)提交。

题目描述

在跳蚤王国的古老传说中,尘雨巷是一条被迷雾笼罩的环形秘巷。每当雨季来临,尘埃与水雾交织成帘,巷中的 n 盏魔法灯若隐若现。作为伏特国王最信任的探险家,你被传送至某盏魔法灯前——你既不知道巷子的长度 n,也不知道初始位置和魔法灯的状态。雨季结束前,你必须完成伏特给你的任务——勘破巷子的长度 n

尘雨巷是一个长度为 n环形巷子。这个巷子中排列着 n 盏魔法灯,每盏魔法灯可能为开启状态或关闭状态。一开始,你被传送到其中一盏魔法灯面前,但是你并不知道你的面前是哪一盏魔法灯,也不知道每个魔法灯目前的状态。

为了勘破巷子的长度 n,你可以使用若干次魔法,每次魔法是下面的四种之一:

  • 雨幕穿行(顺):顺时针移动到下一盏魔法灯面前,消耗 1 点体力;
  • 雨幕穿行(逆):逆时针移动到下一盏魔法灯面前,消耗 1 点体力;
  • 尘埃之窥:查询你面前的魔法灯的状态,消耗 1 点体力;
  • 雾中秘仪:改变你面前的魔法灯的状态(即将开启状态变为关闭状态,将关闭状态变为开启状态),不消耗体力

由于你的时间有限,你必须在雨季结束前(至多使用 2×106 次魔法)求出巷子的长度 n。此外,伏特国王还将根据你花费的体力点数多少授予不同的奖赏,具体见“子任务”部分。

实现细节

选手不需要,也不应该实现 main 函数。

选手应确保提交的程序包含头文件 lane.h,可在程序开头加入以下代码实现:

#include "lane.h"

选手需要实现以下函数:

int solve(int c);
  • c 表示伏特国王颁布的子任务编号;
  • 该函数需要返回 n 的值,表示巷子的长度 n
  • 由于伏特国王可能要求你进行多次探险,因此对于每个测试点,该函数可能会被交互库调用多次

选手可以通过调用以下函数向交互库发送一次魔法的使用:

void clockwise();
  • 调用该函数表示使用魔法“雨幕穿行(顺)”:消耗 1 点体力,顺时针移动到下一盏魔法灯面前。
void anticlockwise();
  • 调用该函数表示使用魔法“雨幕穿行(逆)”:消耗 1 点体力,逆时针移动到下一盏魔法灯面前。
bool ask();
  • 调用该函数表示使用魔法“尘埃之窥”:消耗 1 点体力,查询你面前的魔法灯的状态;
  • 该函数会返回一个 bool 类型的值:若魔法灯是开启状态,则返回 true,否则返回 false
void flip();
  • 调用该函数表示使用魔法“雾中秘仪”:不消耗体力,改变你面前的魔法灯的状态(即将开启状态变为关闭状态,将关闭状态变为开启状态)。

测试程序方式

试题目录下的 grader.cpp 是提供的交互库参考实现,最终测试所用的交互库与该参考实现有所不同,因此选手的解法不应该依赖交互库实现。

最终的评测交互库与样例交互库的实现不同,且可能是适应性的:在不与 ask 此前返回的结果相矛盾的前提下,最终的评测交互库可能会动态调整 n 的值和魔法灯的状态。

选手可以在本题目录下使用如下命令编译得到可执行程序:

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

对于编译得到的可执行程序:

  • 可执行文件将从标准输入读入以下格式的数据:
    • 输入的第一行包含两个整数 c,T,表示子任务编号和探险次数;
    • 对于每组数据包含两行:
      • 第一行包含一个正整数 n
      • 第二行包含一个由 n 个字符组成的字符串,每个字符都是 0 或者 1,表示从初始位置开始,开关的初始状态(0 表示关闭,1 表示开启)按照顺时针排列得到的数组。
  • 对于每组数据,交互库将调用一次函数 solve 进行测试,测试全部完成后,交互库将会输出以下信息:
    • 第一行包含你的得分信息;
    • 第二行包含交互库关于测试结果给出的描述;
  • 如果开启了调试模式,交互库会向标准错误流打印每一组数据以及每一次操作的详细信息。请确保开启调试模式时输入的测试数据较小从而避免意外产生

交互示例

假设 n=2,开关的初始状态为 [0,1],下面是一个合法的交互过程:

选手程序 交互库 说明
调用 solve(2) 开始探险 该次探险属于子任务 2
调用 ask() 返回 0 当前位于初始状态中的第 1 个位置,魔法灯处于关闭状态;消耗 1 点体力
调用 clockwise() 无返回值 顺时针移动一个位置,到初始状态中的第 2 个位置;消耗 1 点体力
调用 ask() 返回 1 当前位于初始状态中的第 2 个位置,魔法灯处于开启状态;消耗 1 点体力
调用 clockwise() 无返回值 顺时针移动一个位置,回到初始状态中的第 1 个位置;消耗 1 点体力
调用 ask() 返回 0 当前位于初始状态中的第 1 个位置,魔法灯处于开启状态;消耗 1 点体力
调用 flip() 无返回值 改变当前位置的魔法灯的状态,开关状态变为 [1,1]
调用 anticlockwise() 无返回值 逆时针移动一个位置,到初始状态中的第 2 个位置;消耗 1 点体力
调用 anticlockwise() 无返回值 逆时针移动一个位置,到初始状态中的第 1 个位置;消耗 1 点体力
调用 ask() 返回 1 当前位于初始状态中的第 1 个位置,魔法灯处于开启状态;消耗 1 点体力
运行结束并返回 2 向屏幕打印交互结果 交互结束,结果正确;共使用 9 次魔法,消耗 8 点体力

题目附件说明

本题附件中包含:

  1. grader.cpp 是提供的交互库参考实现。
  2. lane.h 是头文件,选手不用关心具体内容。
  3. template_lane.cpp 是提供的示例代码,选手可在此代码的基础上实现。
  4. lane1.inlane2.inlane3.in 是大样例,分别对应三个子任务。

子任务

记总探险次数,即函数 solve 的总调用次数为 T;每次探险的巷子长度 n 的总和为 n。对于所有测试数据保证:1n1051T106n107

伏特国王共颁布了 3 个子任务:

  • 初探尘雨(子任务 1,3 分):
    • 保证 T10
    • 保证初始状态下所有魔法灯均为关闭状态;
    • 只要对于单个测试点的每次探险,选手程序都使用不超过 2×106 次魔法,正确确定巷子的长度 n,就可以得到满分;否则不得分。
  • 雾锁千巷(子任务 2,40 分):
    • 保证 n2×103T5×103
    • 对于单个测试点的每次探险,选手程序至多使用 20n 次魔法,否则不得分;
    • 对于单个测试点,设在 T 次探险中,x 表示消耗的体力点数 q 与巷子的长度 n 的比值 qn 的最大值,则选手程序在该测试点的得分:
      • x7.83,则得到 40 分(满分);
      • x>15,则得到 0 分;
      • 7.83<x15,则得到 40×15x157.83 分。
  • 终勘轮回(子任务 3,57 分):
    • 无特殊限制;
    • 对于单个测试点的每次探险,选手程序至多使用 20n 次魔法,否则不得分;
    • 若一次探险设消耗的体力点数为 q,巷子的长度 n,那么伏特对这次探险的满意度为:
      • n2×103,则满意度等于 q2n
      • n>2×103,则满意度等于 qn
    • 对于单个测试点,设 x 表示在 T 次探险中伏特的满意度的最大值,则选手程序在该测试点的得分:
      • x5.35,则得到 57 分(满分);
      • x>8,则得到 0 分;
      • 5.35<x8,则得到 57×8x85.35 分。

一个子任务的得分为其中所有测试点得分的最小值,得分向下取整保留两位小数。

题目保证在规定的魔法使用次数限制下,交互库运行所需的时间不超过 3s;交互库使用的内存大小固定,且不超过 64MB

提示

注意:

  • 选手不应通过非法方式获取交互库的内部信息,如试图直接读取魔法灯的状态,或直接与标准输入、输出流进行交互。此类行为将被视为作弊;
  • 最终的评测交互库与样例交互库的实现不同,且可能是适应性的:在不与 ask 此前返回的结果相矛盾的前提下,最终的评测交互库可能会动态调整 n 的值和魔法灯的状态。

本题首先会受到和传统相同的限制,例如编译错误会导致整道题目得 0 分,运行时错误、超过时间限制、超过空间限制都会导致相应测试点得 0 分。选手只能在程序中访问自己定义的和交互库给出的变量或数据,及其相应的内存空间。尝试访问其他位置空间将可能导致编译错误或运行错误。

时间限制: 5s(交互库至多使用 3s

空间限制: 512MB(交互库至多使用 64MB