#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <limits.h>
void pis(int *is, int size) {
int i;
for (i
= 0; i
< size
; i
++) printf("%d ", is
[i
]); }
int fact(int n) {
int i, fact = 1;
for (i = 1; i <= n; i++) fact *= i;
return fact;
}
int count_permutations(int n, int r) {return fact(n) / fact(n - r);}
int count_combinations(int n, int r) {return count_permutations(n, r) / fact(r);}
struct nruis {int n, r, size, cap, *is; unsigned int *uis;};
void push_int(struct nruis *p, int value) {
if (p && p->size + 1 <= p->cap) p->uis[p->size++] = value;
}
void comb(struct nruis *p, int need, int chosen, int at) {
if (!p || p->n < need + at) return;
if (!need) {
push_int(p, chosen);
return;
}
comb(p, need - 1, chosen | (1 << at), at + 1);
comb(p, need, chosen, at + 1);
}
struct nruis *create_combinations(int n, int r) {
if (sizeof (unsigned int) * CHAR_BIT < n) return 0;
if (n < r) return 0;
struct nruis
*p
= malloc(sizeof (struct nruis
)); p->n = n;p->r = r;p->size = 0;
p->cap = count_combinations(n, r);
p
->is
= malloc(sizeof (int) * r
); p
->uis
= malloc(sizeof (unsigned int) * p
->cap
); comb(p, r, 0, 0);
return p;
}
void delete_nruis(struct nruis *p) {
if (p) {
}
}
struct nruis *ui2is(struct nruis *p, unsigned int ui) {
int i = 0, j;
if (p) for (j = 0; j < p->n; j++) if (ui & (1 << j)) p->is[i++] = j;
return p;
}
void pnruis(struct nruis *p) {
int i;
if (p) for (i = 0; i < p->size; i++) pis(ui2is(p, p->uis[i])->is, p->r);
}
#define DIGIT_MASK 0xFull
#define DIGIT_MASK_WIDTH 4
struct nulls {int n, size, cap, *is; unsigned long long *ulls;};
struct nulls *ull2is(struct nulls *p, unsigned long long value) {
int i;
if (p) for (i = 0; i < p->n; i++) p->is[i] = (value >> DIGIT_MASK_WIDTH * i) & DIGIT_MASK;
return p;
}
unsigned long long is2ull(struct nulls *p) {
int i;
unsigned long long value = 0;
if (p) for (i = 0; i < p->n; i++) value |= (unsigned long long)p->is[i] << DIGIT_MASK_WIDTH * i;
return value;
}
#undef DIGIT_MASK
#undef DIGIT_MASK_WIDTH
void push_current_buff(struct nulls *p) {
if (p && p->size + 1 <= p->cap) p->ulls[p->size++] = is2ull(p);
}
void permute(struct nulls *p, int l, int r) {
int i, tmp;
if (!p) return;
else if (l == r) push_current_buff(p);
else {
for (i = l; i <= r; i++) {
#define SWAP(t, p, q) (t = *(p), *(p) = *(q), *(q) = t)
SWAP(tmp, p->is + l, p->is + i);
permute(p, l + 1, r);
SWAP(tmp, p->is + l, p->is + i);
#undef SWAP
}
}
}
#define DIGIT_MAX 15
struct nulls *create_permutations(int n) {
if (n < 1 || DIGIT_MAX + 1 < n) return 0;
int i;
struct nulls
*p
= malloc(sizeof (struct nulls
)); p->n = n;p->size = 0;
p->cap = count_permutations(n, n);
p
->is
= malloc(sizeof (int) * n
); for (i = 0; i < n; i++) p->is[i] = i;
p
->ulls
= malloc(sizeof (unsigned long long) * p
->cap
); permute(p, 0, n-1);
return p;
}
#undef DIGIT_MAX
void delete_nulls(struct nulls *p) {
if (p) {
}
}
void pnulls(struct nulls *p) {
int i;
if (p) for (i = 0; i < p->size; i++) pis(ull2is(p, p->ulls[i])->is, p->n);
}
struct pool {int *nums, **ps, n_ps;};
struct pool *create_pool(const char *cs) {
struct pool *pool = 0;
int counts
[128] = {0}, i
, len
= strlen(cs
), n_alpha
= 0, **p
; for (i = 0; i < len; i++) counts[cs[i]]++;
for (i
= 0; i
< 128; i
++) if (counts
[i
] && isalpha(i
)) n_alpha
++; pool
= malloc(sizeof (struct pool
)); pool
->nums
= malloc(sizeof (int) * 128); pool
->ps
= malloc(sizeof (int *) * n_alpha
); pool->n_ps = n_alpha;
for (i
= 0, p
= pool
->ps
; i
< 128; i
++) if (counts
[i
] && isalpha(i
)) *p
++ = &pool
->nums
[i
]; return pool;
}
void delete_pool(struct pool *p) {
if (p) {
}
}
void p(struct pool *pool) {
int i;
for (i
= 0; i
< pool
->n_ps
; i
++) printf("%d: %d\n", i
, *pool
->ps
[i
]); }
int cs2i(const char *cs, struct pool *pool) {
int i
, len
= strlen(cs
), j
= 1, ret
= 0; for (i = 0; i < len; i++) {
ret += pool->nums[cs[len - 1 - i]] * j;
j *= 10;
}
return ret;
}
struct pool *create_pool3(const char *a, const char *b, const char *c) {
struct pool *pool = create_pool(buff);
return pool;
}
void f440(const char *a, int (*op)(int, int), const char *b, const char *c) {
struct pool *pool = create_pool3(a, b, c);
struct nruis *combinations = create_combinations(10, pool->n_ps);
struct nulls *permutations = create_permutations(pool->n_ps);
int i, j, k;
printf("%s\t%s\t%s\n", a
, b
, c
); for (i = 0; i < combinations->size; i++) {
ui2is(combinations, combinations->uis[i]);
for (j = 0; j < permutations->size; j++) {
ull2is(permutations, permutations->ulls[j]);
for (k = 0; k < pool->n_ps; k++) *pool->ps[k] = combinations->is[permutations->is[k]];
if (pool->nums[*a] == 0 || pool->nums[*b] == 0 || pool->nums[*c] == 0) continue;
if (op(cs2i(a, pool), cs2i(b, pool)) == cs2i(c, pool)) {
printf("%d\t%d\t%d\n", cs2i
(a
, pool
), cs2i
(b
, pool
), cs2i
(c
, pool
)); }
}
}
delete_nulls(permutations);
delete_nruis(combinations);
delete_pool(pool);
}
int add(int a, int b) {return a + b;}
int sub(int a, int b) {return a - b;}
int main() {
f440("SEND", add, "MORE", "MONEY");
f440("WWWDOT", sub, "GOOGLE", "DOTCOM");
return 0;
}
I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdHJpbmcuaD4KI2luY2x1ZGUgPHN0ZGxpYi5oPgojaW5jbHVkZSA8bGltaXRzLmg+Cgp2b2lkIHBpcyhpbnQgKmlzLCBpbnQgc2l6ZSkgewogIGludCBpOwogIGZvciAoaSA9IDA7IGkgPCBzaXplOyBpKyspIHByaW50ZigiJWQgIiwgaXNbaV0pOwogIHB1dHMoIiIpOwp9CmludCBmYWN0KGludCBuKSB7CiAgaW50IGksIGZhY3QgPSAxOwogIGZvciAoaSA9IDE7IGkgPD0gbjsgaSsrKSBmYWN0ICo9IGk7CiAgcmV0dXJuIGZhY3Q7Cn0KaW50IGNvdW50X3Blcm11dGF0aW9ucyhpbnQgbiwgaW50IHIpIHtyZXR1cm4gZmFjdChuKSAvIGZhY3QobiAtIHIpO30KaW50IGNvdW50X2NvbWJpbmF0aW9ucyhpbnQgbiwgaW50IHIpIHtyZXR1cm4gY291bnRfcGVybXV0YXRpb25zKG4sIHIpIC8gZmFjdChyKTt9CgoKc3RydWN0IG5ydWlzIHtpbnQgbiwgciwgc2l6ZSwgY2FwLCAqaXM7IHVuc2lnbmVkIGludCAqdWlzO307CnZvaWQgcHVzaF9pbnQoc3RydWN0IG5ydWlzICpwLCBpbnQgdmFsdWUpIHsKICBpZiAocCAmJiBwLT5zaXplICsgMSA8PSBwLT5jYXApIHAtPnVpc1twLT5zaXplKytdID0gdmFsdWU7Cn0Kdm9pZCBjb21iKHN0cnVjdCBucnVpcyAqcCwgaW50IG5lZWQsIGludCBjaG9zZW4sIGludCBhdCkgewogIGlmICghcCB8fCBwLT5uIDwgbmVlZCArIGF0KSByZXR1cm47CiAgaWYgKCFuZWVkKSB7CiAgICBwdXNoX2ludChwLCBjaG9zZW4pOwogICAgcmV0dXJuOwogIH0KICBjb21iKHAsIG5lZWQgLSAxLCBjaG9zZW4gfCAoMSA8PCBhdCksIGF0ICsgMSk7CiAgY29tYihwLCBuZWVkLCBjaG9zZW4sIGF0ICsgMSk7Cn0Kc3RydWN0IG5ydWlzICpjcmVhdGVfY29tYmluYXRpb25zKGludCBuLCBpbnQgcikgewogIGlmIChzaXplb2YgKHVuc2lnbmVkIGludCkgKiBDSEFSX0JJVCA8IG4pIHJldHVybiAwOwogIGlmIChuIDwgcikgcmV0dXJuIDA7CiAgc3RydWN0IG5ydWlzICpwID0gbWFsbG9jKHNpemVvZiAoc3RydWN0IG5ydWlzKSk7CiAgcC0+biA9IG47cC0+ciA9IHI7cC0+c2l6ZSA9IDA7CiAgcC0+Y2FwID0gY291bnRfY29tYmluYXRpb25zKG4sIHIpOwogIHAtPmlzID0gbWFsbG9jKHNpemVvZiAoaW50KSAqIHIpOwogIHAtPnVpcyA9IG1hbGxvYyhzaXplb2YgKHVuc2lnbmVkIGludCkgKiBwLT5jYXApOwogIGNvbWIocCwgciwgMCwgMCk7CiAgcmV0dXJuIHA7Cn0Kdm9pZCBkZWxldGVfbnJ1aXMoc3RydWN0IG5ydWlzICpwKSB7CiAgaWYgKHApIHsKICAgIGZyZWUocC0+dWlzKTsKICAgIGZyZWUocC0+aXMpOwogICAgZnJlZShwKTsKICB9Cn0Kc3RydWN0IG5ydWlzICp1aTJpcyhzdHJ1Y3QgbnJ1aXMgKnAsIHVuc2lnbmVkIGludCB1aSkgewogIGludCBpID0gMCwgajsKICBpZiAocCkgZm9yIChqID0gMDsgaiA8IHAtPm47IGorKykgaWYgKHVpICYgKDEgPDwgaikpIHAtPmlzW2krK10gPSBqOwogIHJldHVybiBwOwp9CnZvaWQgcG5ydWlzKHN0cnVjdCBucnVpcyAqcCkgewogIGludCBpOwogIGlmIChwKSBmb3IgKGkgPSAwOyBpIDwgcC0+c2l6ZTsgaSsrKSBwaXModWkyaXMocCwgcC0+dWlzW2ldKS0+aXMsIHAtPnIpOwp9CgoKI2RlZmluZSBESUdJVF9NQVNLIDB4RnVsbAojZGVmaW5lIERJR0lUX01BU0tfV0lEVEggNApzdHJ1Y3QgbnVsbHMge2ludCBuLCBzaXplLCBjYXAsICppczsgdW5zaWduZWQgbG9uZyBsb25nICp1bGxzO307CnN0cnVjdCBudWxscyAqdWxsMmlzKHN0cnVjdCBudWxscyAqcCwgdW5zaWduZWQgbG9uZyBsb25nIHZhbHVlKSB7CiAgaW50IGk7CiAgaWYgKHApIGZvciAoaSA9IDA7IGkgPCBwLT5uOyBpKyspIHAtPmlzW2ldID0gKHZhbHVlID4+IERJR0lUX01BU0tfV0lEVEggKiBpKSAmIERJR0lUX01BU0s7CiAgcmV0dXJuIHA7Cn0KdW5zaWduZWQgbG9uZyBsb25nIGlzMnVsbChzdHJ1Y3QgbnVsbHMgKnApIHsKICBpbnQgaTsKICB1bnNpZ25lZCBsb25nIGxvbmcgdmFsdWUgPSAwOwogIGlmIChwKSBmb3IgKGkgPSAwOyBpIDwgcC0+bjsgaSsrKSB2YWx1ZSB8PSAodW5zaWduZWQgbG9uZyBsb25nKXAtPmlzW2ldIDw8IERJR0lUX01BU0tfV0lEVEggKiBpOwogIHJldHVybiB2YWx1ZTsKfQojdW5kZWYgRElHSVRfTUFTSwojdW5kZWYgRElHSVRfTUFTS19XSURUSAp2b2lkIHB1c2hfY3VycmVudF9idWZmKHN0cnVjdCBudWxscyAqcCkgewogIGlmIChwICYmIHAtPnNpemUgKyAxIDw9IHAtPmNhcCkgcC0+dWxsc1twLT5zaXplKytdID0gaXMydWxsKHApOwp9CnZvaWQgcGVybXV0ZShzdHJ1Y3QgbnVsbHMgKnAsIGludCBsLCBpbnQgcikgewogIGludCBpLCB0bXA7CiAgaWYgKCFwKSByZXR1cm47CiAgZWxzZSBpZiAobCA9PSByKSBwdXNoX2N1cnJlbnRfYnVmZihwKTsKICBlbHNlIHsKICAgIGZvciAoaSA9IGw7IGkgPD0gcjsgaSsrKSB7CiNkZWZpbmUgU1dBUCh0LCBwLCBxKSAodCA9ICoocCksICoocCkgPSAqKHEpLCAqKHEpID0gdCkKICAgICAgU1dBUCh0bXAsIHAtPmlzICsgbCwgcC0+aXMgKyBpKTsKICAgICAgcGVybXV0ZShwLCBsICsgMSwgcik7CiAgICAgIFNXQVAodG1wLCBwLT5pcyArIGwsIHAtPmlzICsgaSk7CiN1bmRlZiBTV0FQCiAgICB9CiAgfQp9CiNkZWZpbmUgRElHSVRfTUFYIDE1CnN0cnVjdCBudWxscyAqY3JlYXRlX3Blcm11dGF0aW9ucyhpbnQgbikgewogIGlmIChuIDwgMSB8fCBESUdJVF9NQVggKyAxIDwgbikgcmV0dXJuIDA7CiAgaW50IGk7CiAgc3RydWN0IG51bGxzICpwID0gbWFsbG9jKHNpemVvZiAoc3RydWN0IG51bGxzKSk7CiAgcC0+biA9IG47cC0+c2l6ZSA9IDA7CiAgcC0+Y2FwID0gY291bnRfcGVybXV0YXRpb25zKG4sIG4pOwogIHAtPmlzID0gbWFsbG9jKHNpemVvZiAoaW50KSAqIG4pOwogIGZvciAoaSA9IDA7IGkgPCBuOyBpKyspIHAtPmlzW2ldID0gaTsKICBwLT51bGxzID0gbWFsbG9jKHNpemVvZiAodW5zaWduZWQgbG9uZyBsb25nKSAqIHAtPmNhcCk7CiAgcGVybXV0ZShwLCAwLCBuLTEpOwogIHJldHVybiBwOwp9CiN1bmRlZiBESUdJVF9NQVgKdm9pZCBkZWxldGVfbnVsbHMoc3RydWN0IG51bGxzICpwKSB7CiAgaWYgKHApIHsKICAgIGZyZWUocC0+dWxscyk7CiAgICBmcmVlKHAtPmlzKTsKICAgIGZyZWUocCk7CiAgfQp9CnZvaWQgcG51bGxzKHN0cnVjdCBudWxscyAqcCkgewogIGludCBpOwogIGlmIChwKSBmb3IgKGkgPSAwOyBpIDwgcC0+c2l6ZTsgaSsrKSBwaXModWxsMmlzKHAsIHAtPnVsbHNbaV0pLT5pcywgcC0+bik7Cn0KCgpzdHJ1Y3QgcG9vbCB7aW50ICpudW1zLCAqKnBzLCBuX3BzO307CnN0cnVjdCBwb29sICpjcmVhdGVfcG9vbChjb25zdCBjaGFyICpjcykgewogIHN0cnVjdCBwb29sICpwb29sID0gMDsKICBpbnQgY291bnRzWzEyOF0gPSB7MH0sIGksIGxlbiA9IHN0cmxlbihjcyksIG5fYWxwaGEgPSAwLCAqKnA7CiAgZm9yIChpID0gMDsgaSA8IGxlbjsgaSsrKSBjb3VudHNbY3NbaV1dKys7CiAgZm9yIChpID0gMDsgaSA8IDEyODsgaSsrKSBpZiAoY291bnRzW2ldICYmIGlzYWxwaGEoaSkpIG5fYWxwaGErKzsKICBwb29sID0gbWFsbG9jKHNpemVvZiAoc3RydWN0IHBvb2wpKTsKICBwb29sLT5udW1zID0gbWFsbG9jKHNpemVvZiAoaW50KSAqIDEyOCk7CiAgcG9vbC0+cHMgPSBtYWxsb2Moc2l6ZW9mIChpbnQgKikgKiBuX2FscGhhKTsKICBwb29sLT5uX3BzID0gbl9hbHBoYTsKICBmb3IgKGkgPSAwLCBwID0gcG9vbC0+cHM7IGkgPCAxMjg7IGkrKykgaWYgKGNvdW50c1tpXSAmJiBpc2FscGhhKGkpKSAqcCsrID0gJnBvb2wtPm51bXNbaV07CiAgcmV0dXJuIHBvb2w7Cn0Kdm9pZCBkZWxldGVfcG9vbChzdHJ1Y3QgcG9vbCAqcCkgewogIGlmIChwKSB7CiAgICBmcmVlKHAtPnBzKTsKICAgIGZyZWUocC0+bnVtcyk7CiAgICBmcmVlKHApOwogIH0KfQp2b2lkIHAoc3RydWN0IHBvb2wgKnBvb2wpIHsKICBpbnQgaTsKICBmb3IgKGkgPSAwOyBpIDwgcG9vbC0+bl9wczsgaSsrKSBwcmludGYoIiVkOiAlZFxuIiwgaSwgKnBvb2wtPnBzW2ldKTsKfQppbnQgY3MyaShjb25zdCBjaGFyICpjcywgc3RydWN0IHBvb2wgKnBvb2wpIHsKICBpbnQgaSwgbGVuID0gc3RybGVuKGNzKSwgaiA9IDEsIHJldCA9IDA7CiAgZm9yIChpID0gMDsgaSA8IGxlbjsgaSsrKSB7CiAgICByZXQgKz0gcG9vbC0+bnVtc1tjc1tsZW4gLSAxIC0gaV1dICogajsKICAgIGogKj0gMTA7CiAgfQogIHJldHVybiByZXQ7Cn0Kc3RydWN0IHBvb2wgKmNyZWF0ZV9wb29sMyhjb25zdCBjaGFyICphLCBjb25zdCBjaGFyICpiLCBjb25zdCBjaGFyICpjKSB7CiAgY2hhciAqYnVmZiA9IG1hbGxvYyhzdHJsZW4oYSkgKyBzdHJsZW4oYikgKyBzdHJsZW4oYykgKyAxKTsKICBzcHJpbnRmKGJ1ZmYsICIlcyVzJXMiLCBhLCBiLCBjKTsKICBzdHJ1Y3QgcG9vbCAqcG9vbCA9IGNyZWF0ZV9wb29sKGJ1ZmYpOwogIGZyZWUoYnVmZik7CiAgcmV0dXJuIHBvb2w7Cn0Kdm9pZCBmNDQwKGNvbnN0IGNoYXIgKmEsIGludCAoKm9wKShpbnQsIGludCksIGNvbnN0IGNoYXIgKmIsIGNvbnN0IGNoYXIgKmMpIHsKICBzdHJ1Y3QgcG9vbCAqcG9vbCA9IGNyZWF0ZV9wb29sMyhhLCBiLCBjKTsKICBzdHJ1Y3QgbnJ1aXMgKmNvbWJpbmF0aW9ucyA9IGNyZWF0ZV9jb21iaW5hdGlvbnMoMTAsIHBvb2wtPm5fcHMpOwogIHN0cnVjdCBudWxscyAqcGVybXV0YXRpb25zID0gY3JlYXRlX3Blcm11dGF0aW9ucyhwb29sLT5uX3BzKTsKICBpbnQgaSwgaiwgazsKICBwcmludGYoIiVzXHQlc1x0JXNcbiIsIGEsIGIsIGMpOwogIGZvciAoaSA9IDA7IGkgPCBjb21iaW5hdGlvbnMtPnNpemU7IGkrKykgewogICAgdWkyaXMoY29tYmluYXRpb25zLCBjb21iaW5hdGlvbnMtPnVpc1tpXSk7CiAgICBmb3IgKGogPSAwOyBqIDwgcGVybXV0YXRpb25zLT5zaXplOyBqKyspIHsKICAgICAgdWxsMmlzKHBlcm11dGF0aW9ucywgcGVybXV0YXRpb25zLT51bGxzW2pdKTsKICAgICAgZm9yIChrID0gMDsgayA8IHBvb2wtPm5fcHM7IGsrKykgKnBvb2wtPnBzW2tdID0gY29tYmluYXRpb25zLT5pc1twZXJtdXRhdGlvbnMtPmlzW2tdXTsKICAgICAgaWYgKHBvb2wtPm51bXNbKmFdID09IDAgfHwgcG9vbC0+bnVtc1sqYl0gPT0gMCB8fCBwb29sLT5udW1zWypjXSA9PSAwKSBjb250aW51ZTsKCiAgICAgIGlmIChvcChjczJpKGEsIHBvb2wpLCBjczJpKGIsIHBvb2wpKSA9PSBjczJpKGMsIHBvb2wpKSB7CglwcmludGYoIiVkXHQlZFx0JWRcbiIsIGNzMmkoYSwgcG9vbCksIGNzMmkoYiwgcG9vbCksIGNzMmkoYywgcG9vbCkpOwogICAgICB9CiAgICB9CiAgfQogIHB1dHMoIiIpOwogIGRlbGV0ZV9udWxscyhwZXJtdXRhdGlvbnMpOwogIGRlbGV0ZV9ucnVpcyhjb21iaW5hdGlvbnMpOwogIGRlbGV0ZV9wb29sKHBvb2wpOwp9CmludCBhZGQoaW50IGEsIGludCBiKSB7cmV0dXJuIGEgKyBiO30KaW50IHN1YihpbnQgYSwgaW50IGIpIHtyZXR1cm4gYSAtIGI7fQppbnQgbWFpbigpIHsKICBmNDQwKCJTRU5EIiwgYWRkLCAiTU9SRSIsICJNT05FWSIpOwogIGY0NDAoIldXV0RPVCIsIHN1YiwgIkdPT0dMRSIsICJET1RDT00iKTsKICByZXR1cm4gMDsKfQo=