시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 74 | 20 | 14 | 23.333% |
영선이와 효빈이는 평소 전함게임을 즐겨한다. 전함게임은 n칸이 일렬로 놓여진 게임판에서 즐길 수 있는데, 공격과 수비로 역할이 나뉜다.
우선 수비는 전함 k개를 게임판 위에 배치하는데, 이때 전함끼리 겹치거나 맞닿아 있으면 안 된다. 전함은 일렬로 a칸을 차지한다. 그리고 전함의 위치는 공격은 볼 수가 없다.
전함이 다 배치되면 공격은 m번의 미사일을 발사하는데, 미사일들을 통해 하나의 전함이라도 맞춘다면 게임에서 이긴다. 이 미사일은 게임판의 한 칸을 공격한다.
이제 게임을 시작한다!!
영선이가 공격을, 효빈이가 수비를 한다. 근데 효빈이는 이 게임에서 지기 싫어 결국 거짓말을 치기로 했다. 공격입장에서 전함의 위치는 볼 수 없기 때문에, 전함에 미사일이 맞아도 안 맞았다고 말한다. 하지만 꼬리가 길면 밟히기 때문에, 논리적으로 봤을 때 전함을 어떻게든 배치하였더라도 미사일을 맞게 된다면, 패배를 인정할 것이다.
영선이는 거짓말을 친 사실을 알면 매우 화를 낼 것이므로, 효빈이는 몇 번째 미사일에서부터 어떻게 배치하더라도 전함이 미사일을 맞게 되는지를 알고 싶다.
효빈이를 대신하여, 몇번째 미사일에서 패배를 인정하면 되는지 출력하시오. 만약 마지막 미사일까지 전부 피해 이길 수 있다면 -1을 출력하시오.
첫째 줄에는 게임판의 칸 수 n, 전함의 개수 k, 전함이 차지하는 칸 수a가 주어진다.(1≤n,k,a≤200,000)
둘째 줄에는 영선이가 쏠 수 있는 미사일의 개수 m이 주어지고,(1≤m≤n)
셋째 줄에는 영선이가 쏠 예정인 미사일의 위치가 서로 다른 정수 m개가 주어진다. 게임판의 위치는 1부터 n까지 순서대로 매겨져 있다. 또한, 조건에 맞게 전함을 게임판에 배치할 수 있게 k와 a가 주어짐이 보장된다.
효빈이가 몇번째 미사일까지 공격당할 시 패배를 인정하면 되는지 출력하시오. 만약 전부 피할 수 있다면 -1을 출력하시오.
11 3 3 5 4 8 6 1 11
3
5 1 3 2 1 5
-1