Public Judge

pjudge

Time Limit: 1 s Memory Limit: 512 MB Total points: 100 Interactive

#21626. 【PR #3】猜数

Statistics

这是一道交互题

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

然而,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 返回一个数 $a$ 时,Eve 会用这个伪随机数生成器生成一个数 $b$ ,并给 Bob 返回 $a\oplus b$(异或,即 c++ 里的 ^ )。

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

实现细节

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

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

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

你可以调用以下函数:

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

样例交互库

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

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

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

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

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

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

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

样例

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

0 1
998244353 3 332748118 3

以下是一次合法的交互过程。

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

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

数据范围与提示

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

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

  • 若 $Q_\text{max} < Q$,则你的得分为 $0$。
  • 若 $Q_\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 \leq Q_\text{min}$,则你的得分为 $S$。

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

对于所有数据, $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$ ,保证 $P$ 为质数。

子任务编号 $P\le $ 特殊限制 分值
$1$ $10^4$ $T=1$ $20$
$2$ $5\times 10^6$ $15$
$3$ $10^{9}$ $T\le 10$ $15$
$4$ $10^{18}$ $n=3$ $20$
$5$ $n=4$ $20$
$6$ $ $ $10$

时间限制:$\texttt{1s}$

空间限制:$\texttt{512MB}$