Untitled

From Violet Pudu, 5 Years ago, written in Plain Text, viewed 293 times.
URL https://code.nat.moe/view/14b51888 Embed
Download Paste or View Raw
  1. #include <iostream>
  2. #include <string>
  3. #include <cstdlib>
  4. #include <set>
  5. #include <vector>
  6.  
  7. using namespace std;
  8.  
  9. struct Status {
  10.         int a[4], b[4], d[4];
  11.     int idx;
  12.     int carry;
  13.     int result;
  14. };
  15.  
  16. char S(int x) {
  17.     return x == -1 ? 'X' : x + '0';
  18. }
  19.  
  20. void P(const Status& s) {
  21.     return;
  22.     for (int i = 3; i >= 0; --i) {
  23.         cout << S(s.a[i]);
  24.     }
  25.     cout << "|";
  26.     for (int i = 3; i >= 0; --i) {
  27.         cout << S(s.b[i]);
  28.     }
  29.     cout << "|";
  30.     for (int i = 3; i >= 0; --i) {
  31.         cout << S(s.d[i]);
  32.     }
  33.     cout << "|#" << s.idx << " c" << s.carry << " r" << s.result << endl;
  34. }
  35.  
  36. int solve(const Status& s) {
  37.     int idx = s.idx;
  38.     const int *a = s.a; const int *b = s.b; const int *d = s.d;
  39.     int carry = s.carry;
  40.  
  41.     P(s);
  42.    
  43.     if (idx == 3) {
  44.         return a[idx] + b[idx] + carry == d[idx] ? s.result : 0;
  45.     }
  46.    
  47.     if (a[idx] == -1 && b[idx] == -1) {
  48.         int res = 0;
  49.         { // Non-carry sub branch
  50.             Status s2 = s;
  51.             s2.result *= d[idx] - carry - 1;
  52.             if (s2.result < 0)
  53.                 return 0;
  54.             s2.carry = 0;
  55.             s2.idx += 1;
  56.             res += solve(s2);
  57.         }
  58.         { // Carry sub branch
  59.             Status s2 = s;
  60.             s2.result *= 9 - d[idx] - carry;
  61.             if (s2.result < 0) s2.result = 0;
  62.             s2.carry = 1;
  63.             s2.idx += 1;
  64.             res += solve(s2);
  65.         }
  66.         return res;
  67.     } else if (a[idx] == -1) {
  68.         int a1 = d[idx] - carry - b[idx];
  69.         int cc = 0;
  70.         if (a1 < 0) {
  71.             a1 += 10;
  72.             cc = 1;
  73.         }
  74.        
  75.         Status s2 = s;
  76.         s2.idx += 1;
  77.         s2.carry = cc;
  78.         return solve(s2);
  79.     } else if (b[idx] == -1) {
  80.         int b1 = d[idx] - carry - a[idx];
  81.         int cc = 0;
  82.         if (b1 < 0) {
  83.             b1 += 10;
  84.             cc = 1;
  85.         }
  86.        
  87.         Status s2 = s;
  88.         s2.idx += 1;
  89.         s2.carry = cc;
  90.         return solve(s2);
  91.     } else {
  92.         int sum = a[idx] + b[idx] + carry;
  93.         Status s2 = s;
  94.         if (sum >= 10) {
  95.             if (sum - 10 != d[idx])
  96.                 return 0;
  97.  
  98.             s2.carry = 1;
  99.             s2.idx += 1;
  100.             return solve(s2);
  101.         } else {
  102.             if (sum != d[idx])
  103.                 return 0;
  104.            
  105.             s2.carry = 0;
  106.             s2.idx += 1;
  107.             return solve(s2);
  108.         }
  109.     }
  110. }
  111.  
  112. void mapp(string& s, int* targ) {
  113.     if (s.size() == 2) s = "00" + s;
  114.     if (s.size() == 3) s = "0" + s;
  115.     if (s.size() == 1) s = "000" + s;
  116.  
  117.     size_t idx = 0;
  118.     for (; idx < 4; ++idx) {
  119.         if (s[3 - idx] == 'X') {
  120.             targ[idx] = -1;
  121.         } else {
  122.             targ[idx] = s[3 - idx] - '0';
  123.         }
  124.     }
  125. }
  126.  
  127. int main() {
  128.     int n;
  129.     cin >> n;
  130.     while (n-->0) {
  131.         Status s;
  132.         string a, b, c;
  133.         cin >> a >> b >> c;
  134.         mapp(a, s.a);
  135.         mapp(b, s.b);
  136.         mapp(c, s.d);
  137.  
  138.         s.idx = 0;
  139.         s.carry = 0;
  140.         s.result = 1;
  141.  
  142.  
  143.         P(s);
  144.  
  145.         cout << solve(s) << endl;
  146.     }
  147. }

Reply to "Untitled"

Here you can reply to the paste above

captcha