AOJ 1180: Recurring Decimals
問題
Recurring Decimals | Aizu Online Judge
L桁の数字を並び替えて作れる数字の最大値と最小値の差で数列を作っていく。 数列に同じ数字が現れるのはいつか
方針
実際に並び替えて数列を作り、一つ作るたびに数列をチェックする
コード
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i, n) for(int i=0; i<(n); ++i) int strtoint(string s) { int n = 0; int digit = 1; for(int i=s.size()-1; i>=0; --i, digit*=10){ n += digit * (s[i]-'0'); } return n; } int main(void){ int a, L; char s[10]; int x, y; bool flag; vector<int> l; while(cin >> a >> L && (a || L)) { l.clear(); l.push_back(a); flag = false; int i = 0; while(true) { for(int k=L-1; k>=0; --k) { s[k] = a%10 + '0'; a /= 10; } s[L] = '\0'; sort(s, s+L); x = strtoint(s); sort(s, s+L, greater<char>()); y = strtoint(s); l.push_back(y-x); for(int j=0; j<i; ++j) { if(i > 0 && l[i] == l[j]) { cout << j << " " << l[i] << " " << i-j << endl; flag = true; } } if(flag) break; else { i++; a = y-x; } } } }
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1892123
反省
- 重複判定はmapでやるのがよかった