Docking Day

시간 제한2초메모리 제한2048 MB

요약
정수 항구에 놓인 세 척의 배를 목표 항구로 옮기는데, 한 번의 이동은 다른 배 정확히 한 척을 넘어야 하며 최소 이동 횟수를 구한다.
난이도

보통10점 중 7점

유형
그리디, 수학, 완전 탐색, 구현
정답자
아직 제출이 없습니다

문제

A space station has docking ports labeled by distinct positive integers 1,2,3,…1, 2, 3, \dots arranged in a straight line. Port 11 is the leftmost, and the line extends infinitely to the right. Three labeled ships—Red (RR), Green (GG), and Blue (BB)—are currently at different ports. Due to maintenance, traffic control must re-dock the three ships to newly assigned target ports. To keep clear sight lines and safe spacing during re-docking, the moving ship must pass over exactly one other ship—no more, no less. Specifically, traffic control wants to re-dock while satisfying these constraints:

  1. Each ship must end at its own target port.
  2. At any time, no two ships may occupy the same port.
  3. In one move, choose one ship and place it on an empty port so that exactly one of the other two ships has a port strictly between the old and new ports.

For example, suppose RR, GG, and BB are currently at ports 33, 44, 88 and their target ports are 33, 22, 1010, respectively. In three moves - (1) move GG from 44 to 99 (passing BB), (2) move BB from 88 to 1010 (passing GG), and (3) move GG from 99 to 22 (passing RR) - all three ships reach their targets. See the figures below.

Given the current ports and target ports of the three ships, write a program to compute the minimum number of moves required to re-dock them to the target ports.

입력

Your program is to read from standard input. The input starts with a line containing three distinct integers, r_1r\_1, g_1g\_1 and b_1b\_1 (1≤r_1,g_1,b_1≤1061 ≤ r\_1, g\_1, b\_1 ≤ 10^6), which denote the positions of the current ports of RR, GG, and BB, respectively. The following line contains three distinct integers, r_2r\_2, g_2g\_2 and b_2b\_2 (1≤r_2,g_2,b_2≤1061 ≤ r\_2, g\_2, b\_2 ≤ 10^6), which denote the positions of the target ports of RR, GG, and BB, respectively.

출력

Your program is to write to standard output. Print exactly one line. The line should contain the minimum number of moves required to re-dock them to the target ports.

예제2

  1. 예제 1

    입력
    3 4 8
    3 2 10
    
    예상 출력
    3
    
  2. 예제 2

    입력
    3 4 5
    6 2 1
    
    예상 출력
    3