잃어버린 소
면접 대비시간 제한2초메모리 제한512 MB
수직선 위 시작점 x와 목표 y가 주어질 때, 두 배씩 늘어나는 지그재그 탐색을 따라 y에 도달할 때까지 이동한 총 거리를 구한다.
문제
농부 존이 아끼는 소 베시를 잃어버려서 찾아 나서야 한다!
다행히 농장을 가로지르는 길은 긴 길 하나뿐이고, 존은 베시가 이 길 위 어딘가에 있다는 것을 알고 있다. 길을 수직선으로 생각하면 존은 지금 위치 에 있고 베시는 위치 에 있다(존은 를 모른다). 베시의 위치를 안다면 존은 곧장 걸어가서 만큼만 이동하면 된다. 하지만 밖이 어두워서 존은 아무것도 볼 수 없다. 존이 베시를 찾는 방법은 앞뒤로 오가다가 결국 베시의 위치에 도달하는 것뿐이다.
앞뒤로 오가는 가장 좋은 전략을 알아내려고 존은 컴퓨터 과학 연구 문헌을 찾아보았다. 그리고 바로 이 문제를 예전에 컴퓨터 과학자들이 연구했고, 이름도 "잃어버린 소 문제(Lost Cow Problem)"라는 사실을 알고 조금 재미있어했다(실제로 있는 문제다!).
문헌이 권하는 방법은 다음과 같다. 먼저 위치 로 이동하고, 방향을 바꿔 위치 로 이동하고, 다시 위치 로 이동하는 식으로 "지그재그"로 움직인다. 매번 처음 출발한 위치에서 직전보다 두 배 먼 곳까지 간다. 존이 공부하면서 읽은 바에 따르면 이 방법으로는 베시를 찾을 때까지 이동하는 거리가 최악의 경우에도 직선 거리 의 9배를 넘지 않는다(이것도 사실이며, 9배는 어떤 전략으로도 더 낮출 수 없는 최악의 경우 보장값이다).
존은 이 결과를 직접 확인해 보고 싶다. 와 가 주어질 때, 위의 지그재그 탐색 전략을 따라 베시를 찾을 때까지 존이 이동하는 전체 거리를 구하시오. 존은 위치 에 처음 도달하는 순간 멈춘다.
입력
첫째 줄에 서로 다른 두 정수 와 가 공백으로 구분되어 주어진다. 두 수는 모두 이상 이하이다.
출력
존이 베시에게 도달할 때까지 이동한 거리를 한 줄에 출력한다.