AdditionalFile5563.zip

#5563. 「POI2026 R1」Wyrażenie arytmetyczne

标签: 传统 | 时间限制: 11000 ms | 内存限制: 128 MiB |

题目描述

题目译自 XXXIII Olimpiada Informatyczna – I etap Wyrażenie arytmetyczne

Bajtek 喜欢在空闲时间解算术谜题。这类谜题通常都差不多：给定参数 $a, b, c$ 和一个数字 $n$，需要构造一个算术表达式，使其计算结果等于 $n$，且成本最小。

算术表达式的定义如下（递归定义）：

• 基本表达式 $1$ 是一个算术表达式，其成本为 $a$，计算结果为 $1$。

• 如果 $X$ 和 $Y$ 是算术表达式，成本分别为 $x$ 和 $y$，计算结果分别为 $p$ 和 $q$，那么：

  1. $(X+Y)$ 是一个算术表达式，成本为 $x + y + b$，计算结果为 $p + q$；
  2. $(X \times Y)$ 是一个算术表达式，成本为 $x + y + c$，计算结果为 $p \times q$。

例如：$((1+1) \times (1+1)) \times (1+1)$ 是一个合法表达式，成本为 $6a + 3b + 2c$，计算结果为 $8$。

Bajtek 想知道，对于从 $1$ 到 $n$ 的每一个整数，最小的表达式成本分别是多少。请你帮助他计算这些最小成本。

输入格式

仅一行四个整数 $n, a, b, c$ $(1 \leq n \leq 3000,\ 1 \leq a, b, c \leq 10^9)$。

输出格式

仅一行输出 $n$ 个整数，用单个空格分隔，第 $i$ 个数表示计算结果为 $i$ 的算术表达式的最小成本。

样例

输入

6 1 4 2

输出

1 6 11 14 19 19

下表展示了计算到各数字的最优表达式及其成本。

附加样例

1. $n=9,\ a=2,\ b=3,\ c=1$
2. $n=200,\ a=1,\ b=2,\ c=3$
3. $n=2500,\ a=1,\ b=1,\ c=1$
4. $n=3000,\ a=b=c=10^9$

数据范围与提示

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