Informatica Online Judge

  잃어버린 소 [1992 / 07C8]

Time Limit(Test case) : 1000 (ms)
Number of users who solved : 21   Total Tried : 21


The Champion of this Problem (C++) : gs17003 - 0ms / 174byte
My Best Submission (C++) : N/A

[USACO]

Background

농부 존은 소중한 소(배시)를 잃어버려서 찾아야 한다!

다행히, 농장을 가로지르는 길이 1개뿐이고, 배시가 그 길 어딘가에 있다는 것을 알고 있다. 농장을 가로지르는 길의 각 위치에 번호를 매겼을 때, 농부 존은 x 위치에 있고, 배시는 y 위치에 있다.(당연히 존은 배시의 정확한 위치를 모른다.)

농부 존이 배시를 찾아낼 때까지 가장 짧게 움직여야 하는 거리는 $|x-y|$이다. 하지만, 날이 어두워져 어디에 있는지 보이지가 않는다. 그렇기 때문에 배시를 찾기 위해서는 길을 따라 양쪽 방향으로 왔다 갔다 할 수 밖에 없다.

가장 효과적으로 찾아낼 수 있는 전략을 알아내기 위해, 경기과학고에서 정보를 공부하는 학생들에게 상담을 했는데, 그 문제는 실제로 “잃어버린 소 찾기(Lost Cow Problem)”라고 불리는 문제였다.(진짜다!)

배시를 찾기 위해 추천되는 방법은 $x+1$위치로 먼저 이동을 한 후, 다시 반대 방향의 $x-2$위치로 움직이고, 그 다음에는 다시 $x+4$, ... 순서로 “지그재그” 패턴으로 이동하는 방법으로 출발점을 기준으로 이전에 움직였던 거리를 2배씩 늘려가며 반대방향으로 움직여 나가는 것이었다.

존은 “잃어버린 소 찾기” 문제를 해결할 수 있는 알고리즘을 살펴보다가, 이러한 방법으로는 최악의 경우에는 가장 짧은 거리 $|x-y|$의 9배 만큼 이동해야한다는 것을 알게 되었다.(이것도 사실이다. 9배 거리는 배시를 반드시 찾아낼 수 있는 전략의 최악의 경우에 대한 최소 거리이다.)

존은 이러한 결과를 검증해 보고 싶어졌다. 존과 배시의 위치 x, y 가 주어질 때, 위의 지그재그 전략으로 배시를 찾을 때까지 이동하는 거리를 계산해보자.

Input

존(x)과 배시(y)의 위치가 공백을 두고 입력된다.(0 <= x,y <= 1000)

Output

존이 배시를 찾을 때까지 움직인 거리를 출력한다.

IO Example

입력
3 6

출력
9

* 설명 : 처음 존이 3에서 4로 이동한다. 다음으로 4에서 1로 이동한다. 마지막으로 1에서 7까지 이동하던 도중 6에 있던 베시를 찾는다. 이 때 총 이동한 거리는 9이다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]