Advertisement
999ms

Untitled

Aug 30th, 2020
1,604
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.31 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. #define all(x) begin(x),end(x)
  3. #define make_unique(v) sort(all(v)); v.erase(unique(all(v)), end(v))
  4.  
  5. using namespace std;
  6. using ll = long long;
  7.  
  8. bool has(string s, char ch) {
  9.     for (char c : s) if (c == ch) return true;
  10.     return false;
  11. }
  12.  
  13. struct Note {
  14.     char sign = 0;
  15.     int val = 0;
  16. };
  17.  
  18. void dbg(vector<Note> v) {
  19.     for (auto n : v) {
  20.         if (n.sign) cout << n.sign;
  21.         else cout << n.val;
  22.     }
  23.     cout << '\n';
  24. }
  25.  
  26.  
  27. vector<vector<Note>> split(vector<Note>& v, string ch) {
  28.     vector<vector<Note>> res;
  29.     vector<Note> cur;
  30.     for (int i = 0; i < int(v.size()); i++) {
  31.         if (has(ch, v[i].sign)) {
  32.             if (cur.size()) {
  33.                 res.push_back(cur);
  34.                 cur.clear();
  35.             }
  36.         } else {
  37.             cur.push_back(v[i]);
  38.         }
  39.     }
  40.     if (cur.size()) res.push_back(cur);
  41.     return res;
  42. }
  43.  
  44.  
  45.  
  46. int calcAdd(const vector<Note>& s) {
  47.     int n = s.size();
  48.     vector<Note> cur;
  49.     for (int i = 0; i < n; i++) {
  50.         if (s[i].sign == 0) {
  51.             cur.push_back(Note(s[i]));
  52.         } else if (s[i].sign == '*') {
  53.             cur.back().val *= s[i + 1].val;
  54.             i++;
  55.         } else {
  56.             cur.push_back(Note(s[i]));
  57.         }
  58.     }
  59.     int ans = 0;
  60.     n = cur.size();
  61.     int pre = 1;
  62.     for (int i = 0; i < n; i++) {
  63.         if (cur[i].sign == 0) {
  64.             ans += pre * cur[i].val;
  65.             pre = 1;
  66.         } else if (cur[i].sign == '+') {
  67.             pre *= 1;
  68.         } else if (cur[i].sign == '-') {
  69.             pre *= -1;
  70.         } else {
  71.             assert(false);
  72.         }
  73.     }
  74.     return ans;
  75. }
  76.  
  77. int calc(vector<Note> s) {
  78.     s.push_back(Note{')', 0});
  79.     s.push_back(Note{'(', 0});
  80.     for (int i = s.size() - 2; i >= 0; i--) {
  81.         swap(s[i], s[i + 1]);
  82.     }
  83.     vector<Note> cur;
  84.     for (auto& note : s) {
  85.         if (note.sign == ')') {
  86.             vector<Note> nxt;
  87.             while (cur.size() && cur.back().sign != '(') {
  88.                 nxt.push_back(cur.back());
  89.                 cur.pop_back();
  90.             }
  91.             cur.pop_back();
  92.             reverse(all(nxt));
  93.             cur.push_back(Note{0, calcAdd(nxt)});
  94.         } else {
  95.             cur.push_back(note);
  96.         }
  97.     }
  98.     return cur[0].val;
  99. }
  100.  
  101. set<string> USED;
  102.  
  103. bool correct(string s) {
  104.     if (USED.count(s)) return false;
  105.     USED.insert(s);
  106.     vector<int> cnt(256);
  107.     for (char ch : s) cnt[ch]++;
  108.    
  109.     if (cnt['='] != 1) return false;
  110.     if (cnt['('] != cnt[')']) return false;
  111.     if (cnt['0'] + cnt['1'] < 2) return false;
  112.    
  113.     int n = s.size();
  114.     int mid = s.find('=');
  115.    
  116.     int f = 0;
  117.     for (int i = 0; i < mid; i++) {
  118.         if (s[i] == '(') f++;
  119.         else if (s[i] == ')') f--;
  120.         if (f < 0) return false;
  121.     }
  122.     if (f) return false;
  123.    
  124.     for (int i = mid + 1; i < n; i++) {
  125.         if (s[i] == '(') f++;
  126.         else if (s[i] == ')') f--;
  127.         if (f < 0) return false;
  128.     }
  129.     if (f) return false;
  130.    
  131.    
  132.    
  133.     string oper = "-+*=";
  134.     string nome = "01()";
  135.    
  136.     for (int i = 0; i < n; i++) {
  137.         if (s[i] == '-') {
  138.             if (i == 0) continue;
  139.             if (s[i - 1] != '=' && s[i - 1] != '-' && has(oper, s[i - 1])) return false;
  140.             if (i + 1 == n) return false;
  141.             if (s[i + 1] != '-' && has(oper, s[i + 1])) return false;
  142.             if (s[i + 1] != '0' && s[i + 1] != '1' && s[i + 1] != '(' && s[i + 1] != '-') return false;
  143.         } else if (s[i] == '=') {
  144.             if (i == 0 || i + 1 == n) return false;
  145.             if (s[i - 1] != ')' && s[i - 1] != '0' && s[i - 1] != '1') return false;
  146.             if (s[i + 1] != '(' && s[i + 1] != '-' && s[i + 1] != '0' && s[i + 1] != '1') return false;
  147.         } else if (s[i] == '+' || s[i] == '*') {
  148.             if (i == 0 || i + 1 == n) return false;
  149.             if (s[i - 1] != '0' && s[i - 1] != '1' && s[i - 1] != ')') return false;
  150.             if (s[i + 1] != '0' && s[i + 1] != '1' && s[i + 1] != '(') return false;
  151.         } else if (s[i] == '(') {
  152.             if (i + 1 == n || s[i + 1] == ')') return false;
  153.         } else if (s[i] == ')') {
  154.             if (i + 1 < n && s[i + 1] ==  '(') return false;
  155.         }
  156.     }
  157.    
  158.    
  159.     for (int i = 0; i < n; i++) {
  160.         if (s[i] == '(' && i) {
  161.             if (s[i - 1] == '0' || s[i - 1] == '1') return false;
  162.         }
  163.         if (s[i] == ')' && i + 1 < n) {
  164.             if (s[i + 1] == '0' || s[i + 1] == '1') return false;
  165.         }
  166.     }
  167.    
  168.     for (int i = 0; i < n - 1; i++) {
  169.         if ((s[i + 1] == '0' || s[i + 1] == '1') && s[i] == '0') {
  170.             if (i == 0 || (s[i - 1] != '1' && s[i - 1] != '0')) {
  171.                 return false;
  172.             }
  173.         }
  174.     }
  175.    
  176.     vector<Note> notes;
  177.     int cur = 0;
  178.     for (int i = 0; i < n; i++) {
  179.         if (s[i] != '0' && s[i] != '1') {
  180.             notes.push_back({s[i], 0});
  181.         } else {
  182.             cur = cur * 2 + s[i] - '0';
  183.             if (i + 1 == n || (s[i + 1] != '0' && s[i + 1] != '1')) {
  184.                 notes.push_back({0, cur});
  185.                 cur = 0;
  186.             }
  187.         }
  188.     }
  189.     auto v = split(notes, "=");
  190.    
  191.     return size(v) == 2u && calc(v[0]) == calc(v[1]);
  192. }
  193.  
  194.  
  195. int main(){
  196.     ios::sync_with_stdio(false);
  197.     cin.tie(nullptr);
  198.     cout.tie(nullptr);
  199.     string s;
  200.     cin >> s;;
  201.    
  202.     string used = "01+-*()=";
  203.     sort(all(used));
  204.     set<char> st;
  205.     for (char ch : s) {
  206.         if (int(used.find(ch)) == -1) {
  207.             st.insert(ch);
  208.         }
  209.     }
  210.    
  211.     if (st.size() > 8u) {
  212.         cout << "0\n";
  213.         return 0;
  214.     }
  215.    
  216.     vector<char> p;
  217.     for (char ch : st) p.push_back(ch);
  218.     set<string> res;
  219.  
  220.     do {
  221.         string cur = s;
  222.         int d = p.size();
  223.         for (int i = 0; i < d; i++) {
  224.             for (int j = 0; j < int(cur.size()); j++) {
  225.                 if (cur[j] == p[i]) {
  226.                     cur[j] = used[i];
  227.                 }
  228.             }
  229.         }
  230.         if (correct(cur)) {
  231.             res.insert(cur);
  232.         }
  233.     } while (next_permutation(all(used)));
  234.     cout << res.size() << '\n';
  235. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement