Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

没有用递归,纯数学算法。我觉得能看懂的 是强人。

Posted by dxacm at 2010-06-11 08:46:51 on Problem 1117
#include <iostream>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <list>

using namespace std;

class ADB {
public:
    int A, D, B;
    int I;
public:
    ADB(){}
    ADB(int a, int d, int b, int i) : A(a), D(d), B(b), I(i) {}
    ADB(const ADB& adb) {
        A = adb.A;
        D = adb.D;
        B = adb.B;
        I = adb.I;
    }
    int add1() const {
        return (A * 10 + D) * I + B;
    }
    int add2() const {
        return A * I + B;
    }
    int sum() const {
        return add1() + add2();
    }
    bool operator<(const ADB& b) const {
        return this->add1() < b.add1();
    }
    bool operator==(const ADB& b) const {
        return this->add1() == b.add1();
    }
    int w() {
        return (int)log10(I);
    }
};

int main() {
    int number;
    while (cin >> number) {
        vector<ADB> result;
        if (number % 2 == 0) {
            for (int i = 10; i <= number; i *= 10) {
                {
                    int a11d = number / i;
                    int a = a11d / 11;
                    int d = a11d % 11;
                    if (d != 10) {
                        int b = (number - i * (11 * a + d)) / 2;
                        ADB t(a, d, b, i);
                        if (t.add1() + t.add2() == number && t.add1() != t.add2()) {
                            result.push_back(t);
                        }
                    }
                }
                {
                    int a11d = number / i - 1;
                    int a = a11d / 11;
                    int d = a11d % 11;
                    if (d != 10) {
                        int b = (number - i * (11 * a + d)) / 2;
                        ADB t(a, d, b, i);
                        if (t.add1() + t.add2() == number && t.add1() != t.add2()) {
                            result.push_back(t);
                        }
                    }
                }
            }
        }
        {
            int a = number / 11;
            int d = number % 11;
            if (d != 10) {
                result.push_back(ADB(a, d, 0, 1));
            }
        }
        sort(result.begin(), result.end());
        vector<ADB>::iterator end = unique(result.begin(), result.end());
        result.resize(end - result.begin());
        cout << result.size() << endl;
        for (vector<ADB>::iterator it= result.begin(); it != end; it++) {
            cout << (*it).add1() << " + "
                 << setfill('0') << setw((*it).w())
                 << (*it).add2() << " = "
                 << (*it).sum() << endl;
        }
    }
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator