[BOJ] 16953 - A → B

4967 ワード
greedy boj 学習ノート ラーニングコーディング テキストリンク
https://www.acmicpc.net/problem/16953
質問する
整数AをBに変えたいです.可能な演算は次の2つです.
  • 2を掛けます.
  • 1を数の一番右側に追加します.
    • AからBまでの演算の最大値を求める.
    入力
    第1行は、A、B(1≦Aしゅつりょく
    AをBに変換するために必要な演算の最大値に1を加算して出力します.作成できない場合は、-1を出力します.
    サンプルI/O
    入力
  • 例1 
    • 2 162
  • 例出力1 
    • 5
2 → 4 → 8 → 81 → 162
    入力
  • 例2 
    • 4 42
  • 例出力2 
    • -1
    入力
  • 例3 
    • 100 40021
  • 例出力3 
    • 5
    Solution
    #include <iostream>

using namespace std;

int main(){
    int A, B;
    cin >> A >> B;
    int answer = 0;
    while(1){
        if(A > B){
            cout << "-1\n";
            break;
        }
        if (A == B){
            cout << answer + 1 << '\n';
            break;
        }
        if (B % 2 == 0){
            B /= 2;
        }
        else if(B % 10 == 1){
            B--;
            B /=10;
        }
        else{
            cout << "-1\n";
            break;
        }
        answer++;
    }
}
    AがBより大きいと答えられないのは当然だ.演算時に答えの範囲を超えた場合があります.
    演算は全部で2つある.Aに2を掛けるか、Aの一番右側に1を追加します.この2つのことを反対に考えてみましょう.
    Bを2で割って、Bを1で割ったとき、あいつを飛ばします.この2つが可能かどうかをチェックしてもいいです.
    どうせ両者の一つだ.後者は2に分けられず,前者は1の位置に1があるはずがない.
    逆に追跡すると、最低限の状況になります.
    タイプスクリプト:タイプ狭まりの話
    マップを変換する