레이팅 미적용농부 존의 소들은 최근 중국 설날이 지나 소의 해(Year of the Ox)가 시작되었다는 소식을 듣고 신이 났다. 소의 해는 언제나 소들이 가장 좋아하는 해이다.
잘 알려져 있듯이, 중국 달력의 띠 동물은 12년 주기를 따른다: 소, 호랑이, 토끼, 용, 뱀, 말, 양, 원숭이, 닭, 개, 돼지, 쥐, 그리고 다시 소. 조금 덜 알려진 사실은, 소의 해마다 신비로운 시간 포털이 열려 소들이 과거나 미래의 다른 소의 해로 시간 여행을 할 수 있다는 것이다.
소 베시는 올해 열린 시간 포털을 이용해, 아주 오래전 역사 속에 살았던 유명한 소 조상 \(N\)명을 방문하고 싶어 한다. 여기서 \(1 \leq N \leq 0x10000\)이다 (소의 해인 만큼 \(N\)의 상한을 16진수로 쓰는 것이 어울려 보인다; 0x10000은 65536과 같다).
안타깝게도 시간 여행은 베시를 조금 어지럽게 만들기 때문에, 베시는 시간 점프를 최대 \(K\)번만 하고 싶다 (\(1 \leq K \leq N\)). 시간 점프를 총 \(K\)번 이하로 사용하면서 모든 조상을 방문하고 현재 연도로 돌아오는 데 걸리는 최소 연수를 구하는 것을 도와주자.
베시는 어떤 소의 해에 시간 포털을 사용하고 싶지 않으면 사용하지 않아도 된다. 시간 포털은 각 소의 해의 첫날끼리 서로 연결하므로, 예를 들어 베시가 어떤 시간 포털로 이동한 뒤 다음 시간 포털까지 12년을 기다리면 그 과정에서 정확히 12년을 보내게 된다. 베시는 현재 소의 해의 첫날에 모험을 시작하므로, 곧바로 과거로 여행할 수 있다. 베시의 조상들 중 소의 해에 사는 조상은 없다.
문제 제공: Brian Dean, David Yang
문제 제공: Brian Dean, David Yang
입력의 첫째 줄에 \(N\)과 \(K\)가 주어진다. 다음 \(N\)개의 줄에는 \(1 \ldots 10^9\) 범위의 서로 다른 정수 \(N\)개가 주어지는데, 이는 베시의 \(N\)명의 조상 각각이 몇 년 전에 살았는지를 나타낸다.
베시가 모든 조상을 방문하고 현재 연도로 돌아오는 데 걸리는 최소 연수를 출력한다.
5 3
101
85
100
46
9536One way for Bessie to visit all her ancestors and return in 36 years is as
follows:
- Enter the portal in the present day and travel 48 years into the past.
- Wait 12 years, then enter the portal 36 years in the past and travel 108 years into the past.
- Wait 24 years, then enter the portal 84 years in the past and travel back to the present year.
riseoj 작성
출처 올림피아드 > USACO > 2020-2021 > February > Silver