/ OIer TK / 题库 /

严厉的班长

严厉的班长

测试数据来自 system/1921

描述

木姑娘在班级里面是班长。虽然是副班长,却有着比正班长更高的威信,并深受小朋友们的爱戴。

每天眼保健操时间,木姑娘都要监督所有小朋友认真做眼保健操。整个过程被描述为n个时间段,第i个时间段内对于揉捏穴位的速度被要求为a[i]。

如果某一位小朋友在n个时间段内,速度分别为b[1],b[2],...,b[n],则他的最终得分为 score = |a[1]-b[1]| + |a[2]-b[2]| + ... + |a[n]-b[n]|。

分数越大,则说明表现越差,如果b[1]到b[n]中,又满足任意两个数字均互素,则会受到木姑娘的严厉批评。

对于爱慕木姑娘的孩子来说,能和木姑娘有更多时间待在一起,才是最关键的。

格式

输入格式

第一行一个整数n,1<=n<=100。

第二行有n个整数,分别为a[1],a[2],...,a[n]且对于每一个a[i]满足1<=a[i]<=30。

输出格式

希望可以找出来一组b[1],...,b[n]满足score最小化,且b数组中的n个元素两两互素,并输出此刻的分数score。

样例1

样例输入1

5
1 1 1 1 1

样例输出1

0

样例2

样例输入2

5
1 6 4 2 8

样例输出2

3

限制

25%的数据,n<=10。
60%的数据,n<=30。
100%的数据,n<=100。

来源

感谢 小岛

信息

ID
1863
难度
(无)
分类
动态规划 | 状态压缩DP 点击显示
标签
(无)
递交数
0
已通过
0
通过率
?
上传者