페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#4576

잠꾸러기 2s 512MB

문제

메이플 월드의 잠꾸러기 웡키는 N 마리의 주황버섯과 함께 일자 맵에서 살고 있다.

 

일자 맵의 위치는 양의 정수 x 에 대해 웡키를 기준으로 왼쪽으로 x 만큼 떨어져 있으면 위치 -x 에 있다고 표현하고, 

오른쪽으로 x 만큼 떨어져 있으면 위치 x 에 있다고 표현하고, 윙키가 위치한 곳에 있으면 위치 0에 있다고 표현한다.

 

각 주황버섯은 매 분마다 왼쪽으로 1 만큼, 오른쪽으로 1 만큼 혹은 제자리로 점프한다. 

즉, 현재 주황버섯이 위치 p 에 있으면 1 분 뒤에는 위치 p-1 에 있거나, 위치 p에 있거나 위치 p+1에 있다.

 

요정 웡키는 주황버섯들이 점프하자마자 모든 주황버섯의 위치를 기록하고 잠들었다. 

기록하고 잠드는 데에는 시간이 걸리지 않는다 가정하자. 

같은 위치에 두 마리 이상의 주황버섯이 존재할 수도 있다.

 

1 분 이상 잠을 잔 후 잠에서 깨어난 웡키는 즉시 모든 주황버섯의 위치를 기록했다. 

이때 깨어나서 기록하는 데에는 시간이 걸리지 않는다고 가정하고, 

주황버섯은 모두 똑같이 생겨서 서로 구분할 수 없다.

 

문득 웡키는 두 기록을 가지고 자신이 최소 몇 분 잤는지 궁금해졌다. 

요정 웡키를 도와 웡키가 최소 몇 분 잤는지 구해주자.​ 


입력

첫 줄에 주황버섯의 수 N이 주어진다. (1≤N≤100 000)

두 번째 줄에 웡키가 잠에 들기 전에 적어둔 주황버섯의 위치 N 개가 공백으로 구분되어 주어진다.

세 번째 줄에 웡키가 잠에서 깨어난 후에 주황버섯의 위치 N 개가 공백으로 구분되어 주어진다.

주어지는 모든 위치는 -1,000,000,000 이상 1,000,000,000 이하이다.​ 

 

 

종류 1 (11점): N≤10
종류 2 (28점): N≤1,000
종류 3 (61점): 추가적인 제한 조건이 없음.​

출력

첫 줄에 웡키가 잔 최소 시간을 출력한다. 


예제 #1

5

1 3 4 6 10
8 3 5 –2 16
6

예제 #2

5

1 1 1 1 1
5 5 5 5 5
4

예제 #3

1

1
1
1

출처

NYPC2020 본선2|ohjtgood
로그인해야 코드를 작성할 수 있어요.