#include <iostream>
#include <string>
#include <vector>
#include <cassert>
using namespace std;
struct solver_t
{
solver_t(string const& a, string const& b, string const& c)
: lhs(a)
, rhs(b)
, res(c)
, subst(128, -1)
, used{}
{
cout << lhs << " + " << rhs << " == " << res << "\n";
}
string lhs;
string rhs;
string res;
vector<int> subst;
int used[10];
int to_number(string& s)
{
int ret = 0;
for (char c : s)
{
assert(subst[c] >= 0);
ret = ret * 10 + subst[c];
}
return ret;
}
void check_and_print()
{
int left = to_number(lhs);
int right = to_number(rhs);
int result = to_number(res);
if (left + right == result)
{
cout << left << " + " << right << " == " << result << "\n";
}
}
void for_each_subst(string& s, int cr, int depth)
{
char c = s[s.size() - depth];
for (int i = depth == s.size(); i < 10; ++i)
{
if (used[i]) { continue; }
subst[c] = i;
used[i] = true;
solve(cr, depth);
used[i] = false;
subst[c] = -1;
}
}
void solve(int cr = 0, int depth = 1)
{
if (depth > lhs.size() || depth > rhs.size() || depth > res.size())
{
check_and_print();
return;
}
char c = res[res.size() - depth];
if (subst[c] >= 0)
{
char a = lhs[lhs.size() - depth];
if (subst[a] >= 0)
{
char b = rhs[lhs.size() - depth];
if (subst[b] >= 0)
{
int sum = subst[a] + subst[b] + cr;
if (sum % 10 != subst[c]) { return; }
solve(sum / 10, depth + 1);
}
else
{
for_each_subst(rhs, cr, depth);
}
}
else
{
for_each_subst(lhs, cr, depth);
}
}
else
{
for_each_subst(res, cr, depth);
}
}
};
int main()
{
solver_t("send", "more", "money")
.solve();
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8c3RyaW5nPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8Y2Fzc2VydD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCnN0cnVjdCBzb2x2ZXJfdAp7Cglzb2x2ZXJfdChzdHJpbmcgY29uc3QmIGEsIHN0cmluZyBjb25zdCYgYiwgc3RyaW5nIGNvbnN0JiBjKQoJCTogbGhzKGEpCgkJLCByaHMoYikKCQksIHJlcyhjKQoJCSwgc3Vic3QoMTI4LCAtMSkKCQksIHVzZWR7fQoJewoJCWNvdXQgPDwgbGhzIDw8ICIgKyAiIDw8IHJocyA8PCAiID09ICIgPDwgcmVzIDw8ICJcbiI7Cgl9CgkKCXN0cmluZyBsaHM7CglzdHJpbmcgcmhzOwoJc3RyaW5nIHJlczsKCgl2ZWN0b3I8aW50PiBzdWJzdDsKCWludCB1c2VkWzEwXTsKCQoJaW50IHRvX251bWJlcihzdHJpbmcmIHMpCgl7CgkJaW50IHJldCA9IDA7CgkJZm9yIChjaGFyIGMgOiBzKQoJCXsKCQkJYXNzZXJ0KHN1YnN0W2NdID49IDApOwoJCQlyZXQgPSByZXQgKiAxMCArIHN1YnN0W2NdOwoJCX0KCQlyZXR1cm4gcmV0OwoJfQoKCXZvaWQgY2hlY2tfYW5kX3ByaW50KCkKCXsKCQlpbnQgbGVmdCA9IHRvX251bWJlcihsaHMpOwoJCWludCByaWdodCA9IHRvX251bWJlcihyaHMpOwoJCWludCByZXN1bHQgPSB0b19udW1iZXIocmVzKTsKCQkKCQlpZiAobGVmdCArIHJpZ2h0ID09IHJlc3VsdCkKCQl7CgkJCWNvdXQgPDwgbGVmdCA8PCAiICsgIiA8PCByaWdodCA8PCAiID09ICIgPDwgcmVzdWx0IDw8ICJcbiI7CgkJfQoJfQoKCXZvaWQgZm9yX2VhY2hfc3Vic3Qoc3RyaW5nJiBzLCBpbnQgY3IsIGludCBkZXB0aCkKCXsKCQljaGFyIGMgPSBzW3Muc2l6ZSgpIC0gZGVwdGhdOwoJCWZvciAoaW50IGkgPSBkZXB0aCA9PSBzLnNpemUoKTsgaSA8IDEwOyArK2kpCgkJewoJCQlpZiAodXNlZFtpXSkgeyBjb250aW51ZTsgfQoJCQkKCQkJc3Vic3RbY10gPSBpOwoJCQl1c2VkW2ldID0gdHJ1ZTsKCQkJCgkJCXNvbHZlKGNyLCBkZXB0aCk7CgkJCQoJCQl1c2VkW2ldID0gZmFsc2U7CgkJCXN1YnN0W2NdID0gLTE7CgkJfQoJfQoKCXZvaWQgc29sdmUoaW50IGNyID0gMCwgaW50IGRlcHRoID0gMSkKCXsKCQlpZiAoZGVwdGggPiBsaHMuc2l6ZSgpIHx8IGRlcHRoID4gcmhzLnNpemUoKSB8fCBkZXB0aCA+IHJlcy5zaXplKCkpCgkJewoJCQljaGVja19hbmRfcHJpbnQoKTsKCQkJcmV0dXJuOwoJCX0KCQkKCQljaGFyIGMgPSByZXNbcmVzLnNpemUoKSAtIGRlcHRoXTsKCQlpZiAoc3Vic3RbY10gPj0gMCkKCQl7CgkJCWNoYXIgYSA9IGxoc1tsaHMuc2l6ZSgpIC0gZGVwdGhdOwoJCQlpZiAoc3Vic3RbYV0gPj0gMCkKCQkJewoJCQkJY2hhciBiID0gcmhzW2xocy5zaXplKCkgLSBkZXB0aF07CgkJCQlpZiAoc3Vic3RbYl0gPj0gMCkKCQkJCXsKCQkJCQlpbnQgc3VtID0gc3Vic3RbYV0gKyBzdWJzdFtiXSArIGNyOwoJCQkJCWlmIChzdW0gJSAxMCAhPSBzdWJzdFtjXSkJeyByZXR1cm47IH0KCQkJCQlzb2x2ZShzdW0gLyAxMCwgZGVwdGggKyAxKTsKCQkJCX0KCQkJCWVsc2UKCQkJCXsKCQkJCQlmb3JfZWFjaF9zdWJzdChyaHMsIGNyLCBkZXB0aCk7CgkJCQl9CgkJCX0KCQkJZWxzZQoJCQl7CgkJCQlmb3JfZWFjaF9zdWJzdChsaHMsIGNyLCBkZXB0aCk7CgkJCX0KCQl9CgkJZWxzZQoJCXsKCQkJZm9yX2VhY2hfc3Vic3QocmVzLCBjciwgZGVwdGgpOwoJCX0KCX0KfTsKCmludCBtYWluKCkgCnsKCXNvbHZlcl90KCJzZW5kIiwgIm1vcmUiLCAibW9uZXkiKQoJCS5zb2x2ZSgpOwp9