POJ 3055 - Digital Friends

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

概要

同じ十進の数字からなる数同士を friends と呼ぶ． 例えば 123 と 32331313323213 は friends であり，123 と 22121221 は friends ではない．

片方の数の隣合った2つの数字を変えることで friends になるような数同士で，かつ friends でないものを almost friends と呼ぶ． ここで「変える」というのは，隣り合った2つの数字を a, b とすると，それを a-1 と b+1 あるいは a+1 と b-1 にすることとする． ただし，変えた結果の数字が 0 から 9 の範囲に収まっており，かつ leading zero を作らないときに限る．

例えば 04 を 13 に変えることで friends になるため 123 と 2223042 は almost friends である．

与えられた2つの数 x, y が friends か almost friends かそのいずれでもないかを答える．

制約

• 0 < x, y < 10^100

解法

やるだけ．

 1 #include <iostream>
 2 using namespace std;
 3 
 4 bool ok(const int *a, const int *b)
 5 {
 6   for (int i = 0; i < 10; i++) {
 7     if ((a[i] == 0) != (b[i] == 0)) {
 8       return false;
 9     }
10   }
11   return true;
12 }
13 
14 void countup(int *a, const string& s)
15 {
16   for (string::const_iterator it = s.begin(); it != s.end(); ++it) {
17     ++a[*it-'0'];
18   }
19 }
20 
21 bool friends(const string& x, const string& y)
22 {
23   int a[10] = {0}, b[10] = {0};
24   countup(a, x);
25   countup(b, y);
26   return ok(a, b);
27 }
28 
29 bool almost_friends(const string& x, const string& y)
30 {
31   int a[10] = {0}, b[10] = {0};
32   countup(a, x);
33   countup(b, y);
34 
35   for (string::const_iterator it = x.begin(); it != x.end() && it+1 != x.end(); ++it) {
36     const int s = *it-'0';
37     const int t = *(it+1)-'0';
38     if (s < 9 && t > 0) {
39       --a[s];
40       --a[t];
41       ++a[s+1];
42       ++a[t-1];
43       if (ok(a, b)) {
44         return true;
45       }
46       ++a[s];
47       ++a[t];
48       --a[s+1];
49       --a[t-1];
50     }
51     if (s > 0 && t < 9 && !(s == 1 && it == x.begin())) {
52       --a[s];
53       --a[t];
54       ++a[s-1];
55       ++a[t+1];
56       if (ok(a, b)) {
57         return true;
58       }
59       ++a[s];
60       ++a[t];
61       --a[s-1];
62       --a[t+1];
63     }
64   }
65   return false;
66 }
67 
68 int main()
69 {
70   int T;
71   cin >> T;
72   while (T-- > 0) {
73     string x, y;
74     cin >> x >> y;
75     if (friends(x, y)) {
76       cout << "friends" << endl;
77     } else if (almost_friends(x, y) || almost_friends(y, x)) {
78       cout << "almost friends" << endl;
79     } else {
80       cout << "nothing" << endl;
81     }
82   }
83   return 0;
84 }