만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

끝까지 외친 정수의 개수

면접 대비

시간 제한3초메모리 제한512 MB

요약
두 학생이 금지된 수를 제외하고 1부터 n까지의 정수를 번갈아 부르며, 승패 규칙에 따라 부른 정수의 총 개수를 구합니다.
난이도

보통10점 중 6점

유형
동적 계획법, 게임 이론, 슬라이딩 윈도우
정답자
아직 제출이 없습니다

문제

두 학생이 1 이상 nn 이하의 정수를 외치는 게임을 하고 있다. 첫 번째 학생이 먼저 정수를 외친 뒤, 두 학생이 번갈아 정수를 외친다. 직전 학생이 외친 정수가 aa이면 현재 학생은 (a+1)(a + 1) 이상 (a+k)(a + k) 이하의 정수를 외쳐야 한다. 처음에 첫 번째 학생은 1 이상 kk 이하의 정수를 외쳐야 한다. 두 학생이 외칠 수 없는 정수 목록도 주어지며, 두 학생은 목록에 있는 정수를 외칠 수 없다. 마지막에 정수를 외칠 수 없는 학생이 게임에서 진다.

현재 학생이 이길 수 있는 정수가 있으면 현재 학생이 이기면서, 두 학생이 앞으로 외칠 정수 개수의 합이 최소가 되도록 플레이한다. 현재 학생이 이길 수 있는 정수가 없으면 두 학생이 앞으로 외칠 정수 개수의 합이 최대가 되도록 플레이한다. 현재 학생이 외칠 수 있는 정수가 여러 개이면 그중 하나를 외친다. 두 학생이 규칙에 맞게 플레이했을 때, 두 학생이 외친 정수 개수의 합을 구하자.

입력

첫 번째 줄에 nn과 kk가 공백을 사이에 두고 순서대로 주어진다.

두 번째 줄에 두 학생이 외칠 수 없는 서로 다른 정수가 공백을 사이에 두고 오름차순으로 주어진다.

출력

첫 번째 줄에 두 학생이 규칙에 맞게 플레이했을 때, 두 학생이 외친 정수 개수의 합을 출력한다.

제한

  • 1≤n≤100,0001 \le n \le 100{,}000
  • 1≤k≤1001 \le k \le 100
  • 두 학생이 외칠 수 없는 서로 다른 정수 목록의 개수는 1 이상 nn 이하이다.
  • 두 학생이 외칠 수 없는 정수는 1 이상 nn 이하의 양의 정수이다.

예제3

  1. 예제 1

    입력
    3 2
    1
    
    예상 출력
    2
    
  2. 예제 2

    입력
    4 2
    2 3
    
    예상 출력
    1
    
  3. 예제 3

    입력
    4 2
    1 2
    
    예상 출력
    0