苏老师的羊腿复制器(新)
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
文件读写
输入文件copy.in
输出文件copy.out
限制
1000ms
128MB
说明
苏老师有一个用于存放羊腿的神奇装置，这个装置呈一个桶的形状，深度无限大，其中每一层都可以存放一个羊腿
每次苏老师往桶里放入羊腿时，只能放在最顶层羊腿的更上一层，而每次取出羊腿时也只能取出最顶层的羊腿
例如苏老师的桶里依次存放了 $3$ 个羊腿，质量分别为 $1,2,3$，那么此时苏老师只能取出最顶层质量为 $3$ 的羊腿，不能跨过 $3$ 直接取质量为 $2$ 和 $1$ 的羊腿
现在苏老师给这个装置加了三个更加神奇的功能——生成、合成与复制！
1. 生成功能：苏老师可以凭空生成一个质量为 $1$ 的羊腿，并将它放在装置最顶层
2. 合成功能：苏老师可以将现在处于最顶层的两个羊腿合并成一个羊腿，并且羊腿质量不会发生消耗，并将合成后的羊腿放在装置最顶层
3. 复制功能：苏老师可以将现在处于最顶层的羊腿完美复制一份，并将它放在装置最顶层
例如苏老师可以依次使用如下按钮：`生成、生成、合成、复制、生成、合成、合成`
这样的操作可以凭空得到一个质量为 $5$ 的羊腿
假设三种功能的能量消耗均一样，现在苏老师想知道最少需要使用多少次功能，可以凭空得到一个质量为 $n$ 的羊腿？
并且苏老师不想浪费粮食，他不希望最终装置中还存在其他羊腿
输入格式
输入第一行包含一个整数 $T$, 表示询问次数
每行包含一个正整数 $n$,表示苏老师想要得到的羊腿质量
| 数据组号 | $n$ | 特别的保证| |
| :---: | :---: | :---: | :---: |
| $1$ | $1 \leq n \leq 10$ |无 | $T=1$ |
| $2$ | $1 \leq n \leq 15$ | 无 | $T = 5$ |
| $3 \sim 5$ | $1 \leq n \leq 100$ | 无 | $T \leq 1000$ |
输出格式
对于每一次询问，输出苏老师最少需要使用功能的次数
样例
1
572023普及组模拟赛1
- Status
- Done
- Rule
- OI
- Problem
- 4
- Start at
- 2023-9-29 18:00
- End at
- 2023-9-30 18:00
- Duration
- 3.5 hour(s)
- Host
-
sulaoshi
- Partic.
- 3