#P18858. [Croatian CPC2025] Formidable Formicidae
[Croatian CPC2025] Formidable Formicidae
Formidable Formicidae
题目描述
一条长度为 的带子被分成 个单位格子,从左到右编号为 。带子上有 只蚂蚁,最初分别位于格子 的中心。
你可以为每只蚂蚁选择初始朝向,向左或向右。开始运动后,所有蚂蚁以每秒一个单位长度的速度移动。两只蚂蚁相撞时,它们立即反向;蚂蚁撞到带子的端点时,也立即反向。转向不消耗时间。
给定 个目标格子 。求最小的非负整数时间 ,使得能够选择初始朝向,让 秒后所有蚂蚁恰好占据这些目标格子的中心。无需指定哪只蚂蚁到达哪个目标格子。
如果无法做到,输出 。
输入格式
第一行包含整数 。
第二行包含 个整数 。
第三行包含 个整数 。
输出格式
输出一个整数,表示最短时间;若不存在这样的初始朝向,输出 。
数据范围
- ,。
- 。
- 所有 互不相同,所有 也互不相同。
样例 1
输入
4 2
2 4
1 4
输出
1
样例 2
输入
8 4
1 3 6 7
1 3 5 8
输出
2
样例 1 说明
让第一只蚂蚁向左,第二只向右。经过一秒,第一只到达格子 的中心;第二只先用半秒到达带子右端点,再用半秒返回格子 的中心。