Advertisement
Guest User

Untitled

a guest
May 19th, 2023
109
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.21 KB | None | 0 0
  1. #include <algorithm>
  2. #include <stdio.h>
  3. #include <string.h>
  4. #include <unordered_set>
  5.  
  6. #ifndef N
  7. const int N = 4;
  8. #endif
  9. static char S[N+4];
  10.  
  11. template<int n> long conv(const char* p) { return p[n-1] + 10 * conv<n-1>(p); }
  12. template<> long conv<0>(const char* p) { return 0; }
  13.  
  14. template<int n> int unconv(char* p, long x) { *p = x % 10; return unconv<n-1>(p+1, x / 10); }
  15. template<> int unconv<0>(char* p, long x) { return x; }
  16.  
  17. constexpr long pow10(int n) { return n ? pow10(n-1) * 10 : 1; }
  18.  
  19. void save(long a, long b) {
  20.     if (b < pow10(N-1)) return;
  21.     printf ("%ld + %ld = %ld\n", a, b, a+b);
  22. }
  23.  
  24. void solve(int id, int m = 0) {
  25.     if (id) {
  26.         for (S[id-1]=S[id]; S[id-1]<=9; S[id-1]++) {
  27.             solve (id-1, m + S[id-1]);
  28.         }
  29.     } else if (m % 9 == 0) { // fprintf (stderr, "* %d%d%d%d\n", S[0], S[1], S[2], S[3]);
  30.         char S1[N], S2[N];
  31.         std::unordered_set<long> R;
  32.         memcpy(S1, S, N);
  33.         fprintf (stderr, "%ld\r", conv<N>(S));
  34.         do {
  35.             memcpy(S2, S1, N);
  36.             long A1 = conv<N>(S1);
  37.             R.insert(A1);
  38.             while (std::prev_permutation(S2, S2+N)) {
  39.                 long A2 = conv<N>(S2);
  40.                 if (R.count(A1+A2)) save(A1, A2);
  41.             }
  42.         } while (std::prev_permutation(S1, S1+N));
  43.     }
  44. }
  45.  
  46. int main() {
  47.     S[N] = 0;
  48.     solve (N);
  49. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement