CF768D Jon and Orbs

题目描述

琼恩·雪诺正在寻找一些用来对抗异鬼所需的宝珠。现在有 $k$ 种不同类型的宝珠，每种至少需要一个。每天在绝境长城以北的一棵鱼梁木树下会生成一个宝珠，这个宝珠是任意一种类型的概率均等。由于长城以北危险重重，他希望知道自己至少需要等待多少天后，派人收集这些宝珠时，能够以不小于 $\frac{p_i-\epsilon}{2000}$ 的概率（其中 $\epsilon < 10^{-7}$），收集到每种类型至少一个宝珠。

为了更好地准备战斗，他还需要你帮他计算 $q$ 个不同 $p_i$ 的答案。由于他正与山姆一起制定作战计划，因此将这个任务交给了你。

输入格式

第一行包含两个用空格隔开的整数 $k$ 和 $q$（$1 \le k,q \le 1000$），分别表示宝珠的种类数和查询的数量。

接下来 $q$ 行，每行一个整数 $p_i$（$1 \le p_i \le 1000$），表示第 $i$ 个查询。

输出格式

输出 $q$ 行。对每个查询，输出一个整数，表示所需的最小天数。

输入输出样例 #1

输入 #1

1 1
1

输出 #1

1

输入输出样例 #2

输入 #2

2 2
1
2

输出 #2

2
2

说明/提示

由 ChatGPT 5 翻译