#P8796. [2017年江苏]优美的棋

    ID: 8890 传统题 1000ms 256MiB 尝试: 2 已通过: 1 难度: 5 上传者: 标签>贪心组合数学博弈论CF1700数学构造枚举

[2017年江苏]优美的棋

优美的棋

题目描述

SR 最近沉迷于下棋,他想修炼自己优美的棋术。

SR 手中有一个1×n1\times n 的棋盘,其中mm 个位置上已经摆放了棋子,其余的位置均为空,未摆放棋子。

SR 在任意时刻可以执行以下其中一个操作:

  1. 花费 11 的代价在任意一个空位置上摆放棋子。

  2. 对于空位置xx,若存在两个已经摆放棋子的位置i,j(i<j)i,j(i<j),若满足x−i=j−xx-i=j-x(即xx 为i,ji,j 的中点)且位置 ii 到位置jj 之间的所有位置(不包括 i,ji,j )均未被摆放棋子,则可以花费00的代价在位置xx处摆放一枚棋子。

SR 执着于练就优美的棋法,他希望花费最少的代价将所有空位置摆放上棋子。

输入格式

第一行输入两个非负整数n,mn,m。

第二行包括mm个正整数,表示哪些位置已经被摆放了棋子。

输出格式

一行一个整数,表示最少的代价。若 n=0n=0,棋盘没有空位置,不需要进行任何操作,答案为 00。

样例输入

10 2
2 5

样例输出

4

数据范围与约定

对于 2020% 的数据,n≤8n\le 8。 对于 4040% 的数据,n≤20n\le 20。 对于 6060% 的数据,n≤103n\le 10^{3}。 对于 8080% 的数据,n≤106n\le 10^{6}。

对于 100100% 的数据,n≤1018,0≤m≤5n\le 10^{18},0\le m\le 5。

其中对于额外的 3030% 的数据 m=0m=0