POJ 1350 - Cabric Number Problem

http://poj.org/problem?id=1350

概要

4桁の数字で，すべての位の数字が同じというわけではない数に対して，以下の処理を繰り返すと 0 か 6174 に収束する． このとき，収束するまでの過程を出力する． もし前提を満たしていないときは「No!!」とだけ出力する．

• 数字を並び換えてできる数のうち最も大きな値を x とする．
• 数字を並び換えてできる数のうち最も小さな値を y とする．0 を含んでいた場合，y は4桁未満の数になりうる点に注意．
• x - y が新しい数字である．

制約

特になし

解法

やるだけ．

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 static const int K = 6174;
 6 
 7 pair<int,int> f(int N)
 8 {
 9   int a[4];
10   int d = 0;
11   for (; d < 4 && N != 0; d++) {
12     a[d] = N%10;
13     N /= 10;
14   }
15   sort(a, a+d);
16   int x = 0, y = 0;
17   for (int i = 0; i < d; i++) {
18     x = 10*x + a[d-i-1];
19     y = 10*y + a[i];
20   }
21   return make_pair(x, y);
22 }
23 
24 int main()
25 {
26   int N;
27   while (scanf("%d", &N) != EOF && N != -1) {
28     printf("N=%d:\n", N);
29     if (N/1000 > 0 && N/10000 == 0) {
30       pair<int,int> r = f(N);
31       if (r.first == r.second) {
32         puts("No!!");
33       } else {
34         int c = 0;
35         while (N != 0 && N != K) {
36           r = f(N);
37           printf("%d-%d=%d\n", r.first, r.second, r.first-r.second);
38           N = r.first - r.second;
39           c++;
40         }
41         printf("Ok!! %d times\n", c);
42       }
43     } else {
44       puts("No!!");
45     }
46   }
47   return 0;
48 }