POJ 1117 - Pairs of Integers

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

概要

\(X + Y = N\) であり、\(Y\) が \(X\) から一つの数字を消して得られるような非負整数の組 \(X, Y\) をすべて答える。 出力は \(X\) について昇順で行う。

制約

• \(10 \le N \le 10 ^ 9\)

解法

• \(X\) から1の位の数字を消して \(Y\) が得られる場合。このとき \(X = 10a + b\) とすると \(Y = a\) で、\(X + Y = 11a + b = N \quad (0 \le b \le 9)\) の解が答え。
• 1の位の数字は \(X, Y\) で一致している場合。このとき \(N = 10a + b\) とすると \(X, Y\) の1の位の数字は \(b, b+5\) の2通りで、それぞれ再帰的に \(N = a, N = a-1\) の部分問題を解くことで答えが得られる。

 1 #include <iostream>
 2 #include <sstream>
 3 #include <vector>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 string to_s(int n)
 8 {
 9   ostringstream oss;
10   oss << n;
11   return oss.str();
12 }
13 
14 vector<pair<int,string> > solve(int N)
15 {
16   if (N <= 0) {
17     return vector<pair<int,string> >();
18   }
19   vector<pair<int,string> > ans;
20   for (int b = 0; b < 10 && N-b >= 0; b++) {
21     const int a11 = N-b;
22     if (a11 % 11 == 0) {
23       const int a = a11 / 11;
24       if (a == 0) {
25         ans.push_back(make_pair(10*a+b, ""));
26       } else {
27         ans.push_back(make_pair(10*a+b, to_s(a)));
28       }
29     }
30   }
31   const int x = N%10;
32   if (x % 2 == 0) {
33     const int y = x/2, z = x/2+5;
34     const string yy = to_s(y), zz = to_s(z);
35     const vector<pair<int,string> > t = solve(N/10), s = solve(N/10-1);
36     for (vector<pair<int,string> >::const_iterator it = t.begin(); it != t.end(); ++it) {
37       ans.push_back(make_pair(10*it->first + y, it->second + yy));
38     }
39     for (vector<pair<int,string> >::const_iterator it = s.begin(); it != s.end(); ++it) {
40       ans.push_back(make_pair(10*it->first + z, it->second + zz));
41     }
42   }
43   return ans;
44 }
45 
46 int main()
47 {
48   int N;
49   cin >> N;
50   vector<pair<int,string> > ans = solve(N);
51   sort(ans.begin(), ans.end());
52   ans.erase(unique(ans.begin(), ans.end()), ans.end());
53   cout << ans.size() << endl;
54   for (vector<pair<int,string> >::const_iterator it = ans.begin(); it != ans.end(); ++it) {
55     cout << it->first << " + " << it->second << " = " << N << endl;
56   }
57   return 0;
58 }