A. Add or XOR

问题描述

给定两个非负整数 $a$ 和 $b$。你可以对 $a$ 进行两种类型的操作，任意次数，任意顺序：

1. $a \leftarrow a + 1$。此操作的成本为 $x$。
2. $a \leftarrow a \oplus 1$，其中 $\oplus$ 表示按位异或操作。此操作的成本为 $y$。

现在要求你使 $a = b$。如果可能，输出最小成本；否则，报告不可能。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ($1 \leq t \leq 10^4$)。接下来是测试用例的描述。

每个测试用例的唯一一行包含四个整数 $a, b, x, y$ ($1 \leq a, b \leq 100, 1 \leq x, y \leq 10^7$) — 给定的两个整数以及两种操作的相应成本。

输出

对于每个测试用例，输出一个整数 — 使 $a = b$ 的最小成本，如果不可能则输出 $-1$。

题解

第二种操作（与1进行异或）当 $a$ 是偶数时会使 $a$ 的值增加1，当 $a$ 是奇数时会使 $a$ 的值减少1。

我们只能在 $a \leq b$ 的情况下从 $a$ 到达 $b$，因为两种操作都只能增加 $a$（除了当 $a$ 是奇数时与1进行异或，这会使 $a$ 减少1）。

策略如下：

• 如果 $a = b + 1$ 且 $a$ 是奇数，我们可以通过一次异或操作到达 $b$，成本为 $y$。
• 如果 $a = b$，不需要操作，所以返回 $0$。
• 如果 $a < b$，我们需要将 $a$ 增加 $(b - a)$ 个单位。
• 否则我们无法从 $a$ 到达 $b$，所以返回 -1。

对于每个单位的增加，我们可以：

1. 使用操作1（加1），成本为 $x$。
2. 当 $a$ 是偶数时，使用操作2（与1进行异或），成本为 $y$。

由于数据量很小，我们可以直接将 $a$ 逐一增加直到达到 $b$，并相应地计算成本。

但实际上，成本可以直接计算：

• 如果 $x \leq y$，总是使用操作1（加1）从 $a$ 到达 $b$，成本为 $(b - a) \cdot x$。
• 否则，成本 $= (b - a) \div 2 \cdot (x + y)$，如果 $(b - a)$ 是奇数，我们还需要一次类型1或类型2的操作。

提交链接