#P9692. Number Guessing

    ID: 6314 交互题 1000ms 512MiB 尝试: 2 已通过: 1 难度: 9 上传者: 标签>难度分类省选/NOI-模拟与实现技巧进位制转换数论同余的加减乘运算排序与序列处理二分查找位运算异或抵消交互与信息策略自适应查询二分交互CF2600杂项交互题

Number Guessing

Source: Petrozavodsk Winter 2022, Day 6. ICPC Camp Day 1, PKU Contest, Problem E.

本题是交互题。

本平台采用下文给出的函数接口及询问范围,与原题存在差别:

  • 原题额外要求 1≤x≤10181\le x\le 10^{18}。

题目描述

这是一道交互题,注意本题交互格式与原题不同。

Alice 有一个 [1,1018][1,10^{18}] 的整数 yy ,而 Bob 想要求出这个数,所以 Bob 每次会选一个 [0,1018][0,10^{18}] 的整数 xx 向 Alice 提问。如果 y>xy>x 则 Alice 返回 22 ,如果 y=xy=x 则 Alice 返回 11 ,如果 y<xy<x 则 Alice 返回 00。

然而,Alice 和 Bob 的通信被 Eve 截获了。Eve 写了一个伪随机数生成器:

const long long P=998244353; // 不一定是这个数。
const int n=3; // 也不一定是这个数。
long long seed=233; // 更不一定是这个数。
int gen()
{
    seed=seed*n%P;
    return seed%n;
}

每次 Alice 返回一个数 aa 时,Eve 会用这个伪随机数生成器生成一个数 bb ,并给 Bob 返回 a⊕ba\oplus b(异或,即 c++ 里的 ^ )。

你是 Bob ,并且你用一些操作得到了 P\texttt P 和 n\texttt n ,但是你不知道 seed\texttt{seed} 。你需要在 100 次询问内得到 yy。

实现细节

你不需要,也不应该实现 main() 函数,或在任何文件与标准输入/输出流中读入或输出任何信息。

你只需要包含头文件 guess.h,并实现以下函数:

void init(int subtask_id,int T);
long long solve(long long P,int n);
  • init 函数会被恰好调用 11 次。
    • 参数 subtask_id 表示当前测试点编号,参数 T 表示当前测试点有几组数据。
  • solve 函数会被调用 TT 次。
    • 参数 n 和参数 P 即为 Eve 的伪随机生成器的参数。你需要返回 Alice 的数 yy 。

你可以调用以下函数:

int query(long long x);
  • 参数 x 表示 Bob 向 Alice 提问的数。
  • 你需要保证 0≤x≤10180\le x\le 10^{18}。
  • 返回值已经被 Eve 修改过了。

样例交互库

在下发文件中,你可以找到样例交互库 grader.cpp ,你可以通过交互库的实现来帮助你理解并实现这道题目。需要注意的是,在进行最终测试时,交互库的实现与样例交互库有所不同,因此你不应当依赖此交互库的实现。

样例交互库将通过以下格式在标准输入中读入数据:

  • 第一行,两个正整数 subtask_id\texttt{subtask\_id} 和 T\texttt T。
  • 接下来 TT 行,每行四个整数 P,n,seed,y\texttt P,\texttt n,\texttt{seed},y ,表示一组测试。

交互过程中,如果出现任何错误,交互库会直接输出错误信息并退出。否则,交互库会在最后输出询问次数的最大值。

你可以在终端使用以下命令来编译你的程序:

g++ grader.cpp guess.cpp -o guess.exe -O2

在最终评测时,对于任何合法的(使用不超过 QmaxQ_\text{max} 次询问操作)交互过程,保证交互库使用的时间不超过 0.10.1 秒,使用的内存不超过 2MB2\texttt{MB}。

样例

以下是一组可能的对样例交互库的输入。

0 1
998244353 3 332748118 3
交互库调用 选手程序调用 返回值
init(0,1)
solve(998244353,3)
query(4) 11
query(2) 22
query(3) 11
33

在这次交互过程中,选手程序猜到了 seed\texttt{seed} ,从而只有第一次的返回值需要异或 11。

数据范围与提示

如果你在某个测试点中没有在时间限制与空间限制内返回结果,或发生了运行时错误,或最终返回的答案不正确,则你在该测试点的得分为 00。

否则,设 QQ 为你在该测试点中调用函数 query 的次数,SS 为该测试点的满分,则:

  • 若 Qmax<QQ_\text{max} < Q,则你的得分为 00。
  • 若 Qmin<Q≤QmaxQ_\text{min} < Q \leq Q_\text{max},则你的得分为 $S \cdot \left( 1 - 0.7 \cdot \dfrac{Q - Q_\text{min}}{Q_\text{max} - Q_\text{min}} \right)$。
  • 若 Q≤QminQ \leq Q_\text{min},则你的得分为 SS。

在一个子任务中,你所得到的分数即为所有测试点分数的最小值。

对于所有数据, $10^3\le P\le 10^{18},3\le n\le 4,0\le \texttt{seed}<P,T\le 100,Q_{\min}=100,Q_\text{max}=200$ ,保证 PP 为质数。

子任务 P≤P\le 特殊限制 分值
11 10410^4 T=1T=1 2020
22 5×1065\times 10^6 1515
33 10910^9 T≤10T\le 10
44 101810^{18} n=3n=3 2020
55 n=4n=4
66 1010

@下发文件

Hydro 平台评测说明

本平台按真实函数交互评测:只包含 guess.h,实现 init 和 solve,不写 main。平台自动联编 grader.cpp;它只向选手提供 subtask_id、T、P、n,隐藏的 seed、y 由独立交互器保管。query 函数通过交互器获取真实响应,最终返回值也由交互器核验,不能通过自行输出询问次数冒充通过。每组超过200次询问立即判错;100次内满分,101..200次按原公式部分得分。

原下发文件中的单机样例交互库及输入格式保留,适用于在本地与函数代码联编测试;上述 Hydro grader.cpp 使用的是平台通信协议。