Farmer John은 자신의 상금 소인 베시(Bessie)를 잃어버렸고, 그녀를 찾아야 합니다!

다행히도, 농장을 가로질러 이어지는 하나의 긴 길만 존재하고, Farmer John은 베시가 반드시 그 길 어딘가에 있다는 것을 알고 있습니다.

그 길을 숫자선이라고 생각하면, Farmer John은 현재 위치 x에 있고, 베시는 현재 위치 y에 있습니다(이 값은 Farmer John이 알지 못합니다).

만약 Farmer John이 베시가 어디에 있는지 알기만 한다면, 그는 곧바로 그녀에게 걸어가서 |x - y| 만큼의 거리를 이동하면 됩니다.

하지만, 밖은 어둡고 Farmer John은 아무것도 볼 수 없습니다.

그가 베시를 찾을 수 있는 유일한 방법은 결국 그녀의 위치에 도달할 때까지 왔다 갔다 걸어 다니는 것입니다.

왕복하며 걷는 가장 좋은 전략을 알아내기 위해, Farmer John은 컴퓨터 과학 연구 문헌을 찾아보았고,
이 정확한 문제가 과거 컴퓨터 과학자들에 의해 연구되었을 뿐만 아니라
실제로 “잃어버린 소 문제(Lost Cow Problem)”라고 불린다는 사실을 알고 다소 재미있어 합니다(이것은 실제 사실입니다!).

Farmer John이 베시를 찾기 위해 추천되는 해결 방법은, 먼저 위치 x+1로 이동한 뒤 방향을 바꿔 x-2로 이동하고,
그 다음 x+4로 이동하는 식으로, 초기 위치에서의 거리(편차)를 매번 이전보다 두 배씩 늘려 가며 “지그재그” 형태로 움직이는 것입니다.

그는 잃어버린 소 문제를 해결하는 알고리즘을 공부하면서, 이 방법이 최악의 경우 자신과 베시 사이의 직접 거리 |x-y|의 9배만큼만 이동하면
반드시 베시를 찾을 수 있다는 것을 읽었습니다(이것 역시 사실이며, 9라는 값은 어떤 전략으로도 보장할 수 있는 최솟값입니다).

Farmer John은 이 결과를 확인해 보고자 합니다. x와 y가 주어질 때, 위에서 설명한 지그재그 탐색 전략을 따를 때 그가 베시를 찾기까지 이동하게 되는 총 거리를 계산하십시오.

#4030 upload 7 done 3 how_to_reg 3

The Lost Cow timer 2s memory 512MB

#4030

The Lost Cow 2s 512MB