[BOJ1011]Fly me to Alpha Centauri Python

1195 ワード
アルゴリズム#アルゴリズム# テキストリンク
1.問題リンク
質問リンク
2.試合前の計画と思考
以前にkを移動した場合,k−1,k,k+1に移動できる条件下で,数列の和式を用いることを決定した.惑星に着くために、まず移動距離を減らす場所がどこなのかを考えました.
全距離の平方根sqrt(距離)まで移動距離を徐々に増やし,その後移動距離を徐々に縮小し,惑星に到達する問題を解決した.
3.解答
n = int(input())

for _ in range(n):
    x, y = map(int, input().split())
    d = int((y-x-1)**0.5)
    if y-x > d*d+d:
        print(2*d+1)
    else:
        print(2*d)
4.問題を解くときに直面する困難と悩み
最初は次のように問題を解いた.
import math
for j in range(int(input())):
    x, y = map(int,input().split())
    n = int(math.sqrt(y-x))
    ans = 2*n - 1
    
    temp = y-x-n**2#가고 남은 거리
    i = n
    while temp != 0:
        if temp//i >= 0:
            ans += temp//i
            temp %= i
        i -= 1
        if i == 0:
            break
    
    print(ans)
移動開始直後の距離が減少した区間が最後の移動距離無条件1の条件であるため,whileゲートを用いて1に調整した.
点数をつけてからコードを見て、最後の移動が1の条件は、移動する距離をy-x+1に設定し、y-xではなくy-x+1にすれば解決できる問題です.
次に等差数列の和式を用いて移動距離を求め,移動距離がk(k+1)より大きい場合はさらに1回移動するようにコードを修正する.
5.解答して分かる概念と感じ
複文を回すのもよいが,数学的に演算回数を減らすことができる場合,既知の式を用いてすぐに解くことができる.
🔥 #10スプリング安全登録を行う
[AVA]22日目(収集フレーム/顧客/奇形器)