QYcode QYcode

CF2111A.Energy Crystals

传统题 时间 2000 ms 内存 256 MiB 3 尝试 1 已通过 1 标签

Energy Crystals

English 简体中文

题目描述

有三个编号为 1,2,31,2,3 的能量水晶，第 ii 个水晶的能量等级记为 aia_i。初始时，所有水晶都为未充能，即能量等级均为 00。每个水晶需充能至 xx 级（恰好为 xx，不能超过）。

每次操作中，你可以将任意一个水晶的能量等级增加任意正数值；然而，能量水晶之间是同步的，因此每次操作后必须满足以下条件：

  • 对于任意一对晶体 ii 和 jj，必须满足 ai≥⌊aj2⌋a_i\ge\lfloor\frac{a_j}{2}\rfloor。

问：将所有水晶充能至 xx 级所需的最少操作次数是多少？

输入格式

每个测试包含多个测试用例。

第一行包含一个整数 t (1≤t≤104)t\ (1\le t\le 10^4)——测试用例的数量。接下来是每个测试用例的描述。

每个测试用例仅包含一行，一个整数 x (1≤x≤109)x\ (1\le x\le 10^9)。

输出格式

对于每个测试用例，输出一个整数——将所有能量晶体充能至 xx 级所需的最少操作次数。

说明/提示

在第一个测试用例中，一种可能的操作序列是：

$$[0,0,0]\to[{\color{red}1},0,0]\to[1,0,{\color{red}1}]\to[1,{\color{red}1},1]$$

在第二个测试用例中，一种可能的操作序列是：

$$[0,0,0]\to[{\color{red}1},0,0]\to[1,{\color{red}1},0]\to[1,1,{\color{red}2}]\to[{\color{red}3},1,2]\to[3,{\color{red}5},2]\to[{\color{red}5},5,2]\to[5,5,{\color{red}5}]$$

Translated by

https://www.luogu.com.cn/user/1048589

样例

7
1
5
14
2025
31415
536870910
1000000000

3
7
9
23
31
59
61

在线编程 IDE

建议全屏模式获得最佳体验

操作

  1. 登录后递交
  3. 讨论 (0)
  4. 题解 (0)
  5. 提交统计