时间限制： 1.0 秒

空间限制： 512 MB

题目描述

给定一个 $n$ 个节点的完全二叉树，你需要实现函数 int lSize(int)，传入完全二叉树的节点规模，返回该二叉树的左子树节点规模。

交互方式

这是一道函数式交互题，不需要选手考虑输入输出，也不要从标准输入读入数据，或将任何内容输出到标准输出，否则会影响判题。

你提交的代码需要包含头文件 lsize.h。

你需要实现函数 int lSize(int)，传入完全二叉树的节点规模，返回该二叉树的左子树节点规模。

以下我们给出一个代码提交实例（固定返回 0，仅作为可以通过编译的示例，不保证能得分）：

#include "lsize.h"
int lSize(int n) { return 0; }

白盒交互库实例

具体请见附加文件区的 interactor.cc 和 lsize.h。本题直接采用白盒交互库进行评测。

如果你本地的实现代码为 main.cc，则将交互库放在同一目录下，在 Linux 系统中输入以下命令行即可运行：

g++ main.cc interactor.cc -Wall -std=c++20 -o foo -lm -O2 -I/include

在 Windows 下会生成 foo.exe，在 Linux 下会生成 foo，你可以输入 .\foo.exe 或者 ./foo 命令行执行该文件。或者将交互库接口与你实现的函数统一在单代码文件中进行本地调试即可。

白盒交互库先读入一个整数 $q$ 表示查询次数，接下来每行读入一个正整数表示一次完全二叉树的查询。对于每次查询，输出一行一个非负整数表示其左子树的规模。

5
1
2
3
4
5

0
1
1
2
3

子任务

对于所有数据，保证查询次数 $q\le 2\times 10^6$，查询的规模 $1\le n\le 10^9$。

本题无数据梯度，需要通过全部数据获得所有分数。

来源

清华 826 考研初试 2020 - 算法大题（1）