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)
- using namespace std;
- using ll = long long;
- bool psp(string &s) {
- int b = 0;
- for (char ch: s) {
- if (ch == '(') {
- b++;
- } else if (ch == ')') {
- b--;
- }
- if (b < 0) return false;
- }
- return b == 0;
- }
- const string signs = "+-*";
- // +-*
- vector<string> bad = {
- "++",
- "+*",
- "-+",
- "-*",
- "*+",
- "**"
- };
- bool is_correct(string &s) {
- const int n = (int) s.size();
- for (int i = 1; i < n - 1; i++) {
- if (!isdigit(s[i - 1]) && isdigit(s[i]) && isdigit(s[i + 1])) {
- if (s[i] == '0') {
- return false; // leading zeros
- }
- }
- }
- for (int i = 0; i < n; i++) {
- if (s[i] == '(') {
- if (i > 0) {
- if (isdigit(s[i - 1])) return false;
- }
- }
- if (s[i] == ')') {
- if (i + 1 < n) {
- if (isdigit(s[i + 1])) return false;
- }
- }
- }
- if (s[0] == '+') {
- return false;
- }
- if (s[0] == '*') {
- return false;
- }
- if (s.size() > 1) {
- if (s[0] == '0' && isdigit(s[1])) {
- return false;
- }
- }
- for (int i = 0; i < n - 1; i++) {
- string f = s.substr(i, 2);
- if (find(all(bad), f) != bad.end()) {
- return false;
- }
- }
- return true;
- }
- const int KEK = -1e9 - 12341;
- enum OP {
- MUL,
- SUM,
- MIN,
- VAL
- };
- string compress(string t) {
- string x;
- int n = (int) t.size();
- for (int i = 0; i < n;) {
- if (t[i] != '-') {
- x.push_back(t[i]);
- i++;
- } else {
- int j = i;
- int c = 0;
- while (j < n && t[j] == '-') {
- c ^= 1;
- j++;
- }
- if (c) {
- x.push_back('-');
- } else {
- x.push_back('-');
- x.push_back('-');
- }
- i = j;
- }
- }
- return x;
- }
- int get2(string s) { // 01+-*
- if (s.empty() || s[0] == '*' || s[0] == '+') {
- return KEK;
- }
- int n = (int) s.size();
- // minus is unary operation
- // --1010 -> reverse with +
- // +-1010 -> reverse with -
- // *-1234 -> use like unary
- int ptr = 0;
- for (int i = 0; i < n; i++) {
- if (i > 0 && s[ptr - 1] == '-' && s[i] == '-') {
- s[ptr - 1] = '+';
- } else if (i > 0 && s[ptr - 1] == '+' && s[i] == '-') {
- s[ptr - 1] = '-';
- } else {
- s[ptr++] = s[i];
- }
- }
- s.resize(ptr);
- n = ptr;
- vector<pair<int, int>> arr;
- for (int i = 0; i < n;) {
- if (s[i] == '+') {
- arr.emplace_back(SUM, 0);
- i++;
- } else if (s[i] == '-') {
- arr.emplace_back(MIN, 0);
- i++;
- } else if (s[i] == '*') {
- arr.emplace_back(MUL, 0);
- i++;
- } else {
- int val = 0;
- while (i < n && isdigit(s[i])) {
- val *= 2;
- val += s[i] - '0';
- i++;
- }
- arr.emplace_back(VAL, val);
- }
- }
- int k = (int) arr.size();
- ptr = 0;
- for (int i = 0; i < k; i++) {
- if (arr[i].first == MIN) {
- if (i + 1 == k) return KEK;
- if (arr[i + 1].first != VAL) return KEK;
- arr[i + 1].second *= -1;
- if (i > 0 && arr[ptr - 1].first != MUL) {
- arr[ptr++] = {SUM, 0};
- }
- } else {
- arr[ptr++] = arr[i];
- }
- }
- // +*10
- arr.resize(ptr);
- k = ptr;
- ptr = 0;
- for (int i = 0; i < k;) {
- if (arr[i].first == MUL) {
- if (i + 1 >= k || arr[i + 1].first != VAL) return KEK;
- arr[ptr - 1].second *= arr[i + 1].second;
- i += 2;
- } else {
- arr[ptr++] = arr[i++];
- }
- }
- k = ptr;
- arr.resize(k);
- // 0101 +
- int answer = 0;
- for (auto[fl, val]: arr) {
- if (fl == VAL) {
- answer += val;
- }
- }
- if (arr.back().first != VAL) {
- return KEK;
- }
- return answer;
- }
- string to_bin(int val) {
- string res;
- if (val == 0) return "0";
- while (val) {
- res.push_back(char('0' + (val & 1)));
- val >>= 1;
- }
- reverse(all(res));
- return res;
- }
- int get(string s) {
- s = "(" + s + ")";
- int n = (int) s.size();
- vector<pair<int, int>> psp;
- vector<int> ind;
- for (int i = 0; i < n; i++) {
- if (s[i] == '(') {
- ind.push_back(i);
- }
- if (s[i] == ')') {
- psp.emplace_back(ind.back(), i);
- ind.pop_back();
- }
- }
- sort(all(psp));
- reverse(all(psp));
- for (auto[l, r]: psp) {
- if (l + 1 == r) { // ()
- return KEK;
- }
- string cur = s.substr(l + 1, r - l - 1);
- int value = get2(cur);
- if (value == KEK) return KEK;
- for (int i = l; i <= r; i++) {
- s[i] = '0';
- }
- if (l == 0) {
- return value;
- }
- if (value < 0) {
- s[l] = '-';
- }
- string b = to_bin(abs(value));
- int le = (int) b.size();
- for (int j = 0; j < le; j++) {
- s[r - j] = b[le - 1 - j];
- }
- }
- return KEK;
- }
- bool check(const string &s) {
- // 01+-*()=
- if (count(all(s), '=') != 1) return false;
- int mid = (int) s.find('=');
- string left = s.substr(0, mid);
- string right = s.substr(mid + 1, s.size() - mid - 1);
- if (left.empty() || right.empty()) return false;
- if (!psp(left) || !psp(right)) return false;
- if (!is_correct(left) || !is_correct(right)) return false;
- left = compress(left);
- right = compress(right);
- int leftRes = get(left);
- int rightRes = get(right);
- if (leftRes == KEK || rightRes == KEK) return false;
- return leftRes == rightRes;
- }
- void solve() {
- string s;
- cin >> s;
- // [01+-*()=]*
- // [A-Za-z]*
- vector<char> arr;
- const int n = (int) s.size();
- for (int i = 0; i < n; i++) {
- if (s[i] >= 'a' && s[i] <= 'z' || s[i] >= 'A' && s[i] <= 'Z') {
- arr.push_back(s[i]);
- }
- }
- sort(all(arr));
- arr.erase(unique(all(arr)), end(arr));
- if (arr.size() > 8) {
- cout << 0 << '\n';
- return;
- }
- string c = "01+-*()=";
- sort(all(c));
- vector<char> rep(256);
- iota(all(rep), 0);
- vector<string> correct;
- long long answer = 0;
- set<string> used;
- do {
- for (int i = 0; i < int(arr.size()); i++) {
- rep[arr[i]] = c[i];
- }
- string t = s;
- for (char &i: t) {
- i = rep[i];
- }
- if (used.count(t)) continue;
- used.insert(t);
- if (check(t)) {
- answer++;
- }
- } while (next_permutation(all(c)));
- cout << answer << '\n';
- }
- int main() {
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- solve();
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement