while ループ辞書の検索64ビット整数P0209

数字を並べて引き算を繰り返すと

0 以上 10^d 未満の整数 x から始めて、次のことを繰り返す。
今の数を前に 0 を補ってちょうど d 桁で書き、その数字を大きい順に並べた数から小さい順に並べた数を引く。
その差が次の数である。
例えば d = 4 なら、2111 は 2111 − 1112 = 999 になる。
999 は 0999 と書くので、9990 − 0999 = 8991 になる。
こうして得られる数を順に a0 = x、a1、a2、… とする。
前に 0 を補った d 桁の数は 10^d 個しかないので、いつかは前に出た数がまた出る。
前に出た数が初めてまた出たときを aj とし、その数が最初に出たときを ai（i < j）とする。
何ステップで終わるかは前もって分からないので、繰り返しは while 文で回す。
入力の行ごとに i、j − i、そしてサイクルをなす数 ai、a(i+1)、…、a(j−1) のうちいちばん小さい数を、一行に空白一つで区切って出力せよ。
いちばん小さい数は前に 0 を付けない普通の整数で出力する。

入力: 最初の行に T（1 ≤ T ≤ 1000）。
続く T 行に d と x（2 ≤ d ≤ 10、0 ≤ x < 10^d）。
x は前に 0 を付けずに与えられる。
出力: T 行。
各行 "i j−i 最小の数"

例 1 · stdin

stdout

main.py プログラミング言語実行バージョン

入力(stdin)

実行すると、これらの行が順に input()・標準入力に渡されます(実行中に入力を求めません)。

$ 準備完了

コードを入力して解くにはパソコンで開いてください。モバイルでは問題と解答を見られます。

ほかの言語では？言語別の解答を見る · 8 言語の解答

何回回るか分からない繰り返しは while です。
Python while a not in seen:、C・C++・Java・C#・JavaScript・TypeScript while (...)、Craykon 間 (条件) { }。
止める条件は「この数を前に見たか」で、数 → 最初に出たステップ番号を辞書に書いておけば i がすぐ分かります（Python dict、JS・TS Map、Java HashMap<Long, Integer>、C# Dictionary<long, int>、C++ std::map、Craykon 辞書() と 含む）。
C には辞書がありませんが、d ≤ 10 なら出てくる数は三十個を超えないので、配列を先頭からなめても十分です。
落とし穴は四つ：① 数を文字列にすると前の 0 が消えます。
0999 を三桁の 999 として扱うと 999 − 999 = 0 で終わってしまいます。
Python str(a).zfill(d)、JS・TS String(a).padStart(d, "0")、Java String.format("%0" + d + "d", a)、C# a.ToString().PadLeft(d, '0')、Craykon ("" + a).前埋め(d, "0") のように補うか、C のように % 10 でちょうど d 回取り出せば 0 も数えられます。
② d = 10 だと 9876543210 のように int（約 21 億）を超える数が出ます。
C・C++ は long long、Java・C# は long が必要で、Java の Integer.parseInt はそのような数で例外を出します。
Python の整数には大きさの限りがなく、JS・TS・Craykon の数は 2^53 まで正確なので、そのままで動きます。
③「すぐ前の数と同じなら止める」と書くと、6174 のようにその場にとどまる数でしか止まりません。
d = 2 では 09 → 81 → 63 → 27 → 45 → 09 のように五つの数が回るので、繰り返しが終わりません。
④ また出たときの j をステップ数として書きがちです。
聞かれているのはサイクルに入る前のステップ数 i です。

Pythonmain.py · 19 行

def step(a, d):    s = str(a).zfill(d)  # 앞에 0을 채워 꼭 d자리로    big = int("".join(sorted(s, reverse=True)))    small = int("".join(sorted(s)))    return big - small  t = int(input())for _ in range(t):    d, x = map(int, input().split())    first_seen = {}  # 수 → 처음 나온 걸음 번호    a, k = x, 0    while a not in first_seen:        first_seen[a] = k        a = step(a, d)        k += 1    i = first_seen[a]    loop = [v for v, at in first_seen.items() if at >= i]    print(i, k - i, min(loop))

JavaScriptmain.js · 28 行

const lines = require("fs").readFileSync(0, "utf8").trim().split("\n"); function step(a, d) {  const digits = String(a).padStart(d, "0").split(""); // 앞에 0을 채워 꼭 d자리로  digits.sort();  const small = Number(digits.join(""));  const big = Number(digits.reverse().join(""));  return big - small;} const t = Number(lines[0]);const out = [];for (let c = 1; c <= t; c++) {  const [d, x] = lines[c].trim().split(" ").map(Number);  const firstSeen = new Map(); // 수 → 처음 나온 걸음 번호  let a = x;  let k = 0;  while (!firstSeen.has(a)) {    firstSeen.set(a, k);    a = step(a, d);    k++;  }  const i = firstSeen.get(a);  let min = Infinity;  for (const [v, at] of firstSeen) if (at >= i) min = Math.min(min, v);  out.push(`${i} ${k - i} ${min}`);}console.log(out.join("\n"));

TypeScriptmain.ts · 29 行

import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").trim().split("\n"); function step(a: number, d: number): number {  const digits: string[] = String(a).padStart(d, "0").split(""); // 앞에 0을 채워 꼭 d자리로  digits.sort();  const small = Number(digits.join(""));  const big = Number(digits.reverse().join(""));  return big - small;} const t = Number(lines[0]);const out: string[] = [];for (let c = 1; c <= t; c++) {  const [d, x] = lines[c].trim().split(" ").map(Number);  const firstSeen = new Map<number, number>(); // 수 → 처음 나온 걸음 번호  let a = x;  let k = 0;  while (!firstSeen.has(a)) {    firstSeen.set(a, k);    a = step(a, d);    k++;  }  const i = firstSeen.get(a)!;  let min = Infinity;  for (const [v, at] of firstSeen) if (at >= i) min = Math.min(min, v);  out.push(`${i} ${k - i} ${min}`);}console.log(out.join("\n"));

JavaMain.java · 41 行

import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.HashMap;import java.util.Map; public class Main {    // 10자리 수(9,876,543,210)는 int(약 21억)를 넘어서 long으로 센다    static long step(long a, int d) {        char[] digits = String.format("%0" + d + "d", a).toCharArray(); // 앞에 0을 채워 꼭 d자리로        Arrays.sort(digits);        long small = Long.parseLong(new String(digits));        long big = Long.parseLong(new StringBuilder(new String(digits)).reverse().toString());        return big - small;    }     public static void main(String[] args) throws IOException {        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));        int t = Integer.parseInt(in.readLine().trim());        StringBuilder out = new StringBuilder();        for (int c = 0; c < t; c++) {            String[] p = in.readLine().trim().split(" ");            int d = Integer.parseInt(p[0]);            long a = Long.parseLong(p[1]);            Map<Long, Integer> firstSeen = new HashMap<>(); // 수 → 처음 나온 걸음 번호            int k = 0;            while (!firstSeen.containsKey(a)) {                firstSeen.put(a, k);                a = step(a, d);                k++;            }            int i = firstSeen.get(a);            long min = Long.MAX_VALUE;            for (Map.Entry<Long, Integer> e : firstSeen.entrySet())                if (e.getValue() >= i) min = Math.min(min, e.getKey());            out.append(i).append(' ').append(k - i).append(' ').append(min).append('\n');        }        System.out.print(out);    }}

C#Main.cs · 42 行

using System;using System.Collections.Generic;using System.Linq;using System.Text; class Program{    // 10자리 수(9,876,543,210)는 int(약 21억)를 넘어서 long으로 센다    static long Step(long a, int d)    {        char[] digits = a.ToString().PadLeft(d, '0').ToCharArray(); // 앞에 0을 채워 꼭 d자리로        Array.Sort(digits);        long small = long.Parse(new string(digits));        Array.Reverse(digits);        long big = long.Parse(new string(digits));        return big - small;    }     static void Main()    {        int t = int.Parse(Console.ReadLine().Trim());        var out_ = new StringBuilder();        for (int c = 0; c < t; c++)        {            string[] p = Console.ReadLine().Trim().Split(' ');            int d = int.Parse(p[0]);            long a = long.Parse(p[1]);            var firstSeen = new Dictionary<long, int>(); // 수 → 처음 나온 걸음 번호            int k = 0;            while (!firstSeen.ContainsKey(a))            {                firstSeen[a] = k;                a = Step(a, d);                k++;            }            int i = firstSeen[a];            long min = firstSeen.Where(e => e.Value >= i).Min(e => e.Key);            out_.Append($"{i} {k - i} {min}\n");        }        Console.Write(out_);    }}

C++main.cpp · 37 行

#include <algorithm>#include <iostream>#include <map>#include <string> // 10자리 수(9,876,543,210)는 int(약 21억)를 넘어서 long long으로 센다long long step(long long a, int d) {    std::string s = std::to_string(a);    s.insert(0, d - s.size(), '0'); // 앞에 0을 채워 꼭 d자리로    std::sort(s.begin(), s.end());    long long small = std::stoll(s);    std::reverse(s.begin(), s.end());    long long big = std::stoll(s);    return big - small;} int main() {    int t;    std::cin >> t;    while (t--) {        int d;        long long a;        std::cin >> d >> a;        std::map<long long, int> firstSeen; // 수 → 처음 나온 걸음 번호        int k = 0;        while (!firstSeen.count(a)) {            firstSeen[a] = k;            a = step(a, d);            k++;        }        int i = firstSeen[a];        long long min = -1;        for (const auto& [v, at] : firstSeen)            if (at >= i) { min = v; break; } // map은 작은 수부터 돈다        std::cout << i << ' ' << k - i << ' ' << min << '\n';    }}

Cmain.c · 40 行

#include <stdio.h> /* 10자리 수(9,876,543,210)는 int(약 21억)를 넘어서 long long으로 센다 */long long step(long long a, int d) {    int count[10] = {0};    for (int i = 0; i < d; i++) { /* 꼭 d번 떼어 내면 앞자리 0도 센다 */        count[a % 10]++;        a /= 10;    }    long long big = 0, small = 0;    for (int g = 9; g >= 0; g--)        for (int r = 0; r < count[g]; r++) big = big * 10 + g;    for (int g = 0; g <= 9; g++)        for (int r = 0; r < count[g]; r++) small = small * 10 + g;    return big - small;} int main(void) {    int t;    scanf("%d", &t);    while (t--) {        int d;        long long a;        scanf("%d %lld", &d, &a);        long long seen[64]; /* 나온 수를 차례대로(d ≤ 10이면 30개를 넘지 않는다) */        int k = 0, i = -1;        while (1) {            for (int s = 0; s < k; s++)                if (seen[s] == a) i = s;            if (i >= 0) break;            seen[k++] = a;            a = step(a, d);        }        long long min = seen[i];        for (int s = i; s < k; s++)            if (seen[s] < min) min = seen[s];        printf("%d %d %lld\n", i, k - i, min);    }    return 0;}

Craykonmain.cray · 40 行

// 한 걸음: 앞에 0을 채워 꼭 d자리로 쓰고, 큰 것부터 늘어놓은 수 − 작은 것부터 늘어놓은 수한걸음(a, d){    s = ("" + a).前埋め(d, "0");    digits = [];    それぞれ (ch の中 s)    {        digits.追加(ch);    }    digits.並べ替え();    small = digits.つなぐ("").数に();    digits.逆に();    big = digits.つなぐ("").数に();    返す big - small;} t = コンソール.行読み().空白除去().数に();繰り返す (c = 0; c < t; c++){    p = コンソール.行読み().空白除去().分ける(" ");    d = p[0].数に();    a = p[1].数に();    firstSeen = 辞書(); // 수 → 처음 나온 걸음 번호    order = []; // 나온 차례대로    k = 0;    間 (!firstSeen.含む(a))    {        firstSeen[a] = k;        order.追加(a);        a = 한걸음(a, d);        k += 1;    }    i = firstSeen[a];    least = order[i];    繰り返す (s = i; s < k; s++)    {        least = 数学.小さい方(least, order[s]);    }    コンソール.書く(i + " " + (k - i) + " " + least);}