[01011] Fly me to the Alpha Centauri

[01011] 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 < 231)

しゅつりょく

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

コード#コード#

#include <iostream>

using namespace std;

int main() {
	// T : testcase
    // x, y : 출발, 도착 좌표
    // dist : x, y사이의 거리
    // cnt : 장치 작동 횟수
    int T, x, y, dist, cnt;

    scanf("%d", &T);

    for(int i = 0; i < T; i++) { // T만큼 반복
        scanf("%d%d", &x, &y);
        dist = y - x;
        cnt = 0;
        // 앞뒤로 1씩 증가한 값 만큼씩 이동
        for(int j = 1;; j++) {
            dist -= j;
            cnt++;
            if(dist < j) break;
            dist -= j;
            cnt++;
            if(dist < j) break;
        }
        if(dist > 0) cnt++;
        printf("%d\n", cnt);
    }
}

追加の説明

ちょっと考えると簡単な問題です.
最短にするには、できるだけ大きな数字を多く使う必要がありますが、使える大きな数字は前後から1に戻る大きさの数字でなければなりません.
したがって,前後にそれぞれ1を増やし,真ん中に最大の数字を用い,このときの残りの距離が0でなければ,最大の数字より小さい数字はいずれも適当な場所に置くことができるので,cntに1を加えながらcntを出力する.
ソース:https://www.acmicpc.net/problem/1011