Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- #define all(x) begin(x),end(x)
- #define make_unique(v) sort(all(v)); v.erase(unique(all(v)), end(v))
- using namespace std;
- using ll = long long;
- bool has(string s, char ch) {
- for (char c : s) if (c == ch) return true;
- return false;
- }
- struct Note {
- char sign = 0;
- int val = 0;
- };
- void dbg(vector<Note> v) {
- for (auto n : v) {
- if (n.sign) cout << n.sign;
- else cout << n.val;
- }
- cout << '\n';
- }
- vector<vector<Note>> split(vector<Note>& v, string ch) {
- vector<vector<Note>> res;
- vector<Note> cur;
- for (int i = 0; i < int(v.size()); i++) {
- if (has(ch, v[i].sign)) {
- if (cur.size()) {
- res.push_back(cur);
- cur.clear();
- }
- } else {
- cur.push_back(v[i]);
- }
- }
- if (cur.size()) res.push_back(cur);
- return res;
- }
- int calcAdd(const vector<Note>& s) {
- int n = s.size();
- vector<Note> cur;
- for (int i = 0; i < n; i++) {
- if (s[i].sign == 0) {
- cur.push_back(Note(s[i]));
- } else if (s[i].sign == '*') {
- cur.back().val *= s[i + 1].val;
- i++;
- } else {
- cur.push_back(Note(s[i]));
- }
- }
- int ans = 0;
- n = cur.size();
- int pre = 1;
- for (int i = 0; i < n; i++) {
- if (cur[i].sign == 0) {
- ans += pre * cur[i].val;
- pre = 1;
- } else if (cur[i].sign == '+') {
- pre *= 1;
- } else if (cur[i].sign == '-') {
- pre *= -1;
- } else {
- assert(false);
- }
- }
- return ans;
- }
- int calc(vector<Note> s) {
- s.push_back(Note{')', 0});
- s.push_back(Note{'(', 0});
- for (int i = s.size() - 2; i >= 0; i--) {
- swap(s[i], s[i + 1]);
- }
- vector<Note> cur;
- for (auto& note : s) {
- if (note.sign == ')') {
- vector<Note> nxt;
- while (cur.size() && cur.back().sign != '(') {
- nxt.push_back(cur.back());
- cur.pop_back();
- }
- cur.pop_back();
- reverse(all(nxt));
- cur.push_back(Note{0, calcAdd(nxt)});
- } else {
- cur.push_back(note);
- }
- }
- return cur[0].val;
- }
- set<string> USED;
- bool correct(string s) {
- if (USED.count(s)) return false;
- USED.insert(s);
- vector<int> cnt(256);
- for (char ch : s) cnt[ch]++;
- if (cnt['='] != 1) return false;
- if (cnt['('] != cnt[')']) return false;
- if (cnt['0'] + cnt['1'] < 2) return false;
- int n = s.size();
- int mid = s.find('=');
- int f = 0;
- for (int i = 0; i < mid; i++) {
- if (s[i] == '(') f++;
- else if (s[i] == ')') f--;
- if (f < 0) return false;
- }
- if (f) return false;
- for (int i = mid + 1; i < n; i++) {
- if (s[i] == '(') f++;
- else if (s[i] == ')') f--;
- if (f < 0) return false;
- }
- if (f) return false;
- string oper = "-+*=";
- string nome = "01()";
- for (int i = 0; i < n; i++) {
- if (s[i] == '-') {
- if (i == 0) continue;
- if (s[i - 1] != '=' && s[i - 1] != '-' && has(oper, s[i - 1])) return false;
- if (i + 1 == n) return false;
- if (s[i + 1] != '-' && has(oper, s[i + 1])) return false;
- if (s[i + 1] != '0' && s[i + 1] != '1' && s[i + 1] != '(' && s[i + 1] != '-') return false;
- } else if (s[i] == '=') {
- if (i == 0 || i + 1 == n) return false;
- if (s[i - 1] != ')' && s[i - 1] != '0' && s[i - 1] != '1') return false;
- if (s[i + 1] != '(' && s[i + 1] != '-' && s[i + 1] != '0' && s[i + 1] != '1') return false;
- } else if (s[i] == '+' || s[i] == '*') {
- if (i == 0 || i + 1 == n) return false;
- if (s[i - 1] != '0' && s[i - 1] != '1' && s[i - 1] != ')') return false;
- if (s[i + 1] != '0' && s[i + 1] != '1' && s[i + 1] != '(') return false;
- } else if (s[i] == '(') {
- if (i + 1 == n || s[i + 1] == ')') return false;
- } else if (s[i] == ')') {
- if (i + 1 < n && s[i + 1] == '(') return false;
- }
- }
- for (int i = 0; i < n; i++) {
- if (s[i] == '(' && i) {
- if (s[i - 1] == '0' || s[i - 1] == '1') return false;
- }
- if (s[i] == ')' && i + 1 < n) {
- if (s[i + 1] == '0' || s[i + 1] == '1') return false;
- }
- }
- for (int i = 0; i < n - 1; i++) {
- if ((s[i + 1] == '0' || s[i + 1] == '1') && s[i] == '0') {
- if (i == 0 || (s[i - 1] != '1' && s[i - 1] != '0')) {
- return false;
- }
- }
- }
- vector<Note> notes;
- int cur = 0;
- for (int i = 0; i < n; i++) {
- if (s[i] != '0' && s[i] != '1') {
- notes.push_back({s[i], 0});
- } else {
- cur = cur * 2 + s[i] - '0';
- if (i + 1 == n || (s[i + 1] != '0' && s[i + 1] != '1')) {
- notes.push_back({0, cur});
- cur = 0;
- }
- }
- }
- auto v = split(notes, "=");
- return size(v) == 2u && calc(v[0]) == calc(v[1]);
- }
- int main(){
- ios::sync_with_stdio(false);
- cin.tie(nullptr);
- cout.tie(nullptr);
- string s;
- cin >> s;;
- string used = "01+-*()=";
- sort(all(used));
- set<char> st;
- for (char ch : s) {
- if (int(used.find(ch)) == -1) {
- st.insert(ch);
- }
- }
- if (st.size() > 8u) {
- cout << "0\n";
- return 0;
- }
- vector<char> p;
- for (char ch : st) p.push_back(ch);
- set<string> res;
- do {
- string cur = s;
- int d = p.size();
- for (int i = 0; i < d; i++) {
- for (int j = 0; j < int(cur.size()); j++) {
- if (cur[j] == p[i]) {
- cur[j] = used[i];
- }
- }
- }
- if (correct(cur)) {
- res.insert(cur);
- }
- } while (next_permutation(all(used)));
- cout << res.size() << '\n';
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement