← 返回题目列表

AtCoder · acl1_f

F. 中心重新排列

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

分数: 1800 点

问题陈述

给出的是整数序列 A 和 B 长度 3N。这两个序列中的每一个都包含三个拷贝 1, 2, \dots, N。 换句话说, A 和 B 都是以下安排 (1, 1, 1, 2, 2, 2, \dots, N, N, N).

Tak可以对序列执行以下操作 A 任意多次:

  • 从中选择一个值 1, 2, \dots, N 并调用它 x. A 恰好包含三个副本 x。删除这三个元素的中间元素。之后,追加 x 到开头或结尾 A.

检查他是否可以转弯 A 进入 B。如果可以的话,打印实现该目标所需的最少操作数。

约束

  • 1 \leq N \leq 33
  • A 和 B 都是以下安排 (1, 1, 1, 2, 2, 2, \dots, N, N, N).
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N
A_1 A_2 ... A_{3N}
B_1 B_2 ... B_{3N}

输出

如果Tak可以转弯 A 进入 B,打印实现该目标所需的最少操作数。否则,打印 -1.


示例输入 1

3
2 3 1 1 3 2 2 1 3
1 2 2 3 1 2 3 1 3

示例输出 1

4

例如,Tak 可以执行如下操作:

  • 2 3 1 1 3 2 2 1 3 (初始状态)
  • 2 2 3 1 1 3 2 1 3 (选择 x = 2 并将其附加到开头)
  • 2 2 3 1 3 2 1 3 1 (选择 x = 1 并将其附加到末尾)
  • 1 2 2 3 1 3 2 3 1 (选择 x = 1 并将其附加到开头)
  • 1 2 2 3 1 2 3 1 3 (选择 x = 3 并将其附加到末尾)

示例输入 2

3
1 1 1 2 2 2 3 3 3
1 1 1 2 2 2 3 3 3

示例输出 2

0

示例输入 3

3
2 3 3 1 1 1 2 2 3
3 2 2 1 1 1 3 3 2

示例输出 3

-1

示例输入 4

8
3 6 7 5 4 8 4 1 1 3 8 7 3 8 2 4 7 5 2 2 6 5 6 1
7 5 8 1 3 6 7 5 4 8 1 3 3 8 2 4 2 6 5 6 1 4 7 2

示例输出 4

7