← 返回题目列表

AtCoder · joi2006yo_d

D. JOI 2006 初步问题 4

中文机器翻译题面 查看原题

配点: 100 点

問題

不同尺寸 n 杯子和 3 有 A、B、C 三个托盘,它们的杯子分别是 3 几个托盘彼此叠放成一堆。然而,在任何托盘中,该托盘中最小的杯子都放置在底部。2 最小的杯子位于其顶部。 将3 最小的杯子放在其上面,并将杯子按尺寸降序面朝下堆叠。比如下图右侧,n = 5 杯子分别放置在托盘 A、B 和 C 中。 2 個,0 個,3 一个放在另一个的上面。

因此,给定杯子的初始状态,以下规则 我们希望找到在观察 1 ~ 3 的同时将所有杯子移至托盘 A 或 C 的次数。

(規則 1) 1 次 1 只能移动一个杯子。它是该托盘上的杯子中最上面的杯子(即最大的杯子)。
(規則 2) 请勿将小杯子叠放在大杯子上。
(規則 3) 杯 1 只允许从托盘 A 到 B、B 到 A、B 到 C 以及 C 到 B 直接移动;不允许直接从 A 移动到 C 或从 C 移动到 A。

n 杯子和整数的初始状态 鉴于 m , 确定是否可以在m 步内将所有杯子堆叠在一起,放在托盘 A 或 C 上,如果可以,则设置最小移动数,如果不能,则设置最小移动数。 创建一个输出 -1 的程序。

输入 在 1 行中,n 和 按字典顺序比较 m 使用空格作为分隔符按此顺序写入。1 \leqq n \leqq 15 和1 \leqq m \leqq 15\,000\,000 。 直到2 行目,3 行目,4 行中,1 减去 n 的整数 3 项目分为两组,并在每组内按升序(升序)排列。但是,这些项目的数量写在每行的开头(整数之前)。2 行中写入的整数(第一个 1 (除一)表示托盘 A 上堆叠的每个杯子的尺寸。同样,3 行中写入的整数(第一个 1 除一)表示托盘B上堆叠的每个杯子的尺寸,4 行中写入的整数(第一个 1 (除一项)表示托盘 C 上堆叠的每个杯子的尺寸。

对于输出,输出(移动次数或 在 -1之后插入换行符)。


入力例 1

3 10
0
1 1
2 2 3

出力例 1

9

入力例 2

4 20
2 1 2
1 3
1 4

出力例 2

3

入力例 3

2 5
2 1 2
0
0

出力例 3

0

入力例 4

3 3
0
1 1
2 2 3

出力例 4

-1