#P18928. [2026多校联测]环灯校准
[2026多校联测]环灯校准
环灯校准
题目描述
观测结束后,维护员要关掉圆形平台上的全部指示灯。平台上有一台校准器,每次都要同时翻转相邻的若干盏灯,无法单独控制其中一盏。
共有 盏灯,沿顺时针方向编号为 。第 盏的下一盏是第 盏。第 盏灯的初始状态为 ,其中 表示熄灭, 表示点亮。
校准器的作用范围固定为 盏灯。一次操作选择起点 ,从第 盏开始,沿顺时针方向将连续 盏灯的状态全部翻转,即 变为 、 变为 ,费用为 。当 时,这次操作会翻转全部灯。可以多次选择同一个起点,每次分别付费。
请你求出关掉全部灯的最小总费用。也可以不操作;如果无论怎样操作都无法关掉全部灯,输出 。
输入格式
第一行两个整数 。
第二行 个整数 。
第三行 个整数 。
输出格式
输出一个整数,表示最小总费用;无解时输出 。
样例 1 输入
4 2
1 1 0 0
5 2 4 3
样例 1 输出
5
样例 1 解释
只在起点 操作一次即可,费用为 。也可以在其余三个起点各操作一次,但费用为 ,因此最小费用是 。
样例 2 输入
3 2
1 0 0
1 2 3
样例 2 输出
-1
样例 2 解释
每次操作恰好翻转两盏灯,状态为 的灯的数量的奇偶性不变。初始只有一盏灯为 ,所以无解。
样例 3
见下发文件中的 phase/3.in 和 phase/3.ans。这是一组较大的样例,题面中不展开。
数据范围与子任务
对于所有测试数据,保证:,,。
本题共有四个子任务,各组独立计分。通过某组全部测试点,才能得到该组分数。
| 子任务 | 分值 | 额外约束 |
|---|---|---|
| 1 | 20 | |
| 2 | 或 | |
| 3 | ||
| 4 | 40 | 无额外约束 |