ぱーぽーの競プロ記

競技プログラミングに関することを書きます。

AOJ 1180 Recurring Decimals

問題文はこちら
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1180&lang=jp


・概要
数字を並び替えたり、引き算したりする問題です。
説明しにくいので各自問題文を読みましょう。


・解法
やるだけ問題です。

文字列の扱いに注意しながら、実装していけばよいです。
string型をint型にしたりその逆をしたりするので、文字列の扱いに慣れてない人は少し苦労するかもしれません。
今までに出てきた数字はマップに保存させておくとよいです。


ソースコード

#include<iostream>
#include<string>
#include<map>
#include<algorithm>
#include<sstream>
using namespace std;

string a;
int l;
map<int,int>table;

int convert(string s){
   int res = 0;
   for(int i = 0 ; i < s.size() ; i++){
      res = res*10 + (int)((char)s[i] - '0');
   }
   return res;
}
   
int main(){
   while(cin >> a >> l){
      if(a=="0" && l==0)break;
      
      table.clear();
      while(a.size() < l)a = "0" + a;
      table[convert(a)] = 0;
      
      for(int i = 1 ; ; i++){
	 sort(a.rbegin(), a.rend());
	 int maxV = convert(a);
	 sort(a.begin(), a.end());
	 int minV = convert(a);
	 int tmp = maxV - minV;
	 
	 if(table.find(tmp)==table.end()){
	    table[tmp] = i;
	    stringstream ss;
	    ss << tmp;
	    a = ss.str();
	    while(a.size() < l)a = "0" + a;
	 }
	 else{
	    cout << table[tmp] << " " << tmp << " " << i - table[tmp]<< endl;
	    break;
	 }
      }
   }
   return 0;
}