Int 2048
riteme.site

Int 2048

时间限制:$1 \mathrm{s}$
空间限制:$1024 \mathrm{MB}$

题目描述

这是一道交互题

注意本交互库不提供Pascal\C支持,只支持C++。

L语言之父Lunk最近声称用该语言编写计数问题不要取模,因为Lunk发明了$256 \mathrm{\ Byte}$int2048_t,并且已经内置到L语言中。

然而屁民们并不相信,因为Lunk的int2048_t还不支持Xntel公司的CSB指令 (Count Set Bits,计数被设置的位的数量),于是众人D之。Lunk为了挽回自己的脸面,决定实现一个CSB命令来教训一下这群智障。

CSB指令是一个这样的指令:它用于计数一个整型的二进制表示中的$1$的个数。例如下面的整型中:

$$01001101$$

其执行CSB的结果是$4$

Lunk不想再搞个新东西来支持这个垃圾玩意,他只准备利用现有的功能来实现它。目前int2048_t所支持的功能如下表所示:

符号 说明 示例 代价 实际复杂度
(constructor) 构造一个int2048_t int2048_t $0$ $\Theta(n)$
(constructor) 从一个字符串构造一个int2048_t int2048_t("110") $0$ $\Theta(n)$
+ 加法 0011 = 0010 + 0001 $1$ $\Theta(n)$
- 取负数 (计算其补码) 1111 = -0001 $1$ $\Theta(n)$
- 减法 (需要执行一个取负数和加法) 1101 = 1111 - 0010 $2$ $\Theta(n)$
~ 将各位取反 1010 = ~0101 $1$ $\Theta(n)$
& 按位与 0010 = 1011 & 0110 $1$ $\Theta(n)$
| 按位或 1111 = 1011 | 0110 $1$ $\Theta(n)$
^ 按位异或 1101 = 1011 ^ 0110 $1$ $\Theta(n)$
<< 左移 1100 = 1011 << 2 $1$ $O(n)$
>> 右移 0010 = 1011 >> 2 $1$ $O(n)$
== 判断是否相等 0010 == 0010 $1$ $\Theta(n)$
!= 判断是否不等 0010 != 1010 $1$ $\Theta(n)$
< 小于 0010 < 0100 $1$ $O(n)$
> 大于 0110 > 0100 $1$ $O(n)$
<= 小于等于 0100 <= 0100 $1$ $O(n)$
>= 大于等于 0010 >= 0010 $1$ $O(n)$
(bool) 转为bool类型 (如果为$0$则为$\mathrm{false}$,否则为$\mathrm{true}$) if (a) $1$ $O(n)$

在上表中,代价是智障们评定运行快慢的标准,实际复杂度是在实际运行 (即你的程序) 中的时间复杂度,其中$n$表示int2048_t的二进制位数,即$2048$

智障屁民们将会给出一堆的测试,如果Lunk的CSB指令写挂了,那么它们将会打$0$分。如果Lunk的CSB指令太慢,它们就又不高兴。于是Lunk请你帮他编写一个快速的CSB指令的实现。

实现

选手目录下将会下发int2048_t.hppint.h两个文件。

int2048_t.hpp是Lunk的int2048_t的实现,已经被int.h包含,选手不用自行包含。

选手需要实现一个evaluate函数,表示CSB指令。其函数原型如下:

1
int evaluate(const int2048_t &num);

当交互库运行时,会将测试数据通过num传入,而该函数的目的就是返回CSB指令在num上的结果。

样例交互库

选手目录下将会下发implementer.cpp这个文件。

假设你的实现的源文件是int.cpp,那么使用下面的编译命令来编译:

1
g++ int.cpp implementer.cpp -std=c++11 -o exec

然后将会得到可执行文件exec

输入格式

此处的输入格式值针对样例交互库而言的。

输入只有一行,表示测试的整形,以二进制形式给出。请确保输入不超过2048位,否则将导致不正常结果。

由于int2048_t是有符号整型,出于一些原因,最终测试数据的输入的最高位都是$0$

输出格式

此处的输出格式是针对样例交互库而言的。

样例交互库将会从输入得知答案,并将输入转为int2048_t,然后执行evaluate得到你的答案。如果两者答案一致,将会输出你所使用的代价总和。否则将输出Wrong answer,并给出正确答案和你的答案。

样例输入

1
01111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111

样例答案

1
2047

评分标准

此题共$10$个数据点,每个数据点$10$分。

对于每一个数据点而言,如果你的答案不正确,那么将记$0$分。
否则,记$a$为你的evaluate执行的代价总和,$v_{\min}$$v_{\max}$是每个数据点的特定的参数,那么你的得分将是:

$$ \left\lfloor \max\left\{ 10 \cdot\min\left\{ 1, \; { v_{\max} - a \over v_{\max} - v_{\min} } \right\}, \; 0 \right\} \right\rfloor $$

数据限制

对于每一个数据点,其限制如下表所示 (其中$x$表示答案):

数据点编号 $x$ $v_{\min}$ $v_{\max}$
$1$$2$$3$ $ \leqslant 400 $ $6140$ $6144$
$4$$5$$6$ $ \leqslant 200 $ $801$ $1201$
$7$$8$$9$$10$ $ \leqslant 2047 $ $76$ $120$

提示

一个整型的原码就是其二进制表示:

$$ 13 \rightarrow 00001101 $$

反码就是将除了符号位 (即最高位) 的所有取反:

$$ 00001101 \rightarrow 01110010 $$

对于负数,其符号位为$1$

$$ 01110010 \rightarrow 11110010 $$

二进制数的补码就是将其反码加上$1$,同时对于溢出的位直接丢弃,符号位也参与计算:

$$ -13 \rightarrow 11110011 \\ -0 \rightarrow 11111111 + 1 \rightarrow 100000000 \rightarrow 00000000 $$

因此采用补码存储负数,原码存储自然数,这样减法可以变为加法:

$$ 1 - 13 = 1 + (-13) \rightarrow 00000001 + 11110011 = 11110100 \rightarrow -12 $$

所以减法需要花费$2$的代价。