#P5956. [Usaco2022 Feb]Sleeping in Class P
[Usaco2022 Feb]Sleeping in Class P
题目描述
Farmer John 的课常常让 Bessie 打瞌睡。Elsie 记下了每节课 Bessie 打瞌睡的次数。共有 节课,第 节课打瞌睡 次。Elsie 想把记录改成每节课打瞌睡的次数都一样。
一次修改可以将相邻的两项合并成它们的和,或把一项拆成两个任意的非负整数,它们的和等于原来的数。比如将 的第 和第 项合并,得到 。然后拆分第三项,可以把 换成 、、、 或 。
给定 个候选值 。对于每个 ,从原始记录出发,求把记录变成每一项都恰好等于 所需的最少修改次数。
输入格式
第一行一个整数 ()。第二行 个整数 (),且 。
第三行一个整数 ()。接下来 行,每行给出一个 ()。
输出格式
对每个 ,输出一行,写出最少修改次数。若无法使所有项都等于 ,输出 -1。
样例 #1
样例输入 #1
6
1 2 3 1 1 4
7
1
2
3
4
5
6
12
样例输出 #1
6
6
4
5
-1
4
5
样例解释 #1
要使每项都等于 ,至少需要 次修改。一种做法为 $[1,2,3,1,1,4]\to[3,3,1,1,4]\to[3,3,1,5]\to[3,3,6]\to[3,3,3,3]$。无法使每项都等于 ,故该询问输出 。
测试点性质
- 测试点 2–4 满足 。
- 测试点 5–7 中,每个 。
- 测试点 8–26 无额外限制。