白駿1011 Fly me to 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点に正確に移動するために必要な空間移動装置の操作回数の最高値を作成してください.

コード#コード#

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    public static void calculate(String s){
        StringTokenizer st=new StringTokenizer(s);
        int remain=-Integer.parseInt(st.nextToken())+Integer.parseInt(st.nextToken());
        long current=1;
        int next=2;
        int count=1;
        if(remain==1){
            System.out.println(1);
            return;
        }

        while(true){
            current+=2*next-1;
            count+=2;
            next++;

            if(current<remain)
                continue;
            else if(current==remain)
                break;
            else{
                if(current-(next-1)>=remain){
                    count--;
                    break;
                }
                else
                    break;
            }
        }

        System.out.println(count);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n=Integer.parseInt(br.readLine());
        String[] tCase=new String[n];
        for(int i=0; i<n; i++)
            tCase[i]=br.readLine();

        for(String s:tCase)
            calculate(s);
    }
}

ソリューション

の優先条件を満たす中で、宇宙船の移動を想像しました.最小限の回数で移動するには、1,2,3,4...4 3 2 1そうするこのため、

1、

、

1、2、

、

1、2、

は、両点間の距離(rese)が等しくなるか大きくなるまで電流値を徐々に増加させていく.current=reseの場合、current>reseの場合ではなく、すぐに戻ります.上記から現在値を増加させると、各フェーズの差は次の中間数(next)+次の中間数-1(next-1)となる.現在のcurrent値は小さくする必要があるため、次の中間数(next)に入ることはできず、最大で次の中間数-1(next-1)に入ることができます.

1、2、3、1(X)

1、2、2、1(O)

1、2、2(O)

ビットの例は、2つに分類される.1つ目は1、2、2、1または1、2、1、1であり、このように中間の数が1つしかない場合、このときの電流は前段階の電流より1~next差がある.2つ目は1,2,2,1,2,1,2,1,1,1,1,このように中間の数が2つの場合、このときの電流は前の段階の電流よりも劣る(next+1)~(2*next).そこで,reseより大きくなったcurrentからnextを減算した値とreseを比較し,どちらの場合であるかを判断し,1回減算するか,直接返すかを決定する.

タイムアウト(問題のyの範囲は最大2^31-1、int型電流がこの値を超えると負)

.

長電流データ変換

が間違っています!(半例:reseが1の場合count出力は2)

残=1の場合の例外処理

😁