아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

단짝 친구

시간 제한1초메모리 제한128 MB

요약
삼각형으로 쌓인 원들에 매겨진 두 번호가 주어지면 인접한 원으로 이동하는 최소 횟수를 구합니다.
난이도

보통10점 중 5점

유형
BFS, 그래프, 수학
정답자
아직 제출이 없습니다

문제

페티와 패티는 단짝 친구인데, 미로에 갇혔다. 미로에는 크기가 같은 원이 무한히 많고, 삼각형 모양으로 빈틈없이 놓여 있다. 맨 윗줄에 원이 1개, 둘째 줄에 2개 있고, rr번째 줄에는 rr개 있다. 이웃한 두 줄은 반 칸씩 어긋나 있어서, 원 하나는 같은 줄에서 양옆에 있는 원과 맞닿고 바로 아랫줄에 있는 원 2개와도 맞닿는다. 번호는 줄 단위로 왼쪽에서 오른쪽으로 매긴다.

         1
       2   3
     4   5   6
   7   8   9  10
11  12  13  14  15

페티와 패티는 각각 원 하나에 서 있고, 두 원이 같을 수도 있다. 페티는 한 번에 지금 서 있는 원에서 맞닿은 원으로 옮겨 간다. 두 원은 한 점이라도 공유하면 맞닿은 것이다.

처음에 페티와 패티가 서 있는 원의 번호가 주어진다. 페티가 친구에게 가는 데 필요한 최소 이동 횟수를 구하라.

입력

입력은 여러 테스트 케이스로 이루어진다. 각 줄에는 페티가 서 있는 원의 번호 aa와 패티가 서 있는 원의 번호 bb가 공백을 사이에 두고 주어진다. 두 번호 모두 1000010000을 넘지 않는다 (1≤a,b≤100001 \le a, b \le 10000).

마지막 줄은 0 0이다. 입력의 끝을 뜻하며 테스트 케이스가 아니다.

출력

ii번째 테스트 케이스의 답을 출력의 ii번째 줄에 정수 하나로 출력한다. 답은 페티가 친구에게 가는 데 필요한 최소 이동 횟수다.

예제2

  1. 예제 1

    입력
    1 3
    2 6
    23 9
    0 0
    
    예상 출력
    1
    2
    4
    
  2. 예제 2

    입력
    1 1
    4 4
    2 3
    1 2
    0 0
    
    예상 출력
    0
    0
    1
    1