Race

题目描述

贝茜正在跑一场长度为 $K$（$1\le K\le 10^9$）米的比赛。她开始时速度为每秒 0 米。在任意一秒内，她可以选择将速度增加 1 米/秒、保持不变，或将速度减少 1 米/秒。例如，在第一秒，她可以把速度增加到 1 米/秒并跑 1 米，或者保持 0 米/秒并跑 0 米。贝茜的速度永远不能降到 0 以下。 贝茜会一直朝终点线方向奔跑，并且她希望在整数秒后结束（即在某个整数时刻，位置恰好到达或超过终点线）。此外，她不希望到达终点时跑得太快：在贝茜跑完 $K$ 米的那个瞬间，她刚刚所保持的速度不超过 $X$（$1 \leq X \leq 10^5$）米/秒。对于 $N$（$1 \leq N \leq 1000$）个不同的 $X$ 值，贝茜想知道自己最快能用多久完成比赛。

输入格式

第一行包含两个整数 $K$ 和 $N$。 接下来 $N$ 行，每行包含一个整数 $X$。

输出格式

输出 $N$ 行，每行输出一个整数，表示贝茜跑完 $K$ 米且到达终点时速度小于等于 $X$ 所需要的最少时间。

10 5
1
2
3
4
5

6
5
5
4
4

提示

评分（SCORING）： 测试点 2-4 满足 $N=X=1.$ 测试点 5-10 没有额外限制。 当 $X = 1$ 时，一种最优方案是： 将速度增加到 1 m/s，行进 1 米 将速度增加到 2 m/s， 行进 2 米，总计 3 米 保持速度 2 m/s，行进 总计 5 米 保持速度 2 m/s，行进 7 米总计 保持速度 2 m/s，行进 9 米总计 将速度降低到 1 m/s， 行进 10 米总计 当 $X = 3$ 时，一种最优方案是： 将速度增加到 1 m/s，行进 1 米 将速度增加到 2 m/s， 行进 3 米总计 将速度增加到 3 m/s，行进 6 米总计 保持速度 3 m/s，行进 9 米总计 保持速度 3 m/s，行进 12 米总计 注意，当 $X = 3$ 时，以下方案是不合法的： 将速度增加到 1 m/s，行进 1 米 将速度增加到 2 m/s， 行进 3 米总计 将速度增加到 3 m/s，行进 6 米总计 将速度增加到 4 m/s，行进 10 米总计 这是因为在贝茜刚好跑完 10 米的那个瞬间，她的速度是 4 m/s。 题目来源：Nick Wu

标签: USACO|2020|Bronze

来源

USACO|2020|Bronze