#F5. 宝石项链
宝石项链
T1 宝石项链(necklace)
时间限制:1.0 秒 空间限制:256 MB
题目描述
小 S 有一条由 颗宝石串成的环形项链,宝石编号为 。第 颗宝石的颜色为 。编号在模 意义下相邻,即 与 相邻, 与 相邻,, 与 相邻, 与 相邻。
小 S 可以进行任意次如下操作:选择一颗宝石 ,同时翻转宝石 的颜色(下标在模 意义下计算)。若同一种颜色在一次操作中被翻转多次,则每次都会改变颜色(翻转两次等于不变)。第 颗宝石被选择一次需要支付 的代价;同一颗宝石可以被选择多次,每次都要支付代价。
小 S 希望最终所有宝石的颜色相同(全部为 或全部为 )。请你求出最小总代价;如果无论如何都无法做到,输出 。
输入格式
第一行一个正整数 。
第二行 个整数 。
第三行 个正整数 。
输出格式
输出一行一个整数,表示最小总代价;若无解,输出 。
样例 1
输入:
4
1 0 1 0
5 1 2 3
输出:
4
样例 1 解释: 选择第 颗和第 颗宝石各操作一次,总代价为 。两次操作后所有宝石都变成颜色 ,可以证明不存在更小的代价。
样例 2
输入:
6
1 0 0 0 0 0
1 1 1 1 1 1
输出:
-1
样例 2 解释: 当 是 的倍数时,三个同余类(下标模 )中颜色 的个数的奇偶性必须相同,否则无解。这里三个同余类中颜色 的个数分别为 ,奇偶性不同,因此无解。
数据范围
对于全部测试数据:;;。
子任务
| 子任务 | 分值 | 特殊限制 |
|---|---|---|
| 1 | 20 | |
| 2 | 所有 | |
| 3 | ||
| 4 | 40 | 无特殊限制 |
提示: 答案可能超过 ,请使用 位整数。