ez_code   1년 전

문제

농부 존은 상품으로 받은 소 베시를 잃어버려 찾아야 합니다!

다행히 주변에는 농장을 가로지르는 긴 길 하나밖에 없어 농부 존은 베시가 그 길 어느 위치에 있다는 것을 압니다. 길을 수직선으로 생각하면, 현재 농부 존은 x에 있고 베시는 (농부 존은 모르는 위치인) y에 있습니다. 만약 농부 존이 베시가 어디 있는지 안다면, 존은 |x - y|의 거리를 베시를 향해 걸어가면 됩니다. 하지만 밖이 어두워 농부 존은 아무 것도 볼 수 없습니다. 존이 취할 수 있는 유일한 방법은 정확히 베시가 있는 곳으로 도달할 때까지 앞뒤로 움직이는 것입니다. 

앞뒤로 움직여 가며 찾는 데 가장 좋은 전략을 고안하기 위해 농부 존은 컴퓨터 과학 연구 문헌을 참고했는데, 그는 과거 컴퓨터 과학자가 이 문제와 똑같은 문제를 연구했을 뿐 아니라 이 문제가 "잃어버린 소 문제"로 불린다는 것에 흥미를 갖게 됐습니다. (사실입니다!)

문헌에 따르면 농부 존은 베시를 찾기 위해 x+1로 이동한 후, 방향을 바꿔 x-2로 이동하고, x+4로 이동하고, 이전 번 시작점에서 떨어진 거리의 2배만큼 시작점에서 떨어진 위치로 "지그재그" 패턴을 그리며 이동해야 합니다. 잃어버린 소 문제를 해결하기 위한 알고리즘 연구 문헌을 읽으면서, 그는 이 접근법이 최악의 경우 그가 베시를 찾기 전에 이동하는 거리가 현재 그와 베시의 거리인 |x - y|의 9배임을 보장한다는 것을 알게 됐습니다 (이 역시 사실이며, 이 값은 모든 접근의 최악 경우 중 가장 적은 값입니다.)

농부 존은 이것이 사실인지 확인하고 싶습니다. x와 y가 주어질 때, 그가 베시를 찾을 때까지 지그재그 탐색 접근을 사용할 경우 이동하는 총 거리를 계산합시다.

입력

한 줄에 공백으로 구분된 두 정수 x, y가 입력됩니다. 두 수 모두 0 ~ 1,000 사이의 수입니다.

출력

농부 존이 베시에게 도달할 때까지 이동하는 거리를 한 줄에 출력합니다.

댓글을 작성하려면 로그인해야 합니다.