#include <stdio.h>
#include <stdlib.h>
/* see http://e...content-available-to-author-only...a.org/wiki/Permutation#Generation_in_lexicographic_order */
int permnext(char *p, int n) {
int kh, k = -1;
int lh, l = -1;
char tmp;
for (kh = 0; kh < n - 1; kh++) {
if (p[kh] < p[kh + 1]) k = kh;
}
if (k == -1) return 1;
for (lh = k + 1; lh < n; lh++) {
if (p[k] < p[lh]) l = lh;
}
if (l == -1) {
fprintf(stderr
, "This didn't happen.\n"); }
tmp = p[k]; p[k] = p[l]; p[l] = tmp;
l = k + 1;
lh = n - 1;
while (l < lh) {
tmp = p[l]; p[l] = p[lh]; p[lh] = tmp;
l++;
lh--;
}
return 0;
}
void check(const char *p, int nda, int ndb, int ndc, int ndd) {
int a = 0, b = 0, c = 0, d = 0;
if (p[nda] == '0') return;
if (p[nda + ndb] == '0') return;
if (p[nda + ndb + ndc] == '0') return;
while (nda--) { a *= 10; a += *p - '0'; p++; }
while (ndb--) { b *= 10; b += *p - '0'; p++; }
if (b < a) return;
while (ndc--) { c *= 10; c += *p - '0'; p++; }
if (c < a) return;
while (ndd--) { d *= 10; d += *p - '0'; p++; }
if (d < c) return;
if (a*d + b*c == b*d) {
printf("%d/%d + %d/%d = 1\n", a
, b
, c
, d
); }
}
int main(void) {
char perm[] = "1023456789";
do {
check(perm, 1, 1, 1, 7);
check(perm, 1, 1, 2, 6);
check(perm, 1, 1, 3, 5);
check(perm, 1, 1, 4, 4);
check(perm, 1, 2, 1, 6);
check(perm, 1, 2, 2, 5);
check(perm, 1, 2, 3, 4);
check(perm, 1, 3, 1, 5);
check(perm, 1, 3, 2, 4);
check(perm, 1, 3, 3, 3);
check(perm, 1, 4, 1, 4);
check(perm, 1, 4, 2, 3);
check(perm, 1, 5, 1, 3);
check(perm, 1, 5, 2, 2);
check(perm, 1, 6, 1, 2);
check(perm, 1, 7, 1, 1);
check(perm, 2, 2, 2, 4);
check(perm, 2, 2, 3, 3);
check(perm, 2, 3, 2, 3);
check(perm, 2, 4, 2, 2);
} while (permnext(perm, 10) == 0);
return 0;
}
I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdGRsaWIuaD4KCi8qIHNlZSBodHRwOi8vZS4uLmNvbnRlbnQtYXZhaWxhYmxlLXRvLWF1dGhvci1vbmx5Li4uYS5vcmcvd2lraS9QZXJtdXRhdGlvbiNHZW5lcmF0aW9uX2luX2xleGljb2dyYXBoaWNfb3JkZXIgKi8KaW50IHBlcm1uZXh0KGNoYXIgKnAsIGludCBuKSB7CiAgaW50IGtoLCBrID0gLTE7CiAgaW50IGxoLCBsID0gLTE7CiAgY2hhciB0bXA7CgogIGZvciAoa2ggPSAwOyBraCA8IG4gLSAxOyBraCsrKSB7CiAgICBpZiAocFtraF0gPCBwW2toICsgMV0pIGsgPSBraDsKICB9CiAgaWYgKGsgPT0gLTEpIHJldHVybiAxOwogIGZvciAobGggPSBrICsgMTsgbGggPCBuOyBsaCsrKSB7CiAgICBpZiAocFtrXSA8IHBbbGhdKSBsID0gbGg7CiAgfQogIGlmIChsID09IC0xKSB7CiAgICBmcHJpbnRmKHN0ZGVyciwgIlRoaXMgZGlkbid0IGhhcHBlbi5cbiIpOwogICAgZXhpdChFWElUX0ZBSUxVUkUpOwogIH0KICB0bXAgPSBwW2tdOyBwW2tdID0gcFtsXTsgcFtsXSA9IHRtcDsKICBsID0gayArIDE7CiAgbGggPSBuIC0gMTsKICB3aGlsZSAobCA8IGxoKSB7CiAgICB0bXAgPSBwW2xdOyBwW2xdID0gcFtsaF07IHBbbGhdID0gdG1wOwogICAgbCsrOwogICAgbGgtLTsKICB9CiAgcmV0dXJuIDA7Cn0KCnZvaWQgY2hlY2soY29uc3QgY2hhciAqcCwgaW50IG5kYSwgaW50IG5kYiwgaW50IG5kYywgaW50IG5kZCkgewogIGludCBhID0gMCwgYiA9IDAsIGMgPSAwLCBkID0gMDsKICBpZiAocFtuZGFdID09ICcwJykgcmV0dXJuOwogIGlmIChwW25kYSArIG5kYl0gPT0gJzAnKSByZXR1cm47CiAgaWYgKHBbbmRhICsgbmRiICsgbmRjXSA9PSAnMCcpIHJldHVybjsKICB3aGlsZSAobmRhLS0pIHsgYSAqPSAxMDsgYSArPSAqcCAtICcwJzsgcCsrOyB9CiAgd2hpbGUgKG5kYi0tKSB7IGIgKj0gMTA7IGIgKz0gKnAgLSAnMCc7IHArKzsgfQogIGlmIChiIDwgYSkgcmV0dXJuOwogIHdoaWxlIChuZGMtLSkgeyBjICo9IDEwOyBjICs9ICpwIC0gJzAnOyBwKys7IH0KICBpZiAoYyA8IGEpIHJldHVybjsKICB3aGlsZSAobmRkLS0pIHsgZCAqPSAxMDsgZCArPSAqcCAtICcwJzsgcCsrOyB9CiAgaWYgKGQgPCBjKSByZXR1cm47CiAgaWYgKGEqZCArIGIqYyA9PSBiKmQpIHsKICAgIHByaW50ZigiJWQvJWQgKyAlZC8lZCA9IDFcbiIsIGEsIGIsIGMsIGQpOwogIH0KfQoKaW50IG1haW4odm9pZCkgewogIGNoYXIgcGVybVtdID0gIjEwMjM0NTY3ODkiOwogIGRvIHsKICAgIGNoZWNrKHBlcm0sIDEsIDEsIDEsIDcpOwogICAgY2hlY2socGVybSwgMSwgMSwgMiwgNik7CiAgICBjaGVjayhwZXJtLCAxLCAxLCAzLCA1KTsKICAgIGNoZWNrKHBlcm0sIDEsIDEsIDQsIDQpOwogICAgY2hlY2socGVybSwgMSwgMiwgMSwgNik7CiAgICBjaGVjayhwZXJtLCAxLCAyLCAyLCA1KTsKICAgIGNoZWNrKHBlcm0sIDEsIDIsIDMsIDQpOwogICAgY2hlY2socGVybSwgMSwgMywgMSwgNSk7CiAgICBjaGVjayhwZXJtLCAxLCAzLCAyLCA0KTsKICAgIGNoZWNrKHBlcm0sIDEsIDMsIDMsIDMpOwogICAgY2hlY2socGVybSwgMSwgNCwgMSwgNCk7CiAgICBjaGVjayhwZXJtLCAxLCA0LCAyLCAzKTsKICAgIGNoZWNrKHBlcm0sIDEsIDUsIDEsIDMpOwogICAgY2hlY2socGVybSwgMSwgNSwgMiwgMik7CiAgICBjaGVjayhwZXJtLCAxLCA2LCAxLCAyKTsKICAgIGNoZWNrKHBlcm0sIDEsIDcsIDEsIDEpOwogICAgY2hlY2socGVybSwgMiwgMiwgMiwgNCk7CiAgICBjaGVjayhwZXJtLCAyLCAyLCAzLCAzKTsKICAgIGNoZWNrKHBlcm0sIDIsIDMsIDIsIDMpOwogICAgY2hlY2socGVybSwgMiwgNCwgMiwgMik7CiAgfSB3aGlsZSAocGVybW5leHQocGVybSwgMTApID09IDApOwogIHJldHVybiAwOwp9