UOJ Logo Universal Online Judge

UOJ

#66. 新年的巧克力棒

统计

马上就要到羊年了,羊村一片欢腾,懒羊羊则懒洋洋地躺在草坪上吃新年的巧克力棒。

他手上的巧克力棒是个由 $n$ 个巧克力单元格组成的长度为 $n$ 的长条,现在懒羊羊想把巧克力棒掰开成一个个小单元格。

初始时懒羊羊会把这根巧克力棒丢在草坪上,然后每次懒羊羊会从草坪上拿起一根长度大于 $1$ 的巧克力棒,然后从某两个相邻的单元格的间隙处掰开变成两根巧克力棒,然后把这两根巧克力棒丢在草坪上。懒羊羊初始愉悦值为 $0$,每次掰开巧克力棒后如果这两根巧克力棒长度相等,那么懒羊羊将提升 $1$ 点愉悦值。

当然,草坪上全是长度为 $1$ 的巧克力棒时懒羊羊就会停止操作。现在懒羊羊想知道,他能获得的愉悦值最多是多少?

输入格式

一行一个正整数 $T$。

接下来 $T$ 行,每行一个正整数 $n$ 表示巧克力棒的长度,你需要对每个给出的 $n$ 计算最多能获得的愉悦值。

输出格式

$T$ 行每行一个整数,表示懒羊羊最多能获得的愉悦值。

样例一

input

5
1
3
4
7
233333333

output

0
1
3
4
233333319

explanation

对于 $n = 1$,初始时草坪上已经全是长度为 $1$ 的了,所以愉悦值为 $0$。

对于 $n = 3$,懒羊羊可以先把它掰开变成一根长度为 $1$ 的和一根长度为 $2$ 的巧克力棒;然后再把长度为 $2$ 的巧克力棒从正中间掰开获得 $1$ 点愉悦值,所以答案是 $1$。

对于 $n = 4$,懒羊羊可以先从正中间掰开变成两根长度为 $2$ 的巧克力棒,获得 $1$ 点愉悦值;然后再对于每根长度为 $2$ 的巧克力棒从正中间掰开各获得 $1$ 点愉悦值,所以答案是 $3$。

限制与约定

对于所有数据,$T \leq 20$。

测试点编号 $n$ 的规模
1$n \leq 5$
2$n \leq 20$
3$n \leq 1000$
4
5
6$n \leq 10^9$
7
8
9
10

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

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

来源

UOJ Goodbye Jiawu

下载

样例数据下载