1842번 - 게임하기 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 300 | 55 | 36 | 19.149% |
문제
1행 m열의 직사각형 체스판 위에서 진행하는 게임을 가정해 보자. 체스판의 각 칸에는 1부터 m까지 번호가 매겨져 있다. n개의 폰 (pawn)이 하나씩의 칸을 차지한 채로 체스판 위에 놓여 있으며, m번 칸은 비어 있다. 두 명의 플레이어가 게임을 한다. 각 플레이어는 자기 차례가 오면 i번 칸에 놓인 폰을 집어서 j번 칸으로 이동시킬 수 있다. 이때, j는 비어있는 칸의 번호 중 최솟값인데, 다만 i보다는 커야 한다. 게임의 승자는 마지막 칸인 m번 칸에 폰을 집어넣는 사람이다.
예를 들어, m=7인 그림의 상황에서 차례가 된 플레이어는 2번 칸의 폰을 4번 칸으로 옮길 수 있고, 3번 칸의 폰을 4번 칸으로 옮길 수도 있으며, 6번 칸의 폰을 7번 칸으로 옮겨 게임을 이길 수도 있다.
어떤 플레이어의 수가 ‘필승수'라고 하는 것은, 그 수를 둔 후엔 상대편이 어떤 수를 두더라도 반드시 이길 수 있는 경우를 말한다. 체스판의 현재 상황이 주어졌을 때, 이번에 차례를 맞은 플레이어가 둘 수 있는 필승수의 가짓수를 계산하는 프로그램을 작성하라.
입력
첫째 줄에 두 양의 정수 m과 n이 주어진다. (2 ≤ m ≤ 109, 1 ≤ n ≤ 106, n＜m) 둘째 줄에는 n개의 양의 정수가 오름차순으로 주어지는데, 이는 각각 현재 폰이 놓여 있는 칸의 번호를 나타낸다.
출력
첫째 줄에 이번에 차례를 맞은 플레이어가 둘 수 있는 필승수의 가짓수를 출력한다.
예제 입력 1
5 2 1 3
예제 출력 1
1
예제 입력 2
5 2 2 3
예제 출력 2
0
출처
Olympiad > Polish Olympiad in Informatics > POI 2003/2004 > Stage 1 1번
- 문제를 번역한 사람: author10
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호