Int 2048
时间限制:
空间限制:
题目描述
这是一道交互题。
注意本交互库不提供Pascal\C支持,只支持C++。
L语言之父Lunk最近声称用该语言编写计数问题不要取模,因为Lunk发明了int2048_t
,并且已经内置到L语言中。
然而屁民们并不相信,因为Lunk的int2048_t
还不支持Xntel公司的CSB
指令 (Count Set Bits,计数被设置的位的数量),于是众人D之。Lunk为了挽回自己的脸面,决定实现一个CSB
命令来教训一下这群智障。
CSB
指令是一个这样的指令:它用于计数一个整型的二进制表示中的
其执行CSB
的结果是
Lunk不想再搞个新东西来支持这个垃圾玩意,他只准备利用现有的功能来实现它。目前int2048_t
所支持的功能如下表所示:
符号 | 说明 | 示例 | 代价 | 实际复杂度 |
---|---|---|---|---|
(constructor) | 构造一个int2048_t | int2048_t | ||
(constructor) | 从一个字符串构造一个int2048_t | int2048_t("110") | ||
+ | 加法 | 0011 = 0010 + 0001 | ||
- | 取负数 (计算其补码) | 1111 = -0001 | ||
- | 减法 (需要执行一个取负数和加法) | 1101 = 1111 - 0010 | ||
~ | 将各位取反 | 1010 = ~0101 | ||
& | 按位与 | 0010 = 1011 & 0110 | ||
| | 按位或 | 1111 = 1011 | 0110 | ||
^ | 按位异或 | 1101 = 1011 ^ 0110 | ||
<< | 左移 | 1100 = 1011 << 2 | ||
>> | 右移 | 0010 = 1011 >> 2 | ||
== | 判断是否相等 | 0010 == 0010 | ||
!= | 判断是否不等 | 0010 != 1010 | ||
< | 小于 | 0010 < 0100 | ||
> | 大于 | 0110 > 0100 | ||
<= | 小于等于 | 0100 <= 0100 | ||
>= | 大于等于 | 0010 >= 0010 | ||
(bool) | 转为bool 类型 (如果为 | if (a) |
在上表中,代价是智障们评定运行快慢的标准,实际复杂度是在实际运行 (即你的程序) 中的时间复杂度,其中int2048_t
的二进制位数,即
智障屁民们将会给出一堆的测试,如果Lunk的CSB
指令写挂了,那么它们将会打CSB
指令太慢,它们就又不高兴。于是Lunk请你帮他编写一个快速的CSB
指令的实现。
实现
选手目录下将会下发int2048_t.hpp
和int.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
是有符号整型,出于一些原因,最终测试数据的输入的最高位都是
输出格式
此处的输出格式是针对样例交互库而言的。
样例交互库将会从输入得知答案,并将输入转为int2048_t
,然后执行evaluate
得到你的答案。如果两者答案一致,将会输出你所使用的代价总和。否则将输出Wrong answer
,并给出正确答案和你的答案。
样例输入
1 | 01111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111 |
样例答案
1 | 2047 |
评分标准
此题共
对于每一个数据点而言,如果你的答案不正确,那么将记
否则,记evaluate
执行的代价总和,
数据限制
对于每一个数据点,其限制如下表所示 (其中
数据点编号 | |||
---|---|---|---|
提示
一个整型的原码就是其二进制表示:
其反码就是将除了符号位 (即最高位) 的所有取反:
对于负数,其符号位为
二进制数的补码就是将其反码加上
因此采用补码存储负数,原码存储自然数,这样减法可以变为加法:
所以减法需要花费