2674 : 순간이동 장치(Teleporters)
- 제한시간
- 1000 ms
- 메모리제한
- 64 MB
- 해결횟수
- 1 회
- 시도횟수
- 6 회
문제
당신은 이집트를 서쪽에서 동쪽으로 직선으로 횡단하는 어느 경기에 참가하고 있다.
초기에 경기는 서쪽 끝에서 시작하며, 규정상 언제나 길을 따라 동쪽으로만 이동해야 한다.
그런데 길에는 곳곳에 N개의 순간이동 장치가 설치돼 있다.
순간이동 장치는 두 지점이 한 쌍으로 존재하여 한 지점에 도달한 사람을 다른 지점으로 즉시 옮겨 놓는다.
그래서 순간이동 장치에 도달한 사람은 어느 쪽 지점에 닿았냐에 따라 지금보다 동쪽으로 갈 수도 있고, 왔던 길인 서쪽으로 되돌아갈 수도 있다.
순간이동 된 후에도 당신은 계속해서 동쪽으로 가던 길을 가야 한다.
또한 순간이동 장치가 있는 지점을 순간이동 없이 그냥 무시하고 통과할 수도 없다.
당연한 가정이지만 순간이동 장치가 두 지점이 동일 위치에 겹치는 경우는 없으며, 두 지점은 모두 경기 코스 내부에만 존재한다.
순간이동을 한 번 할 때마다 당신은 1점을 얻는다. 이 경기의 목표는 점수를 최대한 많이 따서 횡단을 마치는 것이다.
점수를 많이 따기 위해, 당신은 경기를 시작하기 전에 최대 M개의 순간이동 장치를 추가로 요구할 수 있다.
새 순간이동 장치의 양 지점은 기존 순간이동 장치들의 지점과 겹치지만 않는다면 아무 곳에나, 심지어 정수가 아닌 위치에도 설정할 수 있다.
모든 순간이동 장치들의 지점 위치는 제각기 달라야 하며 새 순간이동 장치들도 지점의 위치가 반드시 경기 코스 내부에 존재해야 한다.
참고로, 이 규정대로라면 순간이동 장치를 어떤 방식으로 설치하더라도
무한 순환에 빠지는 일이 없이 동쪽까지 경기 완주는 언제나 가능하다는 사실을 염두에 두기 바란다.
N개의 기본 순간이동 장치들의 위치와 당신이 추가 가능한 순간이동 장치 개수의 최대치 M을 입력 받아서,
이 경기 코스에서 얻을 수 있는 최대 점수를 구하는 프로그램을 작성하시오.
입력형식
출력형식
입력 예3 1 10 11 1 4 2 3 |
출력 예6 |
입력 예3 3 5 7 6 10 1999999 2000000 |
출력 예12 |
Hint!
