3432. Smooth Array

单点时限: 4.0 sec

内存限制: 1024 MB

We always hope things in our lives will run smoothly, and having smooth arrays may help. An array of non-negative integers is -smooth if the sum of every set of consecutive integers is exactly . Unfortunately, not all arrays are -smooth. In fact, all -smooth arrays must contain a repeating pattern of length .

Any array can be made -smooth by changing its elements. In each change one element may be modified to any integer between and , inclusive. You want to make all of your arrays smooth, but you don’t want to make any more changes than necessary. So the question is: What is the minimum number of changes you have to make so that a given array would become -smooth?

输入格式

The first line of input will consist of three integers of the form:

where is the size of the array.

The remainder of the file will consist of integers, , separated by white space.

All input will be within the following constraints:

  • ;
  • .

输出格式

Your program must output a single integer specifying the minimum number of changes that must be made in order to make the array smooth.

样例

Input
3 3 5
1
2
3
Output
1
Input
6 3 5
1
2
3
3
2
1
Output
3
Input
5 1 5
1
2
3
4
5
Output
4

1 人解决,1 人已尝试。

1 份提交通过,共有 1 份提交。

8.9 EMB 奖励。

创建: 2 年,2 月前.

修改: 2 年,2 月前.

最后提交: 2 年,2 月前.

来源: NCNA 2017

题目标签
DP