AdditionalFile4849.zip

P9863 [POI 2021/2022 R2] arm

题目背景

翻译自 POI2021-2022R2 Day0 试机题。

题目描述

初始时你有 $1$ 个物品，你需要将物品的数量按若干次以下步骤增加到 $> n$ 个。

• 选择 $1$：将物品数量存储进数据库中，耗费 $a$ 的时间。
• 选择 $2$：使物品数量增加等同于数据库中的数量，耗费 $b$ 的时间。

初始时数据库为空，问最小耗费时间。

输入格式

输入一行，共三个整数 $n,a,b\ (1 \leq n \leq 10^{18},1 \leq a,b \leq 10^9)$。

输出格式

输出最小的耗费时间。

输入输出样例 #1

输入 #1

8 2 1

输出 #1

8

说明/提示

样例解释：

初始时你有一个物品。
先进行一次扫描，耗费 $2$ 时间。
然后打印 $2$ 次，耗费 $1 \times 2 = 2$ 时间，数量增加到 $3$。
继续进行扫描，耗费 $2$ 时间。
最后再打印 $2$ 次，耗费 $1 \times 2 = 2$ 时间，数量变为 $9$。

子任务分配：

子任务编号	特殊性质	分值
$1$	$a = b = 1$	$10$
$2$	$n \leq 10^3$	$40$
$3$	$n \leq 10^5$	$15$
$4$	$n \leq 10^9$
$5$	无特殊限制	$20$

子任务 $0$ 为样例。

#4849. 「POI 2021/2022 R2」Armia klonów

标签: 传统 | 时间限制: 1000 ms | 内存限制: 256 MiB |

题目描述

题目译自 XXIX Olimpiada Informatyczna – II etap Armia klonów

Bajtazar 是字节共和国的将军，他正面临着新的挑战。据情报部门报告，敌对的比特联邦即将对共和国发动攻击。形势看似危急，因为比特联邦的强大军队拥有 $n$ 台战斗机器人，而字节共和国只有一台机器人。好在 Bajtazar 最近购买了一台高效且精准的 3D 打印机。这台机器可以扫描并将整个字节军队存入内置内存（无论军队规模大小，这一操作始终需要 $a$ 小时）；它还能打印内存中的内容，每次打印固定需要 $b$ 小时。一次扫描后，可以进行多次打印。

现在，Bajtazar 想知道，他需要多少时间才能让自己的军队数量（包括最初的那台机器人）超过比特联邦的军队规模。请你帮助他解决这个问题。

输入格式

输入只有一行，包含三个整数 $n, a, b$ $(1 \leq n \leq 10^{18}, 1 \leq a, b \leq 10^{9})$，分别表示比特联邦军队的规模以及 Bajtazar 打印机的扫描和打印参数。

输出格式

输出只有一行，包含一个整数 $t$，表示打印至少 $n$ 台新机器人所需的最短小时数。

样例 1

输入

8 2 1

输出

8

要让军队总数达到至少 $9$ 台，需要 $8$ 小时。首先，扫描一台机器人需要 $2$ 小时。接着，进行两次内存打印，每次 $1$ 小时，共 $2$ 小时，此时军队规模增至 $3$ 台。然后，再次扫描整个军队（$3$ 台），需要 $2$ 小时，再进行两次打印，共 $2$ 小时，最终军队规模达到 $9$ 台。经过 $8$ 小时，共制造了 $8$ 台新机器人，此时打印机内存中存储的是 $3$ 台机器人的扫描数据。

样例 2

见附加文件下 [arm1.in](file:arm1.in) 和 [arm1.out](file:arm1.out)。

该样例满足 $n=100, a=1, b=1$；

样例 3

见附加文件下 [arm2.in](file:arm2.in) 和 [arm2.out](file:arm2.out)。

该样例满足 $n=1000000, a=100, b=1$；

样例 4

见附加文件下 [arm3.in](file:arm3.in) 和 [arm3.out](file:arm3.out)。

该样例满足 $n=10^{18}-1, a=7654321, b=1234567$；

样例 5

见附加文件下 [arm4.in](file:arm4.in) 和 [arm4.out](file:arm4.out)。

该样例满足 $n=10^{18}, a=3 \cdot 10^{9}, b=10^{9}$。

数据范围与提示

详细子任务附加限制及分值如下表所示。

子任务编号	附加限制	分值
$1$	$a=b=1$	$10$
$2$	$n \leq 1000$	$40$
$3$	$n \leq 100000$	$15$
$4$	$n \leq 10^{9}$	$15$
$5$	无附加限制	$20$