QOJ.ac

QOJ

时间限制: 1.0 s 内存限制: 256 MB 总分: 100

#9595. Python 将比 C++ 更快

统计

Little Q 正在学习编程语言。他经常使用 Python,因为它是最常用的编程语言之一。然而,当他用 Python 编写代码时,他发现程序运行效率并不高,尤其是与 C/C++ 相比时。他想知道 Python 的运行效率是否会随着版本更新而有所提高,于是进行了一项实验。

实验中使用的算法是蒙特卡洛算法,通过在正方形内生成大量随机点来估计 $\pi$ 的值。他在 Python 中编写了这个算法,并使用不同版本的 Python 运行它,记录下运行时间。形式化地,总共有 $n$ 个已发布的 Python 版本,即 3.1, 3.2, ..., 3.n。该算法在版本 3.i 上的运行时间为 $a_i$ 毫秒。Little Q 惊讶地发现,Python 的运行效率确实会随着版本迭代而改变。

Little Q 还测试了该算法在 C++ 中的运行时间,稳定为 $k$ 毫秒。接着他产生了一个有趣的想法:利用实验数据来预测未来的哪个 Python 版本效率会高于 C++。遗憾的是,他忘记了如何应用回归模型,因此他使用了一种暴力预测方法:

  • 对于 $i > n$ 的未来版本 $i$,$a_i = \max(0, 2a_{i-1} - a_{i-2})$。

利用这种预测方法,请告诉他最早的效率严格高于 C++ 的 Python 版本,即找到满足 $a_i < k$ 的最小 $i$。

输入格式

第一行包含两个整数 $n$ 和 $k$ ($2 \le n \le 10, 1 \le k \le 1000$),分别表示已发布的 Python 版本数量和算法在 C++ 中的运行时间。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($k < a_i \le 10^5$),表示算法在每个 Python 版本上的运行时间。

输出格式

输出 Python 3.x will be faster than C++,其中 $x$ 是满足 $a_x < k$ 的最早版本号。如果不存在这样的版本,则输出 Python will never be faster than C++

样例

样例输入 1

10 1
11 45 14 19 19 8 10 13 10 8

样例输出 1

Python 3.14 will be faster than C++

样例输入 2

10 1
2 2 2 2 2 2 2 2 2 2

样例输出 2

Python will never be faster than C++

说明

第一个样例可以用下图表示,其中蓝线代表 Python 的效率,红线代表 C++ 的效率。虚线表示预测值。正如你所见,Python 3.14 的效率将高于 C++。

对于第二个样例,很容易注意到 Python 的运行时间始终为 2 毫秒,包括对未来版本的预测。因此,Python 的效率永远不会高于运行时间为 1 毫秒的 C++。

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.