AOJ 1180: 繰り返す10進数 / Recurring Decimals

競技プログラミング AOJ ICPC

問題

問題文

問題概要

非負の整数 a_0 と桁数 L が与えられる. 以下の規則を適用し, a_i から a_{i+1} をつくる.

  • 整数 a_i を 10進表記し, 桁が足りない場合は上位の桁を0埋めする.
  • 各桁の数字を並び替えてできる数字のうち, 最大のものから最小のものを引いた値を a_{i+1} とする.

このとき a_i = a_j (i > j) を満たす. 最小の i を求め, そのときの [j, a_i, i-j] の値を出力せよ.

ただし, i は20を超えないと仮定して良い.

解答例

指針

  • やるだけ

解説

iが20を超えないことが保証されているので, 重複する値が出るまで a_0 から順に a_1, a_2, ... と求めていけばいい.

重複しているかどうかの判定は std::map などの連想配列を使う. 今回は i が非常に小さいので, std::vector などに値を保持して, 毎回 O(N) の探索をして, 重複しているかを調べても十分間に合う.

std::map を使って重複を判定するには std::map::find を使う.

なお, a_i から a_{i+1} を求めるには, a_i を数値から文字列に変換すると実装が楽になる.

数値 -> 文字列 (int -> string) の変換は C++11 以降では, std::to_string が使える.

文字列 -> 数値 (string -> int) の変換は C++ 11 以降では, std::stoi が使える.

C++11以前の古いコンパイラを使っている場合は, char[] を一度経由して変換する.

数値 -> 文字列 (int -> string) の変換は, 数値を sprintf などで, char[] 形式の文字列に変換したあと, string でキャストすればいい.

文字列 -> 数値 (string -> int) の変換は, 文字列を string のメンバ関数である c_str() で char[] 形式の文字列に変換したあと, atoi() などで数値に変換すればいい.

#include <algorithm>
#include <iostream>
#include <string>
#include <map>

using namespace std;

int main() {
  int a, l;
  while (cin >> a >> l) {
    if (a == 0 && l == 0) { break; }

    map<int, int> mp;
    int i = 0;

    while (true) {
      if ( mp.find(a) != mp.end() ) {
        cout << mp[a] << " " << a << " " << i-mp[a] << endl;
        break;
      }
      mp[a] = i++;
      // int -> string 変換 (C++11以降から使用可)
      string s = to_string(a);
      int len = s.length();
      // 0埋め
      for (int i = 0; i < l-len; i++) {
        s = "0" + s;
      }
      int big, little;
      sort( s.begin(), s.end(), greater<char>() );
      big = stoi(s);
      sort( s.begin(), s.end() );
      little = stoi(s);
      // aの値を更新
      a = big-little;
    }
  }

  return 0;
}

#!/usr/bin/env python3

while True:
    a, l = map(int, input().split())
    if a == 0 and l == 0: break

    d, i = {}, 0
    while True:
        if d.get(a) != None:
            print(d[a], a, i-d[a])
            break
        d[a] = i; i += 1
        s = str(a)
        s = "0"*(l-len(s)) + s

        big = int( "".join( sorted(s, reverse=True) ) )
        little = int( "".join( sorted(s) ) )

        a = big-little