QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 2048 MB Total points: 100

#8660. 再战二十四点

Statistics

我们知道……我们以前在竞赛题目中用过“24点挑战”。如果你从未听说过“24点挑战”(或者记忆力不太好),这个游戏的目标是利用给定的 4 个数字(基准值),通过四则运算(必要时可使用括号)得出 24。例如,给定 4 个基准值 3 5 5 2,你可以通过多种方式得到 24。其中两种方式为:$5*5-3+2$ 和 $(3+5)*(5-2)$。请记住,乘法和除法的优先级高于加法和减法,且同级运算符按从左到右的顺序计算。

这对你们大多数人来说都很熟悉,但你们可能不知道的是,你可以对用于得出 24 的表达式的质量进行评分。事实上,我们确信你们不知道这一点,因为这是我们刚刚编造出来的。评分规则如下:表达式的完美评分为 0。每使用一对括号,评分增加 1 分。此外,相对于 4 个基准值的原始顺序,每产生一个逆序对(即交换两个相邻的值),评分增加 2 分。上述第一个表达式的评分为 4,因为使用了两次逆序操作将 3 移动到了第三个位置。第二个表达式的评分更好,为 2,因为它没有使用逆序操作,但使用了两对括号。作为进一步的例子,初始基准值集合 3 6 2 3 可以产生一个评分为 3 的表达式——即 $(3+6+3)*2$——但它也可以产生一个完美评分 0 的表达式——即 $3*6+2*3$。不用说,评分越低,表达式就“越好”。

我们将使用两条附加规则:1) 你不能在任何表达式中使用一元减号,因此你不能使用基准值 3 5 5 2 产生表达式 $-3+5*5+2$;2) 除法仅在结果为整数时才可使用,因此你不能使用基准值 2 3 4 9 产生表达式 $2/3*4*9$。

给定一个基准值序列,确定得出 24 的最低评分表达式。顺便提一下,初始基准值集合 3 5 5 2 有一个评分为 1 的表达式——你能找到它吗?

输入格式

输入包含一行,包含 4 个基准值。所有基准值均在 1 到 100 之间(含 1 和 100)。

输出格式

显示使用该基准值序列可能达到的最低评分。如果无法得出 24,则显示 impossible

样例

样例输入 1

3 5 5 2

样例输出 1

1

样例输入 2

1 1 1 1

样例输出 2

impossible

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.