반딧불이 서브태스크 1초 128MB
문제
반딧불이가 석순(바닥에서 솟아오르는)과 종유석(천장에 매달린) 등 장애물이 가득한 동굴로 날아들어왔습니다.
동굴의 길이는 N 이고 높이는 H 입니다. 첫 번째 장애물은 항상 석순이고 그 후로는 종유석과 석순이 번갈아 나타나는 형태입니다.
다음은 길이 14, 높이 5의 동굴의 예입니다 (이미지는 두 번째 예에 해당):
반딧불이는 장애물 주위를 날아다니는 타입이 아니라, 강력한 쿵푸 동작으로 동굴의 한 쪽 끝에서 다른 쪽 끝까지 높이와 양을 선택하여 모든 장애물을 파괴할 것입니다.
만약 반딧불이가 지면으로 부터 4번째 위치에 해당하는 높이를 선택하면 반딧불이는 총 8개의 장애물을 파괴합니다:
이것은 최선의 선택이 아닙니다. 왜냐하면 반딧불이가 높이 1이나 높이 5 중 하나를 선택하면 덜 피곤할 것이기 때문입니다.
그런 경우에는 오직 7개의 장애물만을 파괴하면 되기 때문입니다.
동굴의 길이와 높이, 그리고 모든 장애물의 크기가 주어졌을 때, 반딧불이가 동굴 끝에 도달하기 위해 파괴해야 하는 최소 장애물 수와 그 수를 달성할 수 있는 높이의 수를 출력하는 프로그램을 작성합시다.
입력
첫 번째 줄에 동굴의 길이와 높이를 의미하는 두 개의 정수 N과 H가 입력된다. (2 ≤ N ≤ 200,000, 2 ≤ H ≤ 500,000, N은 항상 짝수[홀수도 가능] )
다음 N개의 줄에는 장애물의 크기가 한 줄에 하나씩 입력된다. 모든 크기는 H보다 작은 양의 정수이다.
출력
한 줄에 공백으로 구분된 두 정수를 출력한다.
첫 번째 숫자는 반딧불이가 파괴해야 하는 최소 장애물 수이고 두 번째 숫자는 그것이 달성될 수 있는 높이의 수다.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 10점 | H ≤ 3 |
| #2 | 20점 | N, H ≤ 5,000 |
| #3 | 70점 | 추가 제한 없음 |
예제 #1
6 7
1
5
3
3
5
1
2 3
예제 #2
14 5
1
3
4
2
2
4
3
4
3
3
3
2
3
3
7 2
로그인해야 코드를 작성할 수 있어요.