[1011] Fly me to the Alpha Centauri

1011번: Fly me to the Alpha Centauri

 

분석

이동해야 하는 거리

• n의 제곱보다 작거나 같을 때 공간이동 작동 횟수 = n * 2 - 1
• n의 제곱보다 클 때공간이동 작동 횟수 = n * 2

거리	경로	N	N²	공간이동 작동횟수	반복횟수
1	1	1	1	1	1
2	11	1	1	2	1
3	111	2	4	3	2
4	121	2	4	3
5	1211	2	4	4	2
6	1221	2	4	4
7	12211	3	9	5	3
8	12221	3	9	5
9	12321	3	9	5
10	123211	3	9	6	3
11	123221	3	9	6
12	123321	3	9	6
13	1233211	4	16	7	4
14	1233221	4	16	7
15	1233321	4	16	7
16	1234321	4	16	7
17	12344321	4	16	8	4
18	12343221	4	16	8
19	12343321	4	16	8
20	12344321	4	16	8

 

 

풀이

"""
이전 작동시기에 k광년을 이동하였을 때는 k-1 , k 혹은 k+1 광년만을 다시 이동할 수 있다
처음 작동시킬 경우 1 광년을 이동할 수 있으며, 그 다음에는 0(1-1) , 1(1) , 2(1+1) 광년을 이동, 2광년을 이동한다면 다음 시기엔 1(2-1), 2(2), 3(2+1) 광년을 이동
x지점에서 y지점을 향해 최소한의 작동 횟수로 이동
스트케이스의 개수 T가 주어진다. 각각의 테스트 케이스에 대해 현재 위치 x 와 목표 위치 y 가 정수로 주어지며, x는 항상 y보다 작은 값을 갖는다
하지만 y지점에 도착해서도 공간 이동장치의 안전성을 위하여 y지점에 도착하기 바로 직전의 이동거리는 반드시 1광년으로 하려 한다.
3
0 3
1 5
45 50
"""
import math

T = int(input())
for i in range(T):
    s, e = map(int, input().split())
    length = e-s

    n = round(math.sqrt(length))

    while True:
        if length<=n**2:
            print(2*n-1)
            break
        else:
            print(2*n)
            break