실행 시간 제한 | 메모리 제한 |
---|---|
2 초 | 512 MB |
철수는 농장에서 공놀이를 하다가 그가 아끼는 축구공을 잃어버려서 이를 찾고 싶습니다!
다행히도, 농장을 가로지르는 긴 길이 하나뿐이고, 철수는 축구공이 이 길의 어딘가에 있을 거라는 것을 압니다. 이 길을 숫자선으로 생각한다면, 철수는 현재 위치 에 있고 축구공은 위치 에 있습니다.(철수는 알지 못합니다). 만약 철수가 축구공의 위치를 알고 있다면, 거리 를 걸어 축구공의 위치로 직접 갈 수 있습니다. 하지만 밖은 어두워서 철수는 아무것도 볼 수 없습니다. 그가 축구공을 찾을 수 있는 유일한 방법은 축구공의 위치에 도달할 때까지 왔다갔다 걷는 것입니다.
왔다갔다 걷는 최선의 전략을 파악하려고 철수는 컴퓨터 과학 연구 문헌을 찾아보고 본 문제가 과거 컴퓨터 과학자들에 의해 연구되었을 뿐만 아니라 실제로 '잃어버린 소 문제'라고 불리는 것을 발견하게 되어 약간 놀라워합니다.
철수가 축구공을 찾기 위한 권장 솔루션은 위치 로 이동한 후 방향을 돌려 위치 로 이동하고, 그 다음 위치 로 이동하는 등 '지그재그' 패턴으로 이동하며, 각 단계에서 처음 시작 위치에서 두 배 더 멀리 움직입니다.그가 읽은 알고리즘 연구 논문에 의하면, 이 방법은 그가 축구공을 찾을 때까지 그와 축구공 사이의 직접 거리 의 9배를 최악의 경우 이동하게 됨을 보장합니다 (이것은 사실이며, 9라는 수치는 어떤 전략이든 달성할 수 있는 최소의 최악의 경우 보장입니다).
철수는 이 결과를 확인하려고 합니다. 주어진 와 를 가지고 그가 축구공을 찾을 때까지 위의 지그재그 검색 전략에 따라 이동할 총 거리를 계산해주세요.
한 줄의 입력은 두 개의 공백으로 구분된 서로 다른 정수 와 를 포함합니다. 둘 다 범위 내에 있습니다.
한 줄의 출력을 작성하십시오, 이는 철수가 축구공을 찾기 위해 이동할 거리를 포함합니다.
3 6
9
출처: USACO 2017 US Open Contest, Bronze Problem 1. The Lost Cow