UOJ Logo Universal Online Judge

UOJ

#166. 【清华集训2015】King

附件下载 统计

这是一道交互题

跳蚤国王正在带领着四万万跳蚤造计算机。

我们给每只跳蚤一个从 $0$ 开始的整数编号。

由于跳蚤国的文明比较落后,每只跳蚤只能存储一个 $0$ 或 $1$ 的值,对于第 $i$ 只跳蚤这个值记为 $v_i$。

对于所有编号小于 $2n$ 的跳蚤,它们的值由跳蚤国王决定。即,这 $2n$ 个值可以看作是输入。

我们记 \begin{equation} F(a,b,f) = \left \lfloor \frac{f}{2 ^ {2 a + b}} \right \rfloor \mod 2 \end{equation}

对于编号大于等于 $2n$ 的每只跳蚤,设它的编号为 $i$ , 你需要给它指定三个参数 $a_i, b_i, f_i$ ($0 \le a_i < i, 0 \le b_i < i, 0 \le f_i < 16$),则 \begin{equation} v_i = F \left ( v_{a_i}, v_{b_i}, f_i \right ) = \left \lfloor \frac{f_i}{2 ^ {2 v_{a_i} + v_{b_i} }} \right \rfloor \mod 2 \end{equation} 我们称第 $i$ 只跳蚤依赖于第 $a_i$ 和第 $b_i$ 只跳蚤(注意$a_i$可以等于$b_i$)。

下面给出了几个关于 $F$ 的例子:

$a$$b$$F(a,b,14)$$F(a,b,8)$$F(a,b,6)$
$0$$0$$0$$0$$0$
$0$$1$$1$$0$$1$
$1$$0$$1$$0$$1$
$1$$1$$1$$1$$0$

一开始(第 $0$ 时刻),所有编号小于 $2n$ 的跳蚤的值都同时被确定。 然后对于每只编号大于等于 $2n$ 的跳蚤, 它的值将在它依赖的跳蚤的值都确定之后立即开始确定。 由于跳蚤国的信息技术不发达, 每只跳蚤确定它的值需要1小时(注意多只跳蚤可以同时确定它们的值)。

下面是一个例子:(id表示编号,t表示该跳蚤的值被确定的时间,箭头表示跳蚤的依赖关系)

例子

我们可以把编号小于 $2n$ 的跳蚤的值看作两个 $n$ 位的二进制数 $\mathrm{A}, \mathrm{B}$, 其中 $\mathrm{A} = (v_{n-1} \ v_{n-2} \ \cdots \ v_0)_2$, $\mathrm{B} = (v_{2n-1} \ v_{2n-2} \ \cdots \ v_{n})_2$。 跳蚤国王要对 $\mathrm{A}$ 和 $\mathrm{B}$ 做一些运算,得到一个 $n$ 位二进制数, 并用 $n$ 只跳蚤表示出来。

由于跳蚤国王还要带着跳蚤们去舞会,你能使用的跳蚤的数量和时间都有限。 具体来说,你最多使用 $\mathrm{M}$ 只跳蚤,并要求按顺序指定 $n$ 只跳蚤, 在 $\mathrm{T}$ 小时内,你使用的所有跳蚤的值都能被确定, 且指定的 $n$ 只跳蚤的值表示的二进制数为跳蚤国王所求的答案。

作为奖励,跳蚤国王打算送你一个UOJ抱枕。 第一个通过最后一个测试点的选手将获得一个UOJ抱枕。 如果没有选手通过最后一个测试点,则第一个得到此题最高分的选手将获得一个UOJ抱枕。

任务

你需要编写一个函数 build_computer,来帮助跳蚤国王造计算机。

  • build_computer(task_id, n, M, T)
    • task_id: 子任务编号
    • n: 输入的$\mathrm{A}$和$\mathrm{B}$的位数
    • M: 除了编号小于$2n$的跳蚤之外,最多能使用的跳蚤的数目
    • T: 你使用的所有跳蚤的值都要在$\mathrm{T}$小时内被确定

你可以调用一个函数 add_flea(a, b, f), 表示增加一只跳蚤,对于第 $i$ 次调用, 增加的跳蚤的编号为$2n + i - 1$, $a_{2n+i-1}, b_{2n+i-1}, f_{2n+i-1}$分别被设置为$a, b, f$, 然后这个函数会返回$2n + i - 1$。 你最多能调用$\mathrm{M}$次 add_flea

你还需要对每个 $[0, n-1]$ 中的整数 $i$ 调用 set_output 函数(可以按任意顺序调用)。 set_output(i, id) 表示设置输出的二进制数的第 $i$ 位为编号为 $id$ 的跳蚤的值。

子任务

子任务编号需要计算的表达式
1 $(\mathrm{A} + 1) \mod 2 ^ n$
2 $(\mathrm{A} + \mathrm{B}) \mod 2 ^ n$
3 $(\mathrm{A} \times \mathrm{B}) \mod 2 ^ n$

设 $m$ 为 add_flea 的调用次数,$t$ 为所有跳蚤的值被确定的最晚时刻。

测试点编号子任务编号分值$n$$\mathrm{M}$$\mathrm{T}$备注
1 11 $1$ $10000$ $10000$
2 12 $2$ $10000$ $10000$
3 15 $256$ $10000$ $10000$
4 19 $10^5$ $5 \times 10^5$ $50$ 该测试点得分为$\min \left \{ \left \lfloor \frac{5 \times 10^5 - m}{20000} \right \rfloor, 9 \right \}$分
5 110 $10^5$ $1.5 \times 10^6$ $30$ 该测试点得分为$\min \left \{30-t, 10 \right \}$分
6 23 $2$ $10000$ $10000$
7 26 $233$ $10000$ $10000$
8 213$10^5$ $1.2 \times 10^6$ $100$ 该测试点得分为$\min \left \{ \left \lfloor \frac{1.2 \times 10^6-m}{30000} \right \rfloor, 13 \right \}$分
9 214$10^5$ $5 \times 10^6$ $42$该测试点得分为$\min \left \{42-t, 14 \right \}$分
1034 $2$ $10000$ $10000$
1137 $233$ $10^6$ $10^6$
1238 $512$ $3 \times 10^6$ $255$
13317 $1024$ $4 \times 10^6$ $94$ 该测试点得分为$\min \left \{ \left \lfloor\frac{94-t}{2} \right \rfloor, 17 \right \}$分
1431 $1024$ $1920000$ $288$ 第一个通过该测试点的选手将获得一个UOJ抱枕!

实现细节

本题只支持C++。

你只能提交一个源文件实现如上所述的 build_computer 函数,并且遵循下面的命名和接口。

你需要包含头文件 king.h

void build_computer(int task_id, int n, int M, int T);

函数 add_fleaset_output 的接口信息如下。

int add_flea(int a, int b, int f);
void set_output(int i, int id);

评测方式

评测系统将读入如下格式的数据:

  1. 第1行:子任务编号
  2. 第2行:$n, \mathrm{M}, \mathrm{T}$

如果你调用 add_flea 的次数大于 $\mathrm{M}$, 或调用 set_output的次数不等于 $n$, 或没有对 $[0, n-1]$ 中的每个整数作为 set_output 的第一个参数调用 set_output, 你的程序将被判为“Incorrect”。

build_computer 返回后,如果在 $\mathrm{T}$ 小时后,存在一只跳蚤的值还没被确定,则评测系统输出“Incorrect”, 否则我们将用若干组输入对你造的计算机进行测试, 如果对于所有输入数据,你的输出都正确,评测系统将输出“Correct”,否则输出“Incorrect”。

如果评测系统第一行输出了“Correct”,则第二行将会输出 $m$ 和 $t$(定义见“子任务”),否则会输出具体的错误信息。

交互式类型的题目怎么本地测试

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

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

在任何时候,交互库使用的内存都不会超过$128\texttt{MB}$,即选手至少有$384\texttt{MB}$的可用内存。

下载

样例及测评库下载