잃어버린 소

농부 존이 자랑스러운 소 베시를 잃어버렸다. 반드시 찾아야 한다!

다행히 농장을 가로지르는 긴 길은 단 하나뿐이고, 농부 존은 베시가 이 길 위의 어딘가에 있어야 한다는 것을 알고 있다. 이 길을 수직선으로 생각하면, 농부 존은 현재 위치 \(x\)에 있고 베시는 현재 위치 \(y\)에 있다(농부 존은 \(y\)를 모른다). 농부 존이 베시의 위치를 알기만 한다면 곧장 베시에게 걸어가 \(|x - y|\)의 거리만 이동하면 된다. 안타깝게도 밖은 어두워서 농부 존은 아무것도 볼 수 없다. 베시를 찾는 유일한 방법은 베시의 위치에 도달할 때까지 앞뒤로 왔다 갔다 걷는 것뿐이다.

왔다 갔다 하며 탐색하는 최선의 전략을 찾으려던 농부 존은 컴퓨터 과학 연구 문헌을 뒤져 보고, 바로 이 문제가 과거에 컴퓨터 과학자들에 의해 연구되었을 뿐 아니라 실제로 "잃어버린 소 문제(Lost Cow Problem)"라고 불린다는 사실을 알고는 다소 즐거워한다(실제로 그렇다!).

농부 존이 베시를 찾기 위해 권장되는 해법은, 위치 \(x+1\)로 이동한 뒤 방향을 바꿔 위치 \(x-2\)로 이동하고, 다시 위치 \(x+4\)로 이동하는 식으로, 매 단계마다 처음 시작 위치에서 이전보다 두 배 먼 곳까지 가는 "지그재그" 패턴으로 움직이는 것이다. 잃어버린 소 문제를 푸는 알고리즘을 공부하며 읽은 바에 따르면, 이 방법은 베시를 찾을 때까지 최악의 경우에도 자신과 베시 사이의 직선 거리 \(|x-y|\)의 9배만 이동하면 됨을 보장한다(이것도 사실이며, 계수 9는 어떤 전략으로도 달성할 수 있는 가장 작은 최악의 경우 보장이다).

농부 존은 이 결과를 검증해 보고 싶어 한다. \(x\)와 \(y\)가 주어질 때, 위의 지그재그 탐색 전략에 따라 베시를 찾을 때까지 농부 존이 이동하는 총거리를 계산하시오.

문제 출처: Brian Dean

문제 출처: Brian Dean

입력의 한 줄에 공백으로 구분된 서로 다른 두 정수 \(x\)와 \(y\)가 주어진다. 둘 다 \(0 \ldots 1,000\) 범위이다.

농부 존이 베시에게 도달하기 위해 이동하는 거리를 한 줄에 출력한다.

riseoj 작성

출처 올림피아드 > USACO > 2016-2017 > US Open > Bronze