Backjun-1011(Python)-Fly me to Alpha Centauri

Fly me to the Alpha Centauri

質問する

ウヒョンは小さい頃、地球以外の他の惑星でも人類が生き残ることができると信じていた.そして、彼が地球という世界に足を踏み入れてから23年後の今日、世界で最も若いASNA宇宙飛行士となり、新しい世界に足を踏み入れる光栄な時を待っています.
彼が乗る宇宙船には、アルファCentauriという新しい人類の家を切り開くための大規模な生活維持システムが搭載されているため、その巨大なサイズと品質を理由に、最新技術の力を総合的に運用して開発された宇宙移動装置が搭載されている.しかし、このような空間移動装置の欠点は、移動距離が急激に増加すると、機械に深刻な欠陥が生じ、従来の作業時期にk光年を移動する際にk−1、kまたはk+1光年で再移動できることである.例えば、この装置を初めて起動すると、理論的には−1,0,1光年移動できるが、実際には負またはゼロ距離移動は意味がないので、1光年移動し、その後0,1,2光年移動することができる.△ここでさらに2光年移動すれば、次の時期に1、2、3光年移動できる.

金氏は、空間移動装置の起動時のエネルギー消費が大きいことをよく知っているので、x点からy点への移動が最も少ない起動回数を考えている.しかしながら、y点に到達しても、空間移動装置の安全性を確保するためには、y点に到達するまでの移動距離は1光年でなければならない.
キム・ウヒョンのために、x点からy点に正確に移動するために必要な空間移動装置の操作回数の最高値を作成してください.

入力

入力された第1行は、試験例の個数Tを与える.各テストケースについて、現在の位置xとターゲット位置yは整数であり、xは常にyより小さい.(0 ≤ x < y < 2**31)

しゅつりょく

各テストキャビネットについて、x点からy点まで正確に到達するために必要な最小空間移動装置の操作回数を出力する.

コード#コード#

移動距離は1つの格子しか増加または減少できません.

の条件下で、最後の移動距離は1に固定されるべきである.

したがって,移動距離は放物線の形でしか現れない.

検索ルール

移動履歴最小移動回数区間事例111①距離が4未満の区間21-12①距離が4未満の区間31-1-13①距離が4未満の区間41-2-13(2+2)-1②距離が平方数の区間51-2-1-14(2*2)③距離が(平方数+平方根)未満または区間6(4+2)1-2-14に等しい距離が(平方数+平方根)に等しい区間71-2-2-1-15(2*2)+1④距離が(平方数+平方根)より大きい区間81-2-2-15④距離が(平方数+平方根)より大きい区間91-2-3-2-15(3*2)-1②距離が平方数の区間101-2-3-2-16(3*2)③距離が(平方数+平方根)より小さいか、区間111-2-3-3-3-3-3-3-3-3-3-3-3-3-3-3-3-3-3(平方数+平方根)以下または区間12(9+3)1-2-3-2-16③距離が(平方数+平方根)未満または区間131-2-3-2-117(3*2)+1④距離が(平方数+平方根)区間141-2-3-2-2-17-17距離が(平方数+平方根)区間151-2-3-2-17距離が(平方数+平方根)区間151-2-3-3-3-3-2-17(平方根)より大きいより大きな区間161-2-3-4-3-2-17(4*2)-1②距離が平方数の区間

4つのケース区間に分けられるルールを見つけることができます。

1から3までの距離はルールを探さなくてもいいです。(距離=最小移動回数)

入力値間の距離に応じて、繰返しモードでどの区間に属するかを決定し、最小移動回数を得ることができる。

に答える

import math

N = int(input())

count = 0  # 최소 작동 횟수
result = []

for _ in range(N):
    a, b = map(int, input().split())
    distance = b - a    # 주어진 값들간의 거리

    num = math.floor(math.sqrt(distance))  
    # 주어진 값들 사이의 거리에 루트를 씌운다. (제곱근)
    # floor 함수를 사용하여 내림 처리 (정수로 만들기 위해)
    
    num_jegob = num**2                
    # 정수를 제곱근으로 갖는 제곱수 (ex. 9 -> 9의 제곱근은 3)

    if distance == num_jegob:   # 거리가 제곱수인 구간
        count = (num*2)-1

    elif num_jegob < distance <= num_jegob + num:   # 거리가 (제곱수 + 제곱근)보다 작거나 같은 구간
        count = (num*2)

    elif (num_jegob + num) < distance:   # 거리가 (제곱수 + 제곱근)보다 큰 구간   
        count = (num*2) + 1

    elif distance < 4:       # 거리가 4보다 작은 구간
        count = distance
    result.append(count)


for x in result:
    print(x)

放物線を描くことから解答のヒントを得た.1, 2, 3, 4, 5... 放物線の先端,すなわち移動回数の中で最も高い数と距離の相関関係から,区間別の特殊性を見つけてこそ解決できる二乗根であることがわかる.