P.107リモコン

1107リモコン
タイムアウトメモリコミット正解率2秒256 MB 61172145092122.441%
質問する
秀斌はテレビを見ています.秀斌はチャンネルを変えようとしたが、ボタンを強く押しすぎて、数字のボタンが壊れた.
リモコンのボタンは0から9まで数字+と-があります.クリックすると、現在表示されているチャンネルから+1チャンネルに移動し、-をクリックして-1チャンネルに移動します.チャンネル0で-を押すと、チャンネルはそのままで、チャンネルは無限大になります.
スビンが今移動するチャンネルはNです.ボタンに障害が発生した場合は、Nチャンネルに移動するには何回ボタンを押す必要があるかを尋ねるプログラムを作成します.
秀彬が今見ているチャンネルは100番です.
入力
第1行は、スビンが移動するチャンネルN(0≦N≦500000)を与える.2行目には、障害ボタンの個数M(0≦M≦10)が与えられる.障害が発生したボタンがある場合は、3行目に障害が発生したボタンが表示され、同じボタンは複数回表示されません.
しゅつりょく
チャネルNに移動するには、最初の行の出力で少なくとも何回ボタンを押す必要がありますか.
入力例1
5457
3
6 7 8
サンプル出力1
6
入力例2
100
5
0 1 2 3 4
サンプル出力2
0
入力例3
500000
8
0 2 3 4 6 7 8 9
サンプル出力3
11117
入力例4
100
3
1 0 5
サンプル出力4
0
入力例5
14124
0
サンプル出力5
5
入力例6
1
9
1 2 3 4 5 6 7 8 9
サンプル出力6
2
入力例7
80000
2
8 9
サンプル出力7
2228
コード#コード#

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

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

        int cur = 100;
        int tar = Integer.parseInt(br.readLine());
        int n = Integer.parseInt(br.readLine());

        if (n > 0) {
            int[] btn = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            int res;

            int min = Integer.MAX_VALUE;
            if (tar < 100) {
                while (cur >= 0) {
                    if (not_breakdown(cur, btn)) {
                        res = Math.abs(cur - tar) + ((Integer.toString(cur).length() > 100 - cur) ? 100 - cur : Integer.toString(cur).length());
                        min = (min > res) ? res : min;
                    }
                    else {
                        if (cur == tar) min = (min > 100 - cur) ? 100 - cur : min;
                    }
                    cur--;
                }
            } else if (tar == 100) min = 0;
            else {
                while (cur <= 999999) {
                    if (not_breakdown(cur, btn)) {
                        res = Math.abs(cur - tar) + ((Integer.toString(cur).length() > cur - 100) ? cur - 100 : Integer.toString(cur).length());
                        min = (min > res) ? res : min;
                    }
                    else {
                        if (cur == tar) min = (min > cur - 100) ? cur - 100 : min;
                    }
                    cur++;
                }
            }

            System.out.println(min);
        }
        else
            System.out.println((Integer.toString(tar).length() > Math.abs(tar - 100)) ? Math.abs(tar - 100) : Integer.toString(tar).length());
    }

    public static boolean not_breakdown(int cur, int[] btn) {
        int a, b;
        a = cur;

        if (a != 0) {
            while (a != 0) {
                b = a % 10;
                a /= 10;
                for (int i = 0; i < btn.length; i++) {
                    if (b == btn[i]) return false;
                }
            }
        }
        else {
            for (int i = 0; i < btn.length; i++) {
                if (a == btn[i]) return false;
            }
        }
        return true;
    }
}

コードの説明
0から99999999まで回転する方法を選びました.時間制限が2秒なので、他に考えがなく、ブルートフォースを使うことにしました.近い値+または-を選択する方法もあるが,時間制限に比べてコードが複雑になりすぎるため,この方法は選択されていない.
大きな条件は、障害ボタンの有無です.故障したボタンがない場合は、必要なtvチャンネルボタンを直接押して切り替えるか、標準点100の+または-ボタンで切り替えることができます.
故障したボタンがあれば、現在のチャンネルを変えて、そのチャンネル番号のボタンが故障しているかどうかを分けます.障害ボタンが含まれている場合は、+または-を100でしか押すことができません.障害ボタンがなければ、現在のボタンを押す回数と、現在のボタンが変更したいチャンネルとの違いを加算した値は、チャンネルを変更するためにボタンを押す個数です.
この方法でminを更新し,置換する.
交換したいチャンネルが現在のチャンネル(100)と同じであれば、特別な計算を必要とせずに直接0を出力する.